코딩테스트 준비 3편

해당 게시글은 https://covenant.tistory.com/143 을 참고하여 작성했습니다.

 

이번 챕터는 문제 풀이 중간 중간에 들어가는 꼭 ! 기억해야 풀이 시간이 줄어드는 순열, 조합, 빈도계산, 덱, 우선순위 큐에 대해 알아보겠습니다. 

 

1. 순열, 조합

1-1. 순수한 방법

for문 2개를 사용해서 nC2를 구하는 방법은 다음과 같습니다.

for i in range(0, N-1): 
    for j in range(i+1, N): 
        print(i, j)

 

백준 9613번 GCD 합 문제를 풀 수 있습니다. GCD는 다음 챕터에서 살펴볼 것입니다.
그렇다면 nC3은? nC4는...? for문을 사용해서는 한계가 있습니다.

 

1-2. itertools을 사용한 조합

from itertools import combinations
print(list(combinations([1, 2, 3, 4], 3)))

 

combinations의 첫 번째 인자에 배열을 넣고, 두 번째 인자에는 nCm 이라면 m에 해당하는 값을 넣습니다. 출력 결과는 다음과 같습니다.

[(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)]

 

위에서 본 순수한 방법을 combinations를 사용하면 다음과 같이 표현할 수 있습니다.

list(combinations([0, 1, 2, 3], 2))

 

 

1-3. 순열

백준 15649번 N과 M (1) 문제를 살펴보겠습니다. 순열을 활용하면 문제를 풀 수 있습니다.

from itertools import permutations

N, M = map(int, input().split())
arr = [str(i) for i in range(1, N+1)]

for e in list(permutations(arr, M)):  
    print(" ".join(e))

 

1-4. 덤

중복 순열은 다음과 같이 사용합니다.

from itertools import product

 

중복 조합은 다음과 같이 사용합니다.

from itertools import combinations_with_replacement

 

하지만 입사를 위한 코딩테스트에서 중복 순열, 중복 조합을 사용해야만 문제가 풀리는 경우는 없습니다 ! itertools에는 순열과 조합 말고 다양한게 있구나 하고 넘어가시면 됩니다. 

 

 

2. 빈도 계산

모르면 기업 코딩테스트에서 조금 고생하게 되는 부분입니다. 바로 Counter 입니다. 이번에는 바로 예제로 시작해볼까요 ? 백준 2592번 대표값 입니다. 본 문제에서는 입력으로 들어오는 10개의 정수의 평균과 최빈값을 구해야 합니다. 평균은 sum(arr) // 10을 구하면 되니 넘어가고, 최빈값은 Counter().most_common()과 같이 구합니다.

from collections import Counter 

