1. Set

  • 백준 1107번(리모컨) 문제를 풀 때 유용하게 사용
  • 해당 문제는 특정 길이의 문자열에 대해 가능한 모든 조합을 탐색해야 하는데
    시간복잡도를 줄이기 위해 중복이 없는 집합을 사용
  • 빈집합은 set() 명령어로 간단하게 정의
  • Set은 Dictionary와 동일한 Hash Table 기반이기 때문에
    x in s 연산의 시간복잡도가 O(1)
    리스트의 x in s 연산 시간복잡도가 O(n)인 것과는 큰 차이

Set을 응용해 작성한 코드 일부

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

buttons = set([str(i) for i in range(10)])
channels = {N,}
diff = {abs(int_N-100)}
if M > 0:
    buttons -= set(list(input().split()))
    channels = set()
    for i in range(1, count+1):
        product = itertools.product(buttons, repeat=i)
        channels |= set(map(''.join, product))

    min_chan, max_chan = '0', '1'
    for _ in range(count-1):
        min_chan += max(buttons)
    for _ in range(count):
        max_chan += min(buttons)
    if set(max_chan) & buttons == set(max_chan):
        channels.add(max_chan)
    if set(min_chan) & buttons == set(min_chan):
        channels.add(min_chan)

2. Dictionary

  • 백준 1620번(나는야 포켓몬 마스터 이다솜) 문제를 풀 때 사용
  • 해당 문제는 문자열 또는 인덱스를 입력했을 때 대칭되는 값을 출력해야 하는데
    처음엔 시간복잡도가 O(n)인 List의 index(x)를 사용하여 시간초과가 발생
  • 문자열과 인덱스의 관계를 Dictionary로 구현해 탐색 시간복잡도를 O(1)로 개선

3. Coutner

  • 백준 10816번(숫자카드 2) 문제를 풀 때 사용
  • 해당 문제는 숫자 카드의 값을 입력했을 때 해당 카드의 개수를 출력해야 하는데
    처음엔 시간복잡도가 O(n)인 List의 count(x)를 사용하여 시간초과가 발생
  • 전체 카드에 대한 Counter를 정의하여 탐색 시간복잡도를 O(1)로 개선

4. Combination

  • 백준 1010번(다리 놓기) 문제를 풀 때 사용
  • 해당 문제는 강에 다리를 놓는 경우의 수를 출력해야 하는데
    math 모듈의 comb 함수를 이용해 경우의 수를 계산

5. Permutation

  • 백준 1107번(리모컨) 문제를 풀 때 유용하게 사용
  • 해당 문제에서 특정 길이의 문자열에 대해 가능한 모든 조합을 나열하는데,
    순서를 고려하고 중복을 허용하기 위해 중복 순열(Product)을 사용

Permutation을 응용해 작성한 코드 일부

1
2
3
4
5

buttons = set([str(i) for i in range(10)])
...
for i in range(1, count+1):
        product = itertools.product(buttons, repeat=i)
        channels |= set(map(''.join, product))

6. Binary Search

  • 백준 1654번(랜선 자르기) 문제를 풀 때 유용하게 사용
  • 해당 문제는 서로 다른 길이의 선들을 동일한 길이로 가장 길게 잘라야 되는데
    처음엔 가장 긴 선부터 가장 짧은 선까지의 범위 내에서 완전탐색을 진행하여 시간초과가 발생
  • 완전탐색을 이분탐색으로 대체하여 시간복잡도 개선

Binary Search를 응용해 작성한 코드 일부

1
2
3
4
5
6
7
8
9

while mn < mx:
    md = (mx + mn) // 2
    count = 0
    for i in range(K):
        count += k[i] // md
    if count < N:
        mx = md
    else:
        mn = md + 1

7. Heap

  • 백준 7662번(이중 우선순위 큐) 문제를 풀 때 유용하게 사용
  • 해당 문제는 최솟값과 최댓값 삭제 기능을 모두 가지고 있는 이중 우선순위 큐를 구현하는 것
  1. 처음엔 List의 pop(x), index(x), max(x)/min(x)를 혼합하여 사용한 것 때문에
    O(n^3) 이상의 시간복잡도를 만들어서 시간초과가 발생
  2. 두번째 시도에선 List의 pop(x)와 heapq 모듈의 heappop(x)를 사용해 시간복잡도를 O(1()로 개선
    하지만, Heap은 이진트리 기반으로 리스트와는 구조가 다르기 때문에 인덱스로 참조 시 에러가 발생
  3. 세번째 시도에선 단일 큐를 Max Heap과 Min Heap으로 나누고 각각에서 heappop(x), heappush(x)를 수행
    하지만, Max Heap 또는 Min Heap에서 삭제된 값이 반대쪽 Heap에서 남아있는 경우가 있어 에러가 발생
  4. 해당 에러에 대한 해결책으로 Max Heap과 Min Heap을 동기화를 시키는 방법도 있지만,
    값이 유효한지 판단하는 Dictionary를 구현해 값에 대한 참/거짓 여부를 참조하는 방법을 이용
    해당 Dictionary를 heappop(x) 사용 시 한 번, 최대/최솟값 출력 시 한 번씩 참조해 에러 해결

Heap을 응용해 작성한 코드 일부

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

if cmd == 'I':
    n = int(n)
    heapq.heappush(min_Q, n)
    heapq.heappush(max_Q, -n)
    try:
        valid[n] += 1
    except KeyError:
        valid[n] = 1
    ins += 1
elif cmd == 'D':
    try:
        if n == '1':
            max_pop = -heapq.heappop(max_Q)
            while not valid[max_pop]:
                max_pop = -heapq.heappop(max_Q)
            valid[max_pop] -= 1
            ins -= 1
        elif n == '-1':
            min_pop = heapq.heappop(min_Q)
            while not valid[min_pop]:
                min_pop = heapq.heappop(min_Q)
            valid[min_pop] -= 1
            ins -= 1
    except IndexError:
        min_Q, max_Q = [], []
        continue

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

max_pop, min_pop = 0, 0
while True:
    max_pop = -heapq.heappop(max_Q)
    if valid[max_pop]:
        break
while True:
    min_pop = heapq.heappop(min_Q)
    if valid[min_pop]:
        break
print(max_pop, min_pop)

8. DFS/BFS

  • 백준 1260번(DFS와 BFS) 문제를 풀 때 사용
  • 해당 문제는 DFS와 BFS로 탐색했을 때의 결과를 출력하는 기본적인 문제
  • DFS는 깊이를 우선적으로 탐색, BFS는 너비를 우선적으로 탐색
  • DFS는 경로의 특징을 저장할 때 사용, BFS는 최단거리를 구할 때 사용
  • DFS는 스택 또는 재귀함수로 구현, BFS는 큐(데크)를 이용해서 구현

DFS/BFS를 응용해 작성한 코드 일부

1
2
3
4
5
6
7
8
9

def dfs(nodes, visited, node):
    visited[node] = True

    next_nodes = nodes[node]
    while next_nodes:
        next_node = heapq.heappop(next_nodes)
        if not visited[next_node]:
            print(next_node, end=' ')
            dfs(nodes, visited, next_node)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def bfs(nodes, visited, root):
    queue = deque()
    visited[root] = True
    queue.append(root)

    while queue:
        node = queue.popleft()
        visited[node] = True
        print(node, end=' ')

        next_nodes = nodes[node]
        while next_nodes:
            next_node = heapq.heappop(next_nodes)
            if not visited[next_node]:
                visited[next_node] = True
                queue.append(next_node)