안 까먹으려고 쓰는 코테 체크리스트(Python)

악어·2024년 9월 5일

cs공부 알고리즘 코테

코딩테스트

목록 보기

4/6

이제 곧 코테를 보러 여기저기 다니게 된다.
자주 쓸 형태를 까먹지 않게 기록해놓자.
별은 내가 생각하는 중요도로 지극히 주관적이다.

주로 내가 볼거기 때문에 설명보다는 바로 코드만 쓴다.
또한 문제풀며 계속 추가+수정할 계획이다.

1. 소수판별 (★★☆☆☆)

방법 1. 에라토스테네스의 체

장점: 시간 복잡도상 가장 유리함 -> 소수 판별보다는 모든 소수를 구할 때 유리
단점: 공간을 꽤 잡아먹기 때문에 판별 가능한 수의 크기가 한정되어 있음(메모리)

def is_prime(n: int) -> bool:
    if n<2:
        return False
    # 짝수 제거
    prime_numbers = [True for _ in range(n+1)]
    i = 2
    while 2*i<=n:
        prime_numbers[2*i] = False
        i += 1
    # 홀수끼리만 소수 판별
    for i in range(3, int(n**0.5)+1, 2):
        if prime_numbers[i]==True:
            j = i
            while i*j<=n:
                prime_numbers[i*j] = False
                j += 2
    return prime_numbers[-1]

방법 2. 약수 여부 판별

장점: 메모리를 적게 먹음 -> 매우 큰 수에 대한 소수 판별이 가능
단점: 시간 복잡도상 많은 소수를 구하거나 판별할 때에는 불리

def is_prime(n: int) -> bool:
    if n<2:
        return False
    elif n<4:
        return True
    elif n%2==0:
        return False
    
    for x in range(5, int(n*0.5)+1, 2):
        if n%x==0:
            return False
    else:
        return True

2. BFS/DFS (★★★★★)

말해 뭐해.. 가장 중요한 빈출 유형.
여기서는 2차원 배열을 탐색하는 코드를 정리한다.

BFS

장점: 실행 순서가 이동 순서를 보장해준다. 즉 최단거리를 구할 수 있다.
단점: 모든 이동 실행이 병렬적으로 일어나기 때문에 각 시점에서 나머지 실행의 결과를 알 수 없다. 또 배열을 사용하기에 메모리 측면에서 약간의 손해

from collections import deque

H, W = map(int, input().split())
visited = [[False]*W for _ in range(H)]
visited[0][0] = True
board = [[0]*W for _ in range(H)]

def bfs():
    global H, W, visited

    q = deque([(0, 0)])
    while q:
        row, col = q.popleft()
        for new_row, new_col in [(row+1, col), (row-1, col), (row, col+1), (row, col-1)]:
            if 0<=new_row<H and 0<=new_col<W and board[new_row][new_col]==0:
                visited[new_row][new_col] = True
                q.append((new_row, new_col))

DFS

장점: 특정 케이스를 끝까지 실행해 볼 수 있어 결과를 기록하는데 용이.
단점: 실행 순서와 이동순서가 다를 수 있어 여러 케이스를 동시에 놓고 비교하는 것은 불가.

from collections import deque

H, W = map(int, input().split())
visited = [[False]*W for _ in range(H)]
visited[0][0] = True
board = [[0]*W for _ in range(H)]

def dfs(row: int, col: int):
    global H, W, visited

    for new_row, new_col in [(row+1, col), (row-1, col), (row, col+1), (row, col-1)]:
        if 0<=new_row<H and 0<=new_col<W and board[new_row][new_col]==0:
            visited[new_row][new_col] = True
            dfs(new_row, new_col)

3. 이분 탐색 (★★★☆☆)

방법 1. 구현

평범한 구현법으로, 이분 탐색을 응용한 여러가지 상황에서 모두 사용 가능하다.
아래처럼 lp==rp인 경우까지 while문이 돌아가게 한 뒤, 최대값은 rp를, 최소값은 lp를 반환해야 정확한 index가 나옴에 유의하자. cp를 구할 때 2로 나누며 나머지를 무시하기 때문에 나오는 특징이다. 물론 이는 리스트 안에 찾고자 하는 값이 없을때만 해당하는 얘기다.

def binary_search(lst: list, x: int) -> int:
    lp, rp = 1, len(lst)-1
    while lp<=rp:
        cp = (lp+rp)//2
        if lst[cp]==x:
        	return cp
        elif lst[cp]>x:
        	rp = cp-1
        else:
            lp = cp+1
    return rp

