Redddy's Devlog

우선순위 큐는 내부적으로 힙(heap)이라는 완전이진트리 Complete binary Tree로 되어 있다. 힙 트리의 루트 노드(root node)에는 데이터들 중에 가장 큰 값 혹은 가장 작은 값을 담게 되는데, 전자는 최대힙(max-heap), 후자는 최소힙(min-heap)이라 한다. 어떤 값을 넣어도 항상 루트에 가장 큰 값 또는 가장 작은 값이 위치하도록 자동으로 갱신한다. 이 과정이 꽤 효율적이라 우선순위 큐의 값 삽입/삭제 시간 복잡도는 O(log N)이다. 무작위 숫자들을 힙에 전부 넣고 하나씩 빼면 정렬된 결과를 얻을 수 있는데, 이게 힙정렬이다. from queue import PriorityQueue pq = PriorityQueue() pq.put(123) pq.put(789) p..

Queue는 스택과 상반된 특징을 띄고 있는 자료구조이다. 둘 다 선형 자료구조이지만, 데이터 입출 순서가 달라지는 부분이 있다. 큐에는 데이터를 넣은 순서 그대로 빼게 된다. 첫 번째로 넣은 데이터가 첫 번째로 빠지며 이를 FIFO라 한다. 큐에 데이터를 넣고 뺄 때 시간 복잡도는 O(1)이므로 N개의 데이터를 넣고 빼야 한다면 총 O(N)이 될 것이다. from queue import Queue q = Queue() q.put(123) q.put(456) q.put(789) while not q.empty(): print(q.get()) 이렇게 import 해서 사용하면 된다. 위 코드에서 대문자 Q로 시작하는 Queue 모듈은 멀티스레딩 환경까지 고려해서 스레드 간에 안전한 방식으로 동작하는 모듈이..

Stack은 '쌓다', '무언가가 쌓여 있는 더미' 등을 의미한다. 스택은 의미 그대로 어떤 데이터를 삽입/삭제하는 과정을 '쌓는' 형태로 나타낼 수 있는 자료구조이다. 스택의 특징은 FILO (First In Last Out) 즉 먼저 저장된 데이터가 가장 나중에 나가는 방식으로 저장된다. 이름에서 힌트를 준것처럼 데이터가 차례대로 쌓인다. 가장 나중에 들어온 데이터는 먼저 나간다 LIFO (Last In First Out). 풜스트인풜스트 아웃 이말은 전에 TV 프로그램을 보다가 소방관 얘기가 나왔을 때 먼저 접했던 것 같다. 자료구조 얘기 하다가 뭔 소방관 얘기냐? 할 수 있겠는데 소방관들이 화재 현장을 들어 갈 때 FILO을 한다고 한다. 즉 먼저 들어가서 구조를 하고 끝까지 현장에 남아서 구조를..

파이썬은 다른 언어들과는 달리 다른 자료형을 담을 수 있는 리스트를 갖고 있다. 하지만 이러한 능력때문에 한가지 주의할 점이 있다. # Python a1 = [[0] * 5] * 3 a1[1][1] = 99 # [1][1] 외에 다른 곳의 값도 99로 출력됨 print(a1) a2 = [[0] * 5 for i in range(3)] a2[1][1] = 99 print(a2) # 의도대로 작동 됨 a1을 실행하면 한군대만 99로 변환되는게 아니라 총 3군데가 99로 변환된다. 반면, 리스트 컴프리헨션을 사용한 a2는 의도한 대로 작동한다. 다차원 배열을 만들 때는 반드시 a2와 같은 방식으로 만들어야 하는데, 그 이유는 위에서 소개한 리스트 구조와 관련이 있다. a1과 같이 만들면 메모리 주소값들이 복사..

요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 예제 입력 예제 출력 7 3 문제 풀이 import sys input..

컴퓨터는 기본적으로 2진법을 사용한다. 2진법이란 0과 1로 모든 숫자를 표현하는 것이다. 우리가 평소에 사용하는 진법은 0부터 9까지 사용하는 10진법이다. 하지만 주위에 12진법 또는 60진법도 눈에 띈다. 시간에서 hour가 12진법, minute 이 60진법이다. 이제 코딩에서 진법을 변환하는 방법을 알아보자. 2진수 : 0b 8진수 : 0o 16진수 : 0x 이렇게 접두사가 붙는다. a = int(100, 2) 이것은 2진수인 100을 10진수로 바꾼다는 의미이다. a를 출력해보면 4가 출력된다. a = int(100, 8) 이는 8진수 100을 10진수로 바꾼다는 뜻이다. a를 출력해보면 64가 출력된다. format(a, 'b') 이것은 10진수 a를 2진수로 바꾼다는 의미이다. b를 o로 ..