Review 1 - 자료구조 기본/정렬/Greedy/정수론

Ⅰ. 자료구조 기본

1. Stack, Queue, Deque

Stack, Queue, Deque는 말 그대로 기본 자료구조인만큼 리뷰할만한 내용이 거의 없다. 아래의 두 가지 내용만 잘 알아두고 있어도 충분한 것 같다.

① Deque의 import 문

from collections import deque 

② Deque의 길이

deq = deque()
len(deq) # 기존 리스트의 길이와 동일

2. Tree

1) 이진 탐색

① 코드

def binary_search(lst, target):
	start = 0
    end = len(lst) - 1
    while start <= end:
    	mid = (start + end) // 2 # 소수점 이하 버림
        if lst[mid] == target:
        	return mid
        elif lst[mid] < target:
        	start = mid + 1
        else:
        	end = mid - 1
            
    return -1

② 주의 사항

• 반드시 리스트를 정렬한 후에 이진 탐색을 진행해야 한다.
• 분기문에서 lst[mid] == target이 아닌, mid == target과 같이 쓰지 않도록 주의한다.

2) BFS/DFS

① BFS/DFS를 수행하기 위해 저장해야 하는 정보

• 그래프(트리) 표현
  • 인접 리스트 또는 인접 행렬 사용
  • 양반향 간선을 고려
• visited 배열

② BFS와 DFS 구현 코드

• Deque 또는 Stack에 append 된(재귀 호출 된) 직후에 visited 배열을 업데이트 해주어야 한다.
• BFS와 DFS 모두 다음 노드를 선택하는 조건은 "인접 노드 중 방문하지 않은 노드"이다.

def BFS(V):
    deq = deque()
    deq.append(V)
    visited1[V] = 1 # append 시점 직후에 visited 배열 업데이트
    
    while deq:
        V = deq.popleft()
        for i in tree[V]: # 인접 노드 중
            if visited1[i] == 0: # 방문하지 않은 노드
                deq.append(i) 
                visited1[i] = 1 # append 시점 직후에 visited 배열 업데이트
                
def DFS(V):
    visited2[V] = 1 # 재귀 호출 된 직후에 visited 배열 업데이트
    for i in tree[V]: # 인접 노드 중
        if visited2[i] == 0: # 방문하지 않은 노드
            dfs(i)

③ 방문할 수 있는 정점이 여러 개일 때, 정점 번호가 작은 것을 먼저 방문해야 하는 조건이 있는 경우

• 인접 행렬을 이용한 풀이에서는 저절로 위 조건을 만족하게 된다.
• 인접 리스트로 풀이하는 경우에는, 각 노드의 인접 노드를 오름차순으로 정렬해주어야 한다.

# 정점 번호가 1부터 시작한다고 가정
tree = [[] for i in range(N + 1)]

for i in range(E): # 간선 개수만큼 반복
    u, v = map(int, input().split()) # 연결된 두 정점
    tree[u].append(v) # 양방향 간선
    tree[v].append(u)
    
for i in range(1, N + 1): # 각 노드의 인접 노드를 오름차순으로 정렬
    tree[i].sort()

④ DFS에서 현재 노드의 깊이를 알아야 하는 경우

• 현재 노드의 깊이를 메서드의 입력 인자로 받으면 된다.

def DFS(V, depth):
    visited[V] = 1 # 재귀 호출 된 직후에 visited 배열 업데이트
    print(depth)

    for i in tree[V]: # 인접 노드 중
        if visited[i] == 0: # 방문하지 않은 노드
            dfs(i, depth + 1)

3) Tree Traversal

① 딕셔너리를 이용한 트리 표현

• 부모 노드를 Key로, [L_Child, R_Child] 배열을 Value로 사용

② 재귀 호출을 이용한 구현

Ⅱ. 정렬 알고리즘

정렬 알고리즘 자체를 구현하는 문제는 나오지 않기 때문에, 편하게 읽고 넘어갈 수 있을만한 부분이다. 아래의 내용만 간단히 확인해도 충분할 것 같다.

① Bubble Sort

• 버블 정렬의 내부 루프(2차 루프)에서 Swap이 한번도 일어나지 않았다면, 이는 이미 정렬이 완료된 상태임을 의미한다.
• 버블 정렬이 완료되기 위해 필요한 (외부) 루프의 횟수는 각 원소가 왼쪽으로(앞으로) 이동한 횟수의 최대 값과 같다. 여기서 왼쪽으로 이동한 횟수는, 정렬 전 Index에서 정렬 후 Index를 빼는 것으로 구할 수 있다.

② Counting Sort

• 정수의 정렬 결과를 출력하는 문제 중 sort() 메서드 사용 시 시간 초과 또는 메모리 초과가 발생하는 문제에서 사용한다.
• 숫자의 범위만큼의 크기를 갖는 배열을 만들고, 주어지는 숫자에 해당하는 인덱스의 값을 1씩 증가시킨다. 이후 배열을 순회하면서 원소가 0이 아닌 인덱스를 원소만큼 반복 출력하면 자연히 정렬된 결과를 얻게 된다.
• 입력 값의 범위가 작은 정수를 정렬하는 데에 유리하다.