방법 2. bisect 모듈 사용

예쁘게 리스트로 정리된 숫자 배열에서 이분 탐색을 쓸 수 있다면, bisect 모듈 사용을 고려해볼 수 있다. 다만 넣을 자리를 찾는 것은 O(logN)일지라도 해당 자리에 insert 하는 것은 O(N) 이므로 주의하자.

from bisect import bisect_left

idx = bisect_left(lst, x)

4. 비트마스킹 (★★★☆☆)

별 두개를 줄까 하다가, 2022년 카카오 코테에서
이를 활용하면 쉽게 풀리는 문제가 있어 3개 줬다.

자주 나오는 유형은 아니지만, 까먹으면 치명적이기에 암기 중요도는 높은 편.

# 초기 배치는 73 = 1001001(2)
bit = 73

# 3번째 위치에 할당하기 (이미 할당되었다면 값 변화 x)
# 실행 결과는 77 = 1001101(2)
bit = bit | (1<<2)

# 4번째 위치 제거하기
# 실행 결과는 69 = 1000101(2)
bit = bit & ~(1<<3)

# 7번째 위치 할당여부 확인
# 실행 결과는 True
bit == bit | (1<<6)

5. union-find (★★★★☆)

단순히 집합 여부를 판단하는 용도라면 별 세개겠지만
크루스칼 알고리즘이나 특정 상황에서 은근 자주 쓰인다.

집합 관련되었다면 일단 믿고쓰는 국밥 기법.
경로 단축 개념을 모른다면 반드시 보고 적용하자.

def find(x: int) -> int:
    global parent
    
    if parent[x]!=x:
    	parent[x] = find(parent[x])
    return parent[x]
    
    
def union(a: int, b: int):
	global parent
    
    pa, pb = find(a), find(b)
    if pa!=pb:
    	parent[min(pa, pb)] = max(pa, pb)

6. 위상 정렬 (★★☆☆☆)

좀 지엽적인 알고리즘일 수 있으나,
선후관계가 조성되어 있는 문제에서는 국밥처럼 든든한 친구.

from collections import deque

N = int(input())
next_nodes = [set() for _ in range(N)]
indegrees = [0]*(N)
for node in range(N):
    # next_nodes 리스트에 선후관계를 채워넣는 로직
    
q = deque()
for node in range(N):
    if indegrees[node]==0:
        q.append(node)
        
while q:
    node = q.popleft()
    for next_node in next_nodes[node]:
        indegrees[next_node] -= 1
        if indegrees[next_node]==0:
        	q.append(next_node)

7. 세그먼트 트리 (★☆☆☆☆)

얘가 기업 코테에 활용될 상황이면 그냥 대부분 못풀지 않을까 싶다.
그냥 내가 자꾸 구현방법을 까먹어서 여기 남겨놓는다.

from math import log2, ceil

def segment(idx: int, fr: int, to: int) -> int:
    global lst, segment_tree
    
    if fr==to:
        segment_tree[idx] = lst[fr]
    else:
        c = (fr+to)//2
        segment_tree[idx] = segment(2*idx, fr, c)+segment(2*idx+1, c+1, to)
    return segment_tree[idx]
    

def edit(idx: int, target: int, change_to: int, fr: int, to: int) -> int:
    global segment_tree
    
    if target<fr or target>to:
        pass
    elif fr==to==target:
        segment_tree[idx] = change_to
    else:
        c = (fr+to)//2
        segment_tree[idx] = edit(2*idx, target, change_to, fr, c)+edit(2*idx+1, target, change_to, c+1, to)
    return segment_tree[idx]
    

def get_value(idx: int, target_fr: int, target_to: int, fr: int, to: int) -> int:
    global segment_tree
    
    if target_to<fr or target_fr>to:
        return 0
    elif fr>=target_fr and to<=target_to:
        return segment_tree[idx]
    else:
        c = (fr+to)//2
        return get_value(2*idx, target_fr, target_to, fr, c)+get_value(2*idx+1, target_fr, target_to, c+1, to)
        
        
N = int(input())
lst = [int(input()) for _ in range(N)]
segment_tree = [0]*(1+2**(ceil(log2(N))+1))
segment(1, 0, N-1)
edit(1, fr, to, 0, N-1)
get_value(1, fr, to, 0, N-1)

.
.
.
계속 추가 예정