대기업 코딩테스트 준비 1: 고난이도 알고리즘 정리

ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com)

• 계속 추가 예정

최소 공통 조상 (LCA)

• 두 노드의 공통된 조상 중에 가장 가까운 조상 찾기
  • 노드의 깊이가 n일 때 n*log(n)개의 공간을 이용해 시간복잡도를 O(MlogN) M은 쿼리 갯수, N은 노드 갯수

1. DFS로 모든 노드 깊이를 계산함
2. 두 노드의 깊이를 맞춤
   1. 깊은 놈 부모로 가서 노드 깊이 맞춤
   2. 한칸씩 올라가며 찾는다.

최소공통조상 1

도약 높이는 점점 짧아진다.(8,4,2,1)

 

import sys
input = sys.stdin.readline # 시간 초과를 피하기 위한 빠른 입력 함수
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정
LOG = 21 # 2^20 = 1,000,000

# 시간복잡도 O(MlogN)
n = int(input())
parent = [[0] * LOG for _ in range(n + 1)] # 부모 노드 정보 (logN개)
d = [0] * (n + 1) # 각 노드까지의 깊이
c = [0] * (n + 1) # 각 노드의 깊이가 계산되었는지 여부
graph = [[] for _ in range(n + 1)] # 그래프(graph) 정보

for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
def dfs(x, depth):
    c[x] = True
    d[x] = depth
    for y in graph[x]:
        if c[y]: # 이미 깊이를 구했다면 넘기기
            continue
        parent[y][0] = x
        dfs(y, depth + 1)

# 전체 부모 관계를 설정하는 함수
def set_parent():
    dfs(1, 0) # 루트 노드는 1번 노드
    for i in range(1, LOG):
        for j in range(1, n + 1):
            # 위로 높이 2^i부모 == 2^i-1부모의 높이 2^i-1위에 있음 (높이는 합이다.)
            parent[j][i] = parent[parent[j][i - 1]][i - 1]

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # b가 더 깊도록 설정
    if d[a] > d[b]:
        a, b = b, a
    # 먼저 깊이(depth)가 동일하도록
    for i in range(LOG - 1, -1, -1):
        if d[b] - d[a] >= (1 << i): # 위에서부터 낮추어준다.
            b = parent[b][i]
    # 부모가 같아지도록
    if a == b:
        return a;
    for i in range(LOG - 1, -1, -1):
        # 조상을 향해 거슬러 올라가기
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]
    # 이후에 부모가 찾고자 하는 조상
    return parent[a][0]

set_parent()

m = int(input())

for i in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))

바이너리 인덱스 트리 - 세그먼트 트리 - 팬웍 트리

• 구간 합을 구하려는 array가 자주 바뀌는 경우

세그먼트트리

예시
# i -= (i & -i)
7  0111
-7 1001 (2의 보수 - 자릿수 하나 올라가야 함)
> 6
6  0110
-6 1010
> 4
4  0100
-4 0100
0 # 끝 - 0은 안씁니다.
즉 4에 저장된 1~4까지 합
6에 저장된 5~6까지의 합
7 더하고 끝~!

• 인덱스 0 은 종료 조건으로 사용하지 않음

• 2^n은 그 인덱스 까지 합.

• 3 변경 시 logn 만큼 변경

• 합 구할 시 logn만큼 합 구함

처음 만드는 구조

import sys
input = sys.stdin.readline

# 0이 아닌 마지막 비트를 찾아가는 기준으로 업데이트
# 데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k)
n, m, k = map(int, input().split())

# 전체 데이터의 개수는 최대 1,000,000개
arr = [0] * (n + 1)
# 바이너리 인덱스 트리
tree = [0] * (n + 1)

# i번째 수까지의 누적 합을 계산하는 함수
def prefix_sum(i):
    result = 0
    while i > 0:
        result += tree[i]
        # 0이 아닌 마지막 비트만큼 빼가면서 이동
        i -= (i & -i)
    return result

# i번째 수를 dif만큼 더하는 함수
def update(i, dif):
    while i <= n:
        tree[i] += dif
        i += (i & -i)