arr = [int(input()) for _ in range(10)]
val = Counter(arr).most_common()
print(sum(arr) // 10)
print(val[0][0])

[(30, 3), (40, 2), (60, 2), (10, 1), (20, 1), (50, 1)]

 

Counter(arr).most_common()을 수행했을 때 결과는 위와 같습니다. 리스트 안에 튜플이 있습니다. 튜플의 0번째 인덱스에는 arr의 숫자, 1번째 인덱스에는 arr 등장 빈도수가 들어 있습니다.

 

 

3. 힙

3-1. 최소힙, 최대힙

파이썬에서는 최소힙으로 구현되어 있습니다. 최소힙을 사용해서 저장하면 저장된 값 중 최솟값이 0번 인덱스, 즉 이진트리의 루트에 위치합니다.

import heapq
 
heap = []  
heapq.heappush(heap, 3)  
heapq.heappush(heap, 1)  
heapq.heappush(heap, 10)  
heapq.heappush(heap, 5)  
heapq.heappush(heap, 8)

 

파이썬에서 힙을 사용해서 3, 1, 10, 5, 8을 각각 힙에 넣었습니다. 출력을 해보면 다음과 같습니다.

[1, 3, 10, 5, 8]

 

     1 <--- Root 
   /   \ 
  3     10 
 / \   
5  8

 

힙에 위와 같이 저장되어 있습니다. 이진 트리의 루트에는 가장 작은 값이 저장되는 것을 확인할 수 있습니다. 

print(len(heap))
>> 5

 

힙의 길이는 리스트, 덱과 동일하게 len()을 이용합니다.

 

heapq.heappop(heap)

 

힙의 루트 원소를 제거하려면 heappop()을 이용합니다. 이 때 pop되는 값이 리턴됩니다.

import sys, heapq
heap = []

# 입력이 최대 10만이 들어올 수 있으므로 입력 가속을 하는게 좋습니다.
for i in range(int(sys.stdin.readline())):
    x = int(sys.stdin.readline()) * -1
    # 입력되는 값에 -1을 곱하여 최대힙을 구현할 수 있습니다

    if x == 0:
        # 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거
        if len(heap) == 0:
            print(0) # 비어있는 경우인데 가장 큰 값을 출력하라고 한 경우
        else:
            print(heapq.heappop(heap) * -1)

    else: # 배열에 x 값을 삽입하는 연산
        heapq.heappush(heap, x)

 

heapq를 사용하게 되면 최소힙을 구현하게 됩니다. 따라서 최대힙과는 다른 방식입니다. 그래서 음수 값을 사용해서 우선순위를 이용하여 최대힙처럼 응용한 것입니다. 최소힙의 원리를 이용하여 최대힙을 구현할 수 있습니다. 힙 공부를 마치며 다음 문제를 추천합니다.

• 백준 1927번 최소 힙
• 백준 11286번 절댓값 힙

4. 덱

덱은 데크라도고 하며 double-ended queue의 약자입니다. 선입선출의 개념인 FIFO와 더불어 나중에 온 값을 먼저 처리하는 LIFO 연산도 가능합니다. 즉, 양방향에서 데이터를 처리할 수 있습니다. collections.deque 즉 파이썬으로 stack 문제를 풀려면 deque를 사용해야 합니다. 

from collections import deque 
deque = deque() # 덱 초기화

 

덱을 사용하는 방법은 위와 같습니다.

deq = deque([i for i in range(1, 5)])

 

deq에는 [1, 2, 3, 4]가 저장됩니다.

deq.appendleft(10)

 

덱의 왼쪽에 값을 추가하려면 .appendleft(value)를 하면 됩니다. 실행을 마치면 덱에는 [10, 1, 2, 3, 4]가 저장됩니다.

deq.append(-10)

 

덱의 오른쪽에 값을 추가하려면 .append(value)를 씁니다. 덱에는 [10, 1, 2, 3, 4, -10]이 저장됩니다.

 

print(deq.pop())

 

덱의 오른쪽에서 값을 제거하려면 .pop()을 씁니다. pop되는 값이 리턴되며 비어있는 덱인 경우 indexError: pop from an empty deque 문구를 만날 수 있습니다. 따라서 빈 덱에 pop을 수행하는지 유의해야 합니다.

print(deq.popleft())

 

덱의 왼쪽에서 값을 제거하려면 .popleft()를 씁니다. 역시 pop되는 값이 리턴되며 비어있는 덱이면 오류를 만납니다.

len(dep)

 

덱의 길이를 구하는 방법은 리스트와 동일하게 len()을 사용합니다. 

deq.rotate(-1)

 

덱을 회전하는 방법이 있습니다. .rotate를 이용하면 됩니다. 인자로 들어간 값만큼 회전하며, 음수이면 좌측으로 회전합니다. .rotate를 활용해서 백준 2164번 카드2 문제를 풀어보세요. 

기본 덱 사용법을 살펴보았습니다. 다음 문제를 추천합니다. 

• 백준 10866번 덱
• 백준 10828번 스택
• 백준 1158번 요세푸스

 

5. 우선순위 큐

우선순위 큐는 기업 코딩테스트에 자주 나오지 않습니다. 하지만 한 번 언급하고 넘어가겠습니다.

from queue import PriorityQueue
que = PriorityQueue()

 

위와 같이 우선순위 큐를 만들 수 있습니다.

que.put(4)
que.put(10)
que.put(2)

for i in range(len(que.queue)):  
    print(que.queue[i], end=" ")

 

.put()을 이용하여 우선순위 큐에 값을 넣습니다. .append()가 아니니 유의하세요 !

2 10 4

 

출력 결과는 위와 같습니다.

que.get()

 

우선순위 큐에 저장된 값은 .get()을 이용해서 제거합니다. 제거한 값이 리턴됩니다. 본 예제에서는 2가 제거됩니다. 

 

 

* 덤

문제를 풀다보면 실행시간을 알고 싶을 때가 있습니다. 이럴 때 다음과 같이 구현해주세요.

import time
start_time = int(round(time.time() * 1000))
some_func()
end_time = int(round(time.time() * 1000))
print('some_func()의 실행시간 : %d(ms)' % (end_time - start_time))

 

some_func()가 실행 시간을 ms 단위로 출력해줍니다.