시간복잡도 Big-oh (big-o) notation 점근 표기법
알고리즘에 대해 공부하다보면, 처음부터 볼 수 있는 개념이 하나 있다. 그것은 바로 시간복잡도이다. 현재 글을 적는 시점에서도, 나도 가끔 가다가 빅오표기법의 계산을 잘못하여 효율성을 잘못 따질때가 있다. 오늘은 이 시간복잡도에 대해서 알아보고자 한다. 모든 동작에는, 시간과 메모리가 필요로 한다. 이 중 시간복잡도는 프로그램을 실행할 때 소요되는 시간을 계산하는것이다. 구문, 함수의 종류 등에 의해 다양한 공식을 띄게 되는데, 크게 아래의 사진과 같은 방식으로 분류된다. O(1), O(logn), O(n), O(n!) 등과 같은 방식이 존재하며, 위의 방식 이외에 적힌 식에 따라 O(n^5) 등 다양한 파생된 결과가 출력될 수 있다. X축은 투입되는 자료의 갯수, Y축은 그 자료들을 투입한 프로그램의 ..
2022. 4. 28.
자료구조 기초 개념, 링크드리스트 Linked-list(Python, Java 등)
자료구조 Data Structure의 개념에 대해 간단히 설명해보고자 한다. 시험기간이기에 중간고사 범위에 대한 간략한 정리와 설명을 할 예정이다. 자료구조란 자료를 저장하고 '정렬'을 수월하게 하기 위한 방식이며, 일반적인 코드를 짜는 것보다 효율적으로 코드를 짤 수 있다. 리니어 방식과 non 리니어 방식이 있는데, 리니어에는 linked list, 스택, 큐 등의 방법이 존재하며, non 리니어에는 트리와 그래프 등의 방식이 존재한다. 논리니어는 시험범위가 아니기에 아직 설명을 할 수는 없고, 우선 리니어 방식의 자료구조에 대해 알아보겠다. 위의 주제 중 스택과 큐, 덱에 관한 글은 문제풀이를 하며 설명을 잠깐 한 적이 있으므로, 이번 시간에는 링크드리스트에 대해 알아보고자 한다. 흔히 리스트를 이..
2022. 4. 17.
백준 알고리즘 10866번 덱(파이썬, python)
이번 시간에는 스택과 큐에 이어, 덱을 배워보려고 한다. 덱의 개념은 스택과 큐를 합친것과 유사한데, 왜냐하면 push와 pop을 하는 부분이 각 끝단에 하나씩 위치하기 때문이다. 이게 무슨말이냐면, 앞과 뒤에 pushfront, pushback을 통해서 각각 대입할 수 있고, popfrront와 popback을 통해 각각 소거할 수 도 있다. 따라서 이번 덱 구문에서 사용가능한 명령은 pushfront, pushback, popfront, popback, size, empty, front, back 이렇게 여덟가지가 있다. 그러면 이 명령들을 사용해서 한번 코드를 짜보도록 하자. /// import sys num=int(input()) deque=[] for i in range(num): new=sys..
2022. 4. 2.
백준 알고리즘 10845번 큐(파이썬 , Python)
스택문제를 풀어봤으면, 관련된 큐와 덱 문제도 풀어보도록하자. 덱 문제는 스택과 큐를 복합한 개념이라, 다음 글에 또 작성하도록 하겠다. 우선 스택은 프링글스 통과 같이, 넣은 순서의 역순대로 나오는 것이라면, 큐는 넣은 순서대로 나온다. 예를 들어서 1,2,3,4의 순서대로 숫자를 삽입했다면, 나오는 것도 1,2,3,4 번이 순서대로 나온다. 놀이공원에서 놀이기구를 타기 위해 줄을 섰다고 생각하면 될 것 같다. 이에 적용되는 명령은, push, pop, size, empty, front, back 이렇게 존재한다. 우선 식을 적고, 각각 어떠한 역할을 하는지 살펴보도록 하자. /// import sys num=int(input()) que=[] for i in range(num): new=sys.std..
2022. 3. 25.
