시간복잡도 Big-oh (big-o) notation 점근 표기법
알고리즘에 대해 공부하다보면, 처음부터 볼 수 있는 개념이 하나 있다. 그것은 바로 시간복잡도이다. 현재 글을 적는 시점에서도, 나도 가끔 가다가 빅오표기법의 계산을 잘못하여 효율성을 잘못 따질때가 있다. 오늘은 이 시간복잡도에 대해서 알아보고자 한다. 모든 동작에는, 시간과 메모리가 필요로 한다. 이 중 시간복잡도는 프로그램을 실행할 때 소요되는 시간을 계산하는것이다. 구문, 함수의 종류 등에 의해 다양한 공식을 띄게 되는데, 크게 아래의 사진과 같은 방식으로 분류된다. O(1), O(logn), O(n), O(n!) 등과 같은 방식이 존재하며, 위의 방식 이외에 적힌 식에 따라 O(n^5) 등 다양한 파생된 결과가 출력될 수 있다. X축은 투입되는 자료의 갯수, Y축은 그 자료들을 투입한 프로그램의 ..
2022. 4. 28.
백준 알고리즘 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.