코딩테스트 시험 전 보는 요약 노트

 

사실 코딩 테스트 요약본은 크게 도움 되지 않는다는 것을 모두가 안다. 그럼 왜 만들었느냐?

• 어떤 문제가 나올지 모르는 상태에서 혹시라도 쉬운 함수나 공식을 까먹을까봐
• 마음의 평안을 위해서
• 유용한 코드나 함수가 있을 때 마다 정리해놓으려고

물론 알고리즘 종류는 다양하고 논리적인 사고로 문제를 풀어야하기 때문에 외우는 것은 도움이 되지 않는다.
가끔 함수나 라이브러리가 기억이 나지 않을 때 참고하기 좋았다.

알고리즘

---

DFS/BFS

# DFS 메서드 정의
def dfs(graph, v, visited):
    # 현재 노드 방문처리
    visited[v] = True
    print(v, end = ' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    # 현재 노드를 방문 처리
    visited[start] = True

    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        print(v, end = ' ')

        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트)
graph = [[], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7]]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

 

힙

• 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나
• 파이썬에서는 PriorityQueue 보다 heapq가 더 빠르게 동작한다.
• 파이썬에서는 최소 힙 구조를 이용

from heapq import heapify, heappop, heappush ,,,

index = [1, 3, 2, 45, 3]
heappush(index, 7)   # 힙에 원소 추가
heappop(index)   # 힙에서 원소 삭제, 최소 힙이므로 가장 작은 값 삭제 됨.
heapify(index)   # 리스트를 힙으로 변환

 

다익스트라

두번째 방법, 까다로운 구현이지만 빠른 방법

• 각 단계에서 ‘최단 거리가 가장 짦은 노드’를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체한다.
• 효과: get_smallest_node() 를 작성할 필요가 없어서 훨씬 빨리 찾을 수 있다.
• 우선순위 큐는 파이썬의 heapq를 활용한다.
• 시간복잡도는 $O(ElogV)$으로 훨씬 빠르다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)  # 무한을 의미하는 10억

# 노드, 간선 개수
n, m = map(int, input().split())
# 시작 노드 입력
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)

# 모든 간선 정보 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a -> b 의 비용이 c
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입 (거리, 노드)의 형태로
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:    # 큐가 비어있지 않다면, 
        # 가장 최단 거리가 짧은 노드에 대해 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면(최단거리 < 현재 소요되는 거리) 무시
        # 이미 처리되면, 최단거리가 결정된 것이므로.
        if distance[now] < dist:
            continue    # 다음 큐 원소 처리
        # 현재 노드와 연결된 다른 인접한 노드들을 확인하면서 최단 거리테이블을 갱신한다.
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
    if distance[i] == INF:
        print('무한')
    else:
        print(distance[i])

 

플로이드와샬

n = int(input())
k = int(input())

# 이차원 행렬 그래프 만들기
INF = int(1e9)  # 초기값 무한으로.
graph = [[INF for _ in range(n+1)] for _ in range(n+1)]

# 연결 정보 업데이트
for _ in range(k):
    a, b, c = map(int, input().split())
    graph[a][b] = c # a에서 b노드까지 c 만큼 소요

# 자기자신 -> 자기자신 비용은 0으로 설정
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0

# 점화식에 따라 플로이드 와샬 알고리즘 수행
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])   

# 모든 노드에 대한 최단경로 출력
for i in range(1, n+1):
    for j in range(1, n+1):
        # 도달할 수 없는 경우 무한(INFINITY)이라고 출력
        if graph[i][j] == INF:
            print("INFINITY", end = ' ')
        else:
            print(graph[i][j], end = ' ')
    print()

# 입력값
# 4 
# 7
# 1 2 4
# 1 4 6
# 2 1 3
# 2 3 7
# 3 1 5
# 3 4 4
# 4 3 2

 

이분탐색

• 아래 두개의 코드는 조건문 형태가 다르다. 문제에 따라 달라지니 이 점 유의해서 구현하기!

import sys
input = sys.stdin.readline

N = int(input())    # 상근이가 가지고 있는 숫자 카드 개수
cards = list(map(int, input().split())) # 상근이가 가지고 있는 숫자 카드에 적혀있는 정수
cards.sort()    # 이분탐색을 위한 정렬!!!!

M = int(input()) 
M_cards = list(map(int, input().split()))   # 상근이가 몇개 가지고 있는지 요구되는 정수들

def binary_search(array, target, start, end):
    if start > end:
        return 0
    mid = (start + end) // 2
    if array[mid] == target:
        return array[start:end+1].count(target)
    elif array[mid] < target:
        return binary_search(array, target, mid+1, end)
    else:
        return binary_search(array, target, start, mid-1)

n_dic = {}    #상근이가 가지고 있는 카드숫자가 몇 번 등장했는지 저장한 딕셔너리
for c in cards:
    if c not in n_dic:
      n_dic[c] = binary_search(cards, c, 0, N-1) # 여기서 이분탐색