# start부터 end까지의 구간 합을 계산하는 함수
def interval_sum(start, end):
    return prefix_sum(end) - prefix_sum(start - 1)

# 배열의 해당 인덱스에 데이터를 삽입하며 트리를 만든다.
for i in range(1, n + 1):
    x = int(input())
    arr[i] = x
    update(i, x)

for i in range(m + k):
    a, b, c = map(int, input().split())
    # 업데이트(update) 연산인 경우
    if a == 1:
        update(b, c - arr[b]) # 바뀐 크기(dif)만큼 적용
        arr[b] = c
    # 구간 합(interval sum) 연산인 경우
    else:
        print(interval_sum(b, c))

벨만 포드

• 음수 간선이 포함된 상황에서의 최단 거리 문제
  • 다음 과정을 N-1번 반복
    • 전체 간선 E 하나씩 확인
    • 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
  • N번째에도 업데이트 되면 순환 존재
  • 다익스트라 최적해 포함
• O(VE)
• 모든 간선 비용이 양수이면
  • 다익스트라
    • 음수 사이클 없으면 써도됨
  • 플로이드와샬
    • 모두에서 모두

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 모든 간선에 대한 정보를 담는 리스트 만들기
edges = []
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    edges.append((a, b, c))

def bf(start):
    # 시작 노드에 대해서 초기화
    distance[start] = 0
    # 전체 n - 1번의 라운드(round)를 반복
    # 트리 n개 노드 엣지 최대 n-1 ... 한 개 씩 연결
    # n번째도 갱신되면? 사이클 존재 불가능.
    for i in range(n):
        # 매 반복마다 "모든 간선"을 확인하며
        # 한 걸음 한 걸음 전진함
        # 다익스트라는 정점에 붙어있는 간선만 확인함
        # 벨만 포드는 모든 간선을 체크함
        for j in range(m):
            cur_node = edges[j][0]
            next_node = edges[j][1]
            edge_cost = edges[j][2]
            # 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if distance[cur_node] != INF and distance[next_node] > distance[cur_node] + edge_cost:
                distance[next_node] = distance[cur_node] + edge_cost
                # n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
                if i == n - 1:
                    return True
    return False

# 벨만 포드 알고리즘을 수행
negative_cycle = bf(1) # 1번 노드가 시작 노드

if negative_cycle:
    print("-1")
else:
    # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단 거리를 출력
    for i in range(2, n + 1):
        # 도달할 수 없는 경우, -1을 출력
        if distance[i] == INF:
            print("-1")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(distance[i])

소수 판별

단 하나의 숫자

# O(N^1/2)
import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x의 제곱근까지의 모든 수를 확인하며
    for i in range(2, int(math.sqrt(x)) + 1):
        # x가 해당 수로 나누어떨어진다면
        if x % i == 0:
            return False # 소수가 아님
    return True # 소수임

여러개의 수가 소수인지 아닌지 판별

• 에라토스테네스의 체
• NloglogN

import math

n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별
array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화

# 에라토스테네스의 체 알고리즘 
for i in range(2, int(math.sqrt(n)) + 1): # 2부터 n의 제곱근까지의 모든 수를 확인하며
    if array[i] == True: # i가 소수인 경우 (남은 수인 경우)
        # i를 제외한 i의 모든 배수를 지우기
        j = 2 
        while i * j <= n:
            array[i * j] = False
            j += 1

# 모든 소수 출력
for i in range(2, n + 1):
    if array[i]:
        print(i, end=' ')

개발형 코테

• REST : 각 자원에 대하여 자원의 상태에 대한 정보를 주고 받는 개발 방식\
  • 자원을 HTTP 메소드로 처리
• API : 프로그램 상호 작용 인터페이스
  • 클라이언트와 서버는 각각 프로그램
  • 두 개체의 상호작용 연결
• Rest API
  • 레스트 아키텍처를 따르는 API
  • 레스트 방식을 따르는 서버에 특정한 요청을 보내서 데이터를 가져오는 것
• REST의 구성 요소
  • 자원 (resource): URI를 이용해 표현
  • 행위 (verb) : HTTP 메서드를 이용해 표현
  • 표현 (Representations)
• JSON
  • 주고받는 데이터 표준

투포인터