Ⅲ. Greedy 알고리즘

① 최적해 보장 조건

• 모든 원소들이 서로 배수 관계에 놓여있어야 한다.

② 우선순위 큐

• import 문

from queue import PriorityQueue

• put(), get(), empty(), qsize() 메서드를 사용할 수 있다.
• put으로 우선순위와 아이템을 모두 삽입하는 경우, 반드시 put((우선순위, 아이템))과 같이 튜플을 전달해야 한다. put(우선순위, 아이템)의 형태로 사용하지 않도록 주의한다.
• 우선순위와 아이템이 모두 삽입된 경우, get으로 가져온 값도 (우선순위, 아이템)의 튜플이므로, 인덱싱 연산을 통해 원하는 값을 추출해야 한다.
• 우선순위가 동일한 경우, 아이템의 값이 작은 값을 우선적으로 선택한다.
• queue[0]를 사용하면, 우선순위 큐에 맨 앞에 위치한 원소를 제거 없이 확인할 수 있다.

pq = PriorityQueue() 
pq.put([1, 'apple'])
pq.put([2, 'banana'])
print(pq.queue[0]) # [1, 'apple'] 출력

fruit = pq.get()
name = fruit[1] # 인덱싱 연산을 통해 과일의 이름을 가져온다.
print(name) # apple 출력

Ⅳ. 정수론

1. 에라토스테네스의 체

① 아이디어

• 주어진 정수 범위(N)만큼의 Size를 갖는 배열을 생성한다.
• 2부터 n(N의 제곱근)까지의 모든 배수를 배열에서 지운다(0으로 Overwrite 한다).
• 이미 지워진 원소에 대해, 배수 제거 연산을 생략한다.
• 최종적으로 배열에서 0이 아닌 모든 원소를 순차적으로 출력한다.

② 배열 초기화

• 배열의 0번 인덱스와 1번 인덱스의 원소는 반드시 0이어야 한다.
• 마지막에 0이 아닌 모든 원소를 출력할 것이므로, 배열을 초기화 할 때 주의가 필요하다.

## 잘못된 초기화 ##
lst = []
for i in range(N + 1):
    lst.append(i) # 1번 인덱스의 원소가 1이 되어 마지막에 함께 출력됨
    
## 올바른 초기화 ##
lst = [0] * (N + 1) # 0번 인덱스와 1번 인덱스의 원소를 0으로 초기화
for i in range(2, N + 1):
    lst[i] = i

③ 배수 제거 코드

• n(N의 제곱근)을 구하는 과정에서, n의 값이 정수가 아닐 수도 있기 때문에 반드시 int로 형변환 해주어야 한다.
• j의 시작 값을 i로 설정하지 않도록 주의한다.

for i in range(2, int(N ** 0.5) + 1):
    if lst[i] == 0:
        continue
        
    for j in range(i + i, N + 1, i):
        lst[j] = 0

④ 소수 판별 코드

def isPrime(N):
	if N == 1:
        return False
        
    for i in range(2, int(N ** 0.5) + 1):
        if N % i == 0:
            return False
        
    return True

⑤ 권장 사항

• 에라토스테네스의 체 문제를 풀이하기 전에, 메모리 제약을 먼저 계산해보아야 한다.

2. 오일러 Phi 함수

① 아이디어

• 인덱스를 값으로 갖는 P[N] 배열을 생성한다.
• 2부터 n(N의 제곱근)까지 N의 소인수인 K를 찾고, P[N]의 값에서 N 이하의 K의 배수의 개수를 뺀다. 이 때, N 이하의 K의 배수의 개수는 P[N] // K로 구할 수 있다.
• 위 연산이 완료된 이후 N의 소인수 분해 결과에서 K 항을 제거하기 위해, N을 K의 거듭 제곱으로 나눈다.
• 반복문 종료 이후에 갱신된 N(N')이 1보다 크면 이는 N'이 소수라는 의미이므로, P[N]의 값에서 N 이하의 N'의 배수의 개수를 빼야 한다. 이 때, N'의 배수의 개수도 동일하게 P[N] // N'으로 구할 수 있다.

② 특정 N과 서로소인, N 이하의 자연수의 개수를 구하는 문제

• 오일러 Phi는 다소 복잡한 알고리즘이기 때문에, P[N] 배열 전체를 구하는 문제보다는, P[N]의 값을 구하는 문제가 출제될 가능성이 더 높다.
• 이 문제에서는 소수 K를 찾는 일이 매우 간단해진다. 아래의 코드만 작성하면, 소인수 분해의 원리에 의해, 항상 소수인 K 값만 조건식을 만족하게 된다.

result = N # P[N]의 값

for K in range(2, int(N ** 0.5) + 1):

    # 단순히 K가 N의 약수인지를 검사하는 식이지만, 소인수 분해의 원리에 의해 K는 항상 소수가 됨.
    if N % K == 0:
        result -= result // K # N에서 K의 배수의 개수만큼 뺌.

        while N % K == 0: # N 값 갱신
            N //= K
            
if N > 1: # 갱신된 N이 소수
    result -= result // N # N이 소수이므로, 위 식에 K 대신 N을 대입