🔥 용감하게 시작하는 코딩테스트 3편

🔥 용감하게 시작하는 코딩테스트 3편

0. 무엇을 공부할까요?

혹시 지난 챕터가 쉬웠나요? 그렇다면 다행입니다. 이번 챕처는 문제 풀이 중간 중간에 들어가는! 꼭 기억해야 풀이 시간이 줄어드는 순열, 조합, 빈도계산, 덱, 우선순위 큐에 대해서 알아보겠습니다.

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))

백준 15650번 N과 M (2) 문제를 풀어보겠습니다. N과 M의 숫자가 주어졌을 때 다음 조건을 만족해야 합니다.

- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- 고른 수열은 오름차순이어야 한다.

조건을 보니 딱 조합의 조건이죠? combinations을 이용해서 구해봅시다.

from itertools import combinations  

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

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

▲ 백준 15650번 N과 M (2) 정답코드

문제의 조건이 1부터 N까지 자연수 이기 때문에 arr = [str(i+1) for i in range(N)] 를 이용해서 1부터 N까지 수를 arr에 저장했습니다.

1-3. 순열

백준 15649번 N과 M (1) 문제를 살펴보겠습니다.

- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

순열을 활용하면 문제를 풀 수 있습니다.

from itertools import permutations  

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

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

▲ 백준 15649번 N과 M (1) 정답코드

1-4. 덤

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

from itertools import product

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

from itertools import combinations_with_replacement

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

2. 빈도 계산

모르면 기업 코딩테스트에서 조금 고생하게 되는 부분입니다. 바로 Counter 입니다. 이번에는 바로 예제로 시작해볼까요? 백준 2592번 대표값 입니다.

본 문제에서는 입력으로 들어오는 10개의 정수의 평균과 최빈값을 구해야합니다. 평균은 `sum(arr) // 10` 을 구하면 되니 넘어가고, 최빈값은

from collections import Counter  

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

▲ 백준 2592번 대표값 정답코드

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

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

Counter를 처음 사용하려면 어색합니다. 백준 1157번 단어공부를 연습문제로 남겨두겠습니다.

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     5 
 / \   / 
4   8 7

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

print(len(heap))
>> 5

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

heapq.heappop(heap)

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

[3, 5, 10, 8]

heappop()을 수행하면 3이 0번 인덱스에 위치하게 됩니다.

그렇다면 최대힙은 어떻게 구현하면 될까요? 백준 11279번 최대 힙 문제를 보겠습니다.

import sys, heapq  
heap = []  

for i in range(int(sys.stdin.readline())):  
    N = int(sys.stdin.readline()) * -1  
  if N == 0:  
        if len(heap) == 0:  
            print(0)  
        else:  
            print(heapq.heappop(heap) * -1)  
    else:  
        heapq.heappush(heap, N)

▲ 백준 11279번 최대 힙 정답코드

입력이 최대 10만이 들어올 수 있으므로 입력 가속을 하는게 좋습니다. (챕터 1 참고) N = int(sys.stdin.readline()) * -1 이렇게 입력되는 값에 -1을 곱하여 최대 힙을 구현할 수 있습니다.

힙 공부를 마치며 다음 문제를 추천합니다.

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

4. 덱

덱은 데크 라고도 하며 double-ended queue의 약자입니다. 선입선출의 개념인 FIFO와 더불어 나중에 온 값을 먼저 처리하는 LIFO 연산도 가능합니다. 즉 양방향에서 데이터를 처리할 수 있습니다. 제가 처음 파이썬을 공부했던 2017년에 파이썬으로 자료구조를 어떻게 구현하는지 궁금해서 당시 출간되지 얼마 안됬던 파이썬 자료구조책을 보았습니다. 그 책에서는 list를 이용해서 스택을 구현했습니다. C 언어만 알던 저에게 list로 스택을 구현한다는 사실은 너무나 충격적이어서 블로그에 포스팅하기도 했습니다.(지금은 내렸지만.. 하하) 그 경험을 살려서 알고리즘 문제를 풀 때 list를 이용해서 스택문제를 풀었는데 이게 왼걸.. 시간초과가 나는 것입니다. 그 이유는 파이썬 공식 래퍼런스에 나와있습니다. fast fixed-length operations 참고. python 래퍼런스 collections.deque 즉 파이썬으로 스택 문제를 풀려면 deque를 사용해야합니다.

from collections import deque 
deq = 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(deq) 

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

print(deQ) 

덱에 있는 값을 출력하려면 print()를 사용하면 됩니다. 콘솔에 [1, 2, 3, 4] 가 출력됩니다.

> deq.rotate(-1) # 음수이면 왼쪽으로 회전 

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

from collections import deque  

 N = int(input())  
card_deque = deque([i for i in range(1, N + 1)])  
while len(card_deque) != 1:  
    card_deque.popleft()  
    card_deque.rotate(-1)  

print(card_deque[0])

▲ 백준 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가 제거됩니다.

99. 덤

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

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 단위로 출력해줍니다.