• 특정한 합을 가지는 부분 연속 순열 찾기
  • 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하며 처리
    1. 시작점과 끝점 index 0 지시
    2. 부분홥이 M과 같다면 카운트
    3. 부분합이 M보다 작으면 end +1
    4. 크거나 같으면 start +1
    5. 모든 케이스 반복까지 2~4 반복

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1, 2, 3, 2, 5] # 전체 수열

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    # end를 가능한 만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]

print(count)

• 정렬되어 있는 두 리스트의 합집합
  • 머지소트 내부에서 쓰이고 있음

# 사전에 정렬된 리스트 A와 B 선언
n, m = 3, 4
a = [1, 3, 5]
b = [2, 4, 6, 8]

# 리스트 A와 B의 모든 원소를 담을 수 있는 크기의 결과 리스트 초기화
result = [0] * (n + m)
i = 0
j = 0
k = 0 # result에서 현재 처리 중인 index

# 모든 원소가 결과 리스트에 담길 때까지 반복
while i < n or j < m:
    # 리스트 B의 모든 원소가 처리되었거나, 리스트 A의 원소가 더 작을 때
    if j >= m or (i < n and a[i] <= b[j]):
        # 리스트 A의 원소를 결과 리스트로 옮기기
        result[k] = a[i]
        i += 1
    # 리스트 A의 모든 원소가 처리되었거나, 리스트 B의 원소가 더 작을 때
    else:
        # 리스트 B의 원소를 결과 리스트로 옮기기
        result[k] = b[j]
        j += 1
    k += 1

# 결과 리스트 출력
for i in result:
    print(i, end=' ')

이진 탐색 트리

트리

• 계층 구조 표현 자료 구조
  • 루트 : 부모 x 최상위 노드
  • 단말 : 자식 x 노드 (leaf)
  • 크기 : 트리 모든 노드 수
  • 깊이 : 루트부터 거리
    • 루트 깊이 0
  • 높이 : 깊이 중 최대값
  • 차수 : 각 노드 자식 방향 간선 개수

항상 탐색 범위가 절반으로 줄어듬

• 균형이 잡혀있을 경우 log(N)

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

# 전위 순회(Preorder Traversal)
def pre_order(node):
    print(node.data, end=' ')
    if node.left_node != None:
        pre_order(tree[node.left_node])
    if node.right_node != None:
        pre_order(tree[node.right_node])

# 중위 순회(Inorder Traversal)
def in_order(node):
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end=' ')
    if node.right_node != None:
        in_order(tree[node.right_node])

# 후위 순회(Postorder Traversal)
def post_order(node):
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])
    print(node.data, end=' ')

n = int(input())
tree = {}

for i in range(n):
    data, left_node, right_node = input().split()
    if left_node == "None":
        left_node = None
    if right_node == "None":
        right_node = None
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

'''
[예시 입력]
7
A B C
B D E
C F G
D None None
E None None
F None None
G None None
[예시 출력]
A B D E C F G 
D B E A F C G 
D E B F G C A 
'''

우선 순위 큐

• 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
  • 힙으로 구현
  • 기본은 최소 힙
• 완전 이진 트리
  • 노드부터 시작하여 왼쪽 자식 노드 오른쪽 자식 노드 순서로 데이터 삽입
    • 삽입 삭제 시 위아래 순서는 유지됨.
  • 삽입 시 logN
    • 맨 아래에 삽입
    • 높이 logN만큼
  • 삭제 시 log N
    • 맨 마지막 노드가 루트에 오도록 함
    • 루트을 덮어씀
    • logN 위치 변경 수행
  • heapify와 heap 정렬 주의하기
    • 힙 정렬은 진짜 정렬임
    • NlogN

import sys
import heapq
input = sys.stdin.readline

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

n = int(input())
arr = []

for i in range(n):
    arr.append(int(input()))

res = heapsort(arr)

for i in range(n):
    print(res[i])

구간 합

• n개의 연속된 수
• M갸의 쿼리
• 여러 번 사용될 만한 정보는 미리 구해 저장해둔다.
  • 접두사 합
    • 리스트 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미한다.
    • O(N+M)

n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산 (세 번째 수부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])