Search
😎

알고리즘 문제 풀이 팁

목차
아래 강의 수강 후 정리한 내용이 다수 존재합니다.

그리디 알고리즘

기본적인 의미는 탐욕(그리디) 알고리즘이다.
현재 상황을 기준으로, 가장 좋은 방법을 선택하는 것이다.
내가 생각한 그 좋은 방법이 매번 반복적으로 선택할 때 최적의 해를 구할 수 있는 방법인지 확인해야한다.
몇 문제를 풀어보니, 나열된 값의 정렬이 매우 중요하다.
즉, 경우의 수(주어질 지, 내가 만들어야될지는 모르겠지만)를 잘 정렬하여 현재 상황이 원하는 순서대로 나타날 수 있도록 해야한다.
예시를 들어보자.
보통 드라이버 세트를 사면 옆 사진처럼 사용할 수 있는 나사의 크기별로 드라이버가 순서대로 들어있다.
어떤 드라이버는 안경용으로 사용되는 매우 작은 나사를 조절할 때 사용할 수 도 있다.
또 어떤 드라이버는 가구 등을 조립할 때 사용하는 큰 나사를 조절할 때 사용하는 드라이버가 있을 수 있다.
근데 우리가 눈으로 나사를 보면 바로 어떤 드라이버가 맞는지 알기 어려울거다.
그래서 우리는 나사와 맞는 모양을 찾고, 크기순으로 하나씩 끼워보며 확인한다.
만약 드라이버가 크기별로 정리되어 있지 않는다면, 적합한 드라이버를 빠른시간에 찾기 어려울 것이다.
만약 잘 정돈되어 있다면, 우리가 원하는 현재 상황은 아래와 같을 것이다.
작은 드라이버 → 큰 드라이버
큰 드라이버 → 작은 드라이버
그리디 알고리즘도 마찬가지다.
경우의 수가 마구 섞여 있다면, 매 순서대로 최적의 방법을 찾는 그리디 알고리즘을 제대로 동작할 수 없다.

구현

시뮬레이션이나 탐색 문제는 2차원 공간에서 방향 벡터를 자주 사용한다.
일반적으로 알고리즘의 2차원 공간은 행렬(Matrix)의 의미를 가지고 사용된다.
이 행렬은 (0, 0) 부터 시작된다.
출처 : 유튜브 “[이것이 코딩 테스트다 with Python] 14강 구현 유형 개요” 강의 중

DFS (깊이 우선 탐색)

설계

주로 재귀함수 방식과 스택을 자주 사용한다.
하나의 기준에서 조건에 맞는 노드를 계속 연결하여 찾기 때문이다.
따라서 재귀로 DFS를 구현할 때, 함수 시작 부분에 중단 조건을 반드시 설정해줘야 한다.
크게 아래와 같은 느낌으로 설계하면 편하다.
def dfs(...): # 탐색 종료 조건 if 탐색 종료 조건: return False if 추가 탐색 가능 조건: # 해당 위치(노드)에 방문했음을 기록하는 코드(문제에 따라 선택) ... # 탐색할 범위의 재귀함수 동작 dfs(...) dfs(...) dfs(...) # 이 부분까지 왔다면, 중간에 멈추지 않고 끝까지 탐색을 마친 경우이다. return True # 추가 탐색 가능 조건에 맞지 않을 때: return False
Python
dfs(...) 함수를 아래처럼 사용할 수 있다.
dfs(...) 사용 시 인자는 다를 수 있다.
... for i in range(N): for j in range(M): if dfs(i, j) == True: 탐색 완료 시 동작 코드
Python

함수 호출 횟수 조정

DFS에서 재귀함수를 사용할 때, 예시에 따라 기본적으로 한정한 재귀 깊이를 넘어서도록 재귀 함수를 호출할 때가 있다. 이때는 RecursionError 를 발생시킬 수 있다.
백준에서 작성한 에러 관련 내용을 살펴보면 백준의 채점 서버에서 정한 기본적인 재귀 깊이는 1000이기 때문에, 그 이상 재귀를 사용하게 되는 예시는 에러를 뱉는다고 한다.
현재 사용하는 IDE에서도 아래처럼 확인이 가능한데, 본인도 1000이 나왔다.
import sys # 1000 print(sys.getrecursionlimit())
Python
아래와 같이 sys모듈의 setrecursionlimit() 메서드를 사용하여 수치 조정이 가능하다.
보통은 10610^{6}이나 10910^{9}값으로 설정한다고 하는데, 아무리 크게 잡아도 채점 서버가 감당할 수 없어질 정도로 깊어지면 Segmentation fault 가 발생해 런타임 에러 이유로 SegFault를 받게된다고 한다.
import sys sys.setrecursionlimit(10**6) ...
Python
아무튼 위와 같이 수정하면 아래 이미지처럼 정상적으로 채점이 진행된다.