for i in M_cards:
    if i in n_dic:
        print(n_dic[i], end = ' ')
    else:
        print(0, end = ' ')

import sys
input = sys.stdin.readline

N, M = map(int, input().split())    # N(나무의 수), M(가져가려고 하는 나무 길이)

tree = sorted(list(map(int, input().split())))  # 나무 리스트

def binary_search(tree, M, start, end):
    sum = 0
    mid = (start+end) // 2
    if start > end:
        return mid

    # 나무 자르기
    for t in tree:
        if t-mid >= 0:  # 잘라진다면,
            sum += (t-mid)

    if sum >= M:
        return binary_search(tree, M, mid+1, end)
    else:
        return binary_search(tree, M, start, mid-1)

result = binary_search(tree, M, 0, max(tree))
print(result)

 

유니온파인드

• 부모 찾을 때, 경로 압축 기법을 사용하기
• 합집합 할 때 비교 하는거 헷갈리지 않기

# 유니온파인드
import sys
sys.setrecursionlimit(1000000) # 재귀 깊이 제한 늘리기
# sys.setrecursionlimit(10**6) # 재귀 깊이 제한 늘리기
input = sys.stdin.readline

n, m = map(int, input().split())    # n+1개의 집합, m개의 연산
parent = [0] * (n+1)    # (n+1)개의 부모 노드 리스트

# 부모 테이블 자기 자신으로 초기화
for i in range(n+1):
    parent[i] = i

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

for _ in range(m):
    check, a, b = map(int, input().split())
    if check == 0:
        # a, b를 합치고
        union_parent(parent, a, b)
    else:
        # a, b가 같은 집합에 포함되어 있는지 확인한다.
        if find_parent(parent, a) == find_parent(parent, b):
            print('YES')
        else:
            print('NO')

유용한 함수

---

• 소수 찾기

#소수 판별 함수
def is_prime_number(x) :
    if x < 2 :
        return False

    for i in range(2, x) :
        if x % i == 0 :
            return False
    return True

 

• 순열/조합

from itertools import permutations
from itertools import combinations
from itertools import combinations_with_replacement

def solution(numbers):
    answer = 0

    num = []
    for i in range(1, len(numbers)+1) :
        #순열 모듈 사용해서 나올 수 있는 모든 수 조합
        num.append(list(set(map(''.join, permutations(numbers, i)))))
    per = list(set(map(int, set(sum(num, [])))))

    for p in per :
        if is_prime_number(p) == True :
            answer += 1

    return answer

 

• 리스트의 요소들의 숫자를 Counter 라이브러리

from collections import Counter
N = [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
C = Counter(N)

print(C)
>> # Counter({'10': 3, '3': 2, '-10': 2, '6': 1, '2': 1, '7': 1})

# 딕셔너리의 items()를 활용해서 key-value를 뒤짚을 수 있다.
reverse_counter = {v:k for k, v in C.items()}

 

• 재귀함수 깊이 늘리기

import sys
sys.setlimitrecursion(1000000)
또는
sys.setlimitrecursion(10**6)  # 10*6이면 60이므로 주의하기

 

• 초깃값 지정이 필요없는 딕셔너리 defaultdict 라이브러리

from collections import defaultdict

text = "Life is too short, You need python."

d = defaultdict(int)   # 인수로 int를 전달하여 딕셔너리 d를 생성한다.
# int를 기준으로 생성한 딕셔너리 d의 값은 항상 0으로 자동 초기화 되므로 초기화를 위한 별도 코드가 필요없음.

for c in text:
    d[c] += 1

print(dict(d))

• 딕셔너리의 key, value 뒤짚기

# key-value 뒤집기: value로 부터 key를 찾으면 순회해야 하므로 간단하게 키-값 을 뒤짚고 get함수로 가져온다.
reverse_dict = {v:k for k, v in alpha_dict.items()}

 

• 리스트 정렬 - 1차원, 2차원

list.sort() # 오름차순 정렬

list.sort(reverse=True) # 내림차순 정렬

list.sort(key = len)  # key 값을 기준으로 정렬, 여기서는 길이를 기준으로 정렬 (len은 길이를 나타내주는 함수)

list.sort(key = lambda x:x[0])  # 2차원 배열의 첫번째 원소를 기준으로 정렬

list.sort(key = lambda x:x[1])  # 2차원 배열의 두번째 원소를 기준으로 정렬

꿀팁모아

---

• 그래프에서도 경로를 찾는 문제면 weight가 없을때 bfs dfs
• weight가 있을때는 dijkstra, floyd warshall
• 경로를 찾는게 아니라 연결성을 묻는 문제면 Mst나 유니온파인드 같은거 쓰는 상황이 많다.

→ 100% 공식이 아니니까 유의해서 잘 판단하기, 잘못 판단하면 올바르지 않은 방법으로 시간을 낭비할 수 있다. (경험담 ㅜ ㅜ)