BFS (넓이 우선 탐색)

주로 큐와 while 함수를 자주 사용한다.
DFS가 하나의 위치에서 조건에 맞는 위치(노드)를 끝까지 탐색했다면, BFS는 하나의 위치에서 인접한 여러 위치(노드)들이 조건에 맞는지를 우선 확인한다.
간단히 말하면 긴 밧줄과 그물과 같은 차이라고 보면 된다.
마찬가지로 함수 초반에 탐색을 중단하는 코드가 반드시 있어야 된다.
from collections import deque # 예시로 x,y 인자를 넣어준 것 def bfs(x, y): # 처음 노드를 초기값으로 넣어준다. queue = deque([(x,y)]) # 큐에 값이 들어있다면 계속 반복 while queue: # 큐에서 값 먼저 꺼내기 K = queue.popleft() # 꺼낸 값이 탐색을 진행할 수 없는 조건인지 if 탐색 불가능 조건: break # 주변의 위치(노드)들이 탐색할 조건에 맞는지 # 현재 위치(노드)에서 값을 조정하여 주변의 위치(노드)의 값을 확인한다. if 주변 노드 값 비교 조건: queue.append(주변 노드 값) 주변 노드의 값을 변경하여, 방문했는지 여부를 설정하거나 몇 번 이 노드를 조회했는지 값을 설정할 수 있다. ...더 많은 주변 노드 탐색 조건 추가
Python
bfs(...) 함수를 아래처럼 사용할 수 있다.
함수안에서 while로 동작하는 경우 밖에서는 한번만 동작시키면 된다.
bfs(...)
Python
만약 특정 2차원 공간에서 최단거리를 구하는 문제일경우, 각 노드에 방문할때마다 노드의 방문 횟수를 기록하면 편하게 최단거리를 구할 수 있다.
확률과 통계에서 배우는 최단거리를 검색하면 더 이해가 빠르게 가능하다.
특정 조건들의 상태에 따라, 별도로 벡터의 상태를 기록해야될 때는 배열을 한차원 더 만들어주면 된다.
상태 값에 따라 함수의 진행이 달라지며, 각 좌표에 반영되는 시점도 다르기 때문이다.
예시로 백준에는 벽 부수기 라는 문제가 있는데, 이 문제에서는 벽 부수기를 사용했는지 여부에 따라 각 좌표의 값이 다르다.

DFS / BFS 공통

각 노드의 연결 정보 정리

문제에서 각 노드의 연결정보를 [ A, B ] 형태의 원소 값이 모인 리스트로 제시해주는 경우가 있다.
이때는 각 노드가 어떤 노드와 연결되었는지 한눈에 확인하기가 불편하다. 아래와 같이 가공하여 문제를 풀면 편하다.
sort()로 정렬을 해준 이유는 더 빠른 탐색을 위해서이다.
# 첫 줄은 각각 정점의 개수와 간선의 개수를 나타낸다. (정점 개수 -> 6 / 간선 개수 -> 5) 6 5 1 2 2 3 4 5 6 3 5 3
Plain Text
# 기존 방법 graph = [list(map(int, input().split())) for _ in range(M)] # [ # [1, 2], # [2, 3], # [4, 5], # [6, 3], # [5, 3] # ] print(graph) # 각 노드별로 연결 노드 저장 graph = [[] for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) graph[a].sort() graph[b].sort() # [[],[2],[1, 3],[2, 5, 6],[5],[3, 4],[3]] print(graph)
Python

Upper bound / Lower bound

오름차순으로 정렬된 숫자들로 이루어진 배열에서, 특정 값(target)보다 큰 / 크거나 같은 값이 존재하는 첫 위치를 찾을 때 사용한다.
Upper bound : 배열에서 특정 값(target)보다 큰 값이 존재하는 첫 위치를 찾는다.
예시
Lower bound : 배열에서 특정 값(target)보다 크거나 같은 값(이상)이 존재하는 첫 위치를 찾는다.
예시