1. 재귀함수 (Recursive Function)
- 자기 자신을 다시 호출하는 함수
- 최대 반복(Recursion)의 깊이 제한이 있으며, 함수 호출 시 프로그램은 메모리 구조에서 스택을 이용
- 재귀호출은 반복적인 스택의 사용을 의미하여 메모리 및 속도에서 성능 저하가 발생
일반적으로 코딩테스트에서는 재귀함수의 종료조건을 반드시 명시해야 하며, 그렇지 않으면 무한히 호출되어 중간에 중단되는 오류가 발생됨 - 팩토리얼 구현 예제
- 반복적으로 1부터 n까지 차례대로 곱하는 형태로 구현될 수 있으나, 이를 재귀함수로 구현할 수 있음
def factorial(n):
# 재귀함수를 다시 호출하지 않는 종료 조건
if n <= 1:
return 1
else:
return n * factorial(n-1)- 유의사항
- 모든 재귀함수는 반복문을 이용하여 동일하게 기능을 구현 가능
- 반복문보다 유리한 경우도 있고 불리한 경우도 있으니, 두 가지 모두 고려하여 검토
- 연속적으로 호출하면 메모리 내부의 스택 프레임에 쌓이므로 그래프 스택을 사용할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많음
(1) 하노이의 탑
- 문제설명
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. - 입력조건 : 첫 번째 장대에 쌓인 원판의 개수 N (1≤N≤ 20)이 주어진다.(예시 : 3)
- 출력조건
- 첫째줄에 최소 이동 횟수 K를 출력한다.
- 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.
- 예시
7 1 3 1 2 3 2 1 3 2 1 2 3 1 3
# N 입력
n = int(input())
# 최소 이동 횟수를 구하는 방법 구현
moves =[]
def hanoi(n, start, end, temp):
if n > 0:
hanoi(n-1, start, temp, end) #n-1개 원판을 start에서 temp로
moves.append((start, end)) #n을 start에서 end로
hanoi(n-1, temp, end, start) #n-1개를 temp에서 end로
hanoi(n, 1, 3, 2)
print(len(moves))
for m in moves:
print(*m) #m을 프린트하는데 언팩해서3
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3
2. DFS / BFS (탐색 알고리즘)
(1) DFS (Depth-First Search, 깊이 우선 탐색)
- 비선형 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
- 스택 자료구조(혹은 재귀함수)를 이용 : 가장 마지막에 만났던 갈림길의 노드로 되돌아서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 이용
- 동작 과정
- 탐색 시작노드(v)를 결정하여 방문 처리
- 노드(v)에 인접합 정점 중에서
- 방문하지 않은 노드 w가 있으면, 노드 v를 스택에 push하고 노드w를 방문, w를 v로 하여 다시 2번을 반복
- 방문하지 않은 노드가 없으면, 탐색의 방향을 바꾸기 위해 pop하여 가장 마지막 방문 정점을 v로 하여 다시 2번을 반복
- 스택이 공백이 될 때까지 2번을 반복
- 결국 모든 노드를 방문하는 순회하는 방법
# DFS 함수 정의 (스택 활용)
def dfs(graph, s, visited):
# 현재 노드를 방문 처리
visited[s] = True
stack = [] # 스택 초기화 (비어있는 리스트)
# 스택이 비어있지 않으면 계속해서 탐색
v = s # s를 현재 노드로 변경
print(s, end=' ')
while True:
for w in graph[v]: #v에 인접하고, 방문안한 w가 있으면
if not visited[w]: # 만약 현재 노드가 방문되지 않았다면
stack.append(v) # 스택에서 현재 방문 노드를 추가
v = w #w를 현재 노드로 변경
print(w, end=' ')
visited[w] = True # w방문 표시
break #v부터 다시 탐색
else:
if stack:
v = stack.pop() # 이전 갈림길을 스택에서 꺼냄
else: #스택이 비어있으면 탐색 종료
break# 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 #node의 최대값
# 정의된 DFS 함수 호출
dfs(graph, 1, visited)1 2 7 6 8 3 4 5
(2) BFS (Breadth-First Search, 너비 우선 탐색)
- 비선형 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
- 큐 자료구조를 이용 : 인접한 노드들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 이용
- 동작과정
- 탐색 시작노드(v)를 결정하여 큐에 삽입하고 방문처리
- 노드(v)에 인접합 정점 중에서
- 큐에서 노드를 꺼내어 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
- 큐가 공백이 될 때까지 2번을 반복
- 결국 모든 노드를 방문하는 순회하는 방법
# BFS 구현 (큐활용)
from collections import deque
# BFS 함수 정의
def bfs(graph, v, visited):
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque([v])
# 현재 노드를 방문 처리
visited[v] = 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)1 2 3 8 7 4 5 6
(3) 미로탈출
- 문제설명
엘리자베스가 산책을 하다가 NxM크기의 미로에 갖혔습니다. 찰스가 엘리자베스를 구하기 위해서 미로에 진입하였는데 벽으로 막혀있어 갈 수 없는 길이 있습니다. 이때 벽은 0으로, 갈 수 있는 길은 1로 표시되어 있습니다. 이때 찰스 왕자가 (1,1)입구에서 엘리자베스가 있는 (N,M)까지 최대한 빠르게 가기 위해 지나가야 하는 최소 칸의 개수를 구하세요. - 입력조건
- 첫째줄에는 두 정수 N,M(4≤N,M≤200)이 주어집니다.
- 다음 N개의 줄에는 각각 M개의 정수(0또는1)로 미로의 정보가 공백없이 붙여서 입력으로 제시됩니다.
- 미로 입구와 공주의 위치인 시작칸과 마지막칸은 항상 1입니다.
- 예시
5 6 101010 111111 000001 111111 111111
- 출력조건 : 최소이동칸의 개수를 출력합니다. 공주에게 도착할 수 없을 경우 -1을 출력합니다. (예시: 10)
from collections import deque
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
# 2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
# BFS 함수 정의
def bfs(graph, n, m):
# 이동할 방향 (상하좌우)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 큐 초기화
queue = deque([(0,0)])
# 방문여부 및 거리 저장 리스트 만들기
distance = [[-1] * m for _ in range(n)] # -1로 초기화 (-1이면 미방문)
distance[0][0] = 1 #시작점은 1로 저장
# BFS 탐색
while queue:
x, y = queue.popleft()
# (x,y)에서 방향이동
for dx, dy in directions:
nx, ny = x+dx, y+dy #다음좌표
# 다음좌표는 범위를 벗어나면 안된다.
# 갈수 있는 길이어야 한다.
# 방문하지 않은 곳
if 0 <= nx < n and 0<= ny < m and graph[nx][ny] == 1 and distance[nx][ny] == -1:
#해당칸을 방문 처리를 하고, 큐에 추가
distance[nx][ny] = distance[x][y] + 1 #이동회수 1 더하기
queue.append((nx, ny))
# 목적지에 도달하면 결과를 반환
if nx == n-1 and ny ==m-1:
return distance[nx][ny]
# 목적지에 도달할 수 없다면 -1
return -1
# BFS 수행
print(bfs(graph, n, m))def bfs(graph, n, m):
# 이동할 방향 (상하좌우)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 큐 초기화
queue = deque([(0,0)])
# 방문여부 및 거리 저장 리스트 만들기
distance = [[-1] * m for _ in range(n)] # -1로 초기화 (-1이면 미방문)
distance[0][0] = 1 #시작점은 1로 저장5 6
101010
111111
000001
111111
111111
10
3. 분할 정복 기법 (Divide and Conquer)
- 문제를 분할해서 해결하는 방법
- 주요 분할 정복 알고리즘
- 퀵 정렬
- 병합 정렬
- 이진 검색
- 설계 전략
- 분할(Divide) : 해결할 문제를 여러개의 작은 부분으로 나눈다.
- 정복(Conquer) : 나눈 작은 문제를 각각 해결한다.
- 통합(Combine) : (필요하다면) 해결된 해답을 모은다.
- 분할 정복 기법 예시 (거듭제곱, )
- 일반적으로 n번 곱하는 반복 알고리즘 :
- 분할 정복 기반의 알고리즘 :
(1) 병합정렬 (Merge Sort)
- 여러 개의 정렬된 자료의 집합을 병합하여 한개의 정렬된 집합으로 만드는 방식
- 자료를 최소 단위의 문제까지 나눈후 차례대로 정렬하여 최종결과를 얻어냄 (top-down방식)
- 동작 과정
- 분할 단계 : 전체 자료의 집합에 대하여 최소 크기의 부분집합이 될때까지 분할작업을 계속한다. (최소크기는 1)
- 병합 단계 : 2개의 부분 집합을 정렬하면서 하나의 집합으로 병합, 부분집합이 1개로 병합될 때까지 반복
- 시간 복잡도 : 분할할때 , 이를 병합할때 N번 반복하기 때문에
# 병합정렬
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def merge_sort(array):
# 리스트의 길이가 1이면 이미 정렬된 상태이므로 그대로 반환
if len(array) == 1:
return array
# 리스트를 절반으로 나누기 위해 중간 인덱스 계산
mid = len(array) //2
left = array[:mid]
right = array[mid:]
# 재귀적으로 left와 right를 정렬
left = merge_sort(left)
right = merge_sort(right)
# 두개의 정렬된 리스트를 병합하여 반환
return merge(left, right)
def merge(left, right):
# 두 리스트를 병합할 결과 리스트를 초기화
result = [0] * (len(left)+len(right))
l = r = 0 # 왼족 리스트와 오른쪽 리스트의 인덱스
# 두 리스트를 순차적으로 비교하여 작은 값을 결과 리스트에 추가
while l < len(left) and r < len(right):
if left[l] < right[r]:
result[l+r] = left[l]
l += 1
else:
result[l+r] = right[r]
r += 1
# 왼쪽 리스트에 남은 요소들을 결과 리스트에 추가
while l < len(left):
result[l+r] = left[l]
l += 1
# 오른쪽 리스트에 남은 요소들을 결과 리스트에 추가
while r < len(right):
result[l+r] = right[r]
r += 1
return result
print(merge_sort(array))[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
(2) 퀵 정렬
- 주어진 배열을 두개로 분할하고 각각을 정렬하는 방식
- 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 과정(Partitioning)을 반복하여 정렬하는 방법
- 가장 기본적인 퀵 정렬은 첫번째 데이터를 기준데이터(Pivot)로 설정
- 각 부분 정렬이 끝난후 병합이라는 후처리작업이 불필요
- 시간복잡도
- 이상적인 경우 분할이 절반씩 일어난다면 너비 x 높이 =
- 최악의 경우(이미 정렬된 배열),
# 퀵정렬
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
if len(array) <=1:
return array
pivot = array[0] # 피벗은 첫 번째 원소
tail = array[1:] # 피벗을 제외한 리스트
left = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
right = [x for x in tail if x > pivot] # 분할된 오른쪽 부분
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 재귀함수를 호출하고, 전체 리스트 반환
return quick_sort(left) + [pivot] + quick_sort(right)
print(quick_sort(array))[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
(3) 이진 탐색 (Binary Search)
- 자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
- 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 수행함
- 이진검색을 하기 위해서는 자료가 정렬된 상태여야 함
- 동작과정
- 자료의 중앙에 있는 원소를 선택
- 중앙 원소의 값과 찾고자 하는 목표값을 비교
- 목표 값이 중앙원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새롭게 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새롭게 검색을 수행
- 찾고자 하는 값을 찾을 때까지 1~3의 과정을 반복
- 시간복잡도 : 전체데이터를 1/2만큼 줄여 가면서 값을 검색하기 때문에
## 이진탐색
array = [2, 4, 7, 9, 11, 19, 23]
def binary_search(array, target):
# 최소와 최대값을 초기화
low = 0
high = len(array) - 1
# 탐색 회수 카운팅
count = 0
# target 이진검색(low와 high가 같아질는 경우가 마지막)
while low <= high:
mid = (low + high) // 2 #중간값 선택
count += 1
if array[mid] == target:
return mid, count
elif array[mid] < target: #중간값보다 크면 오른쪽 탐색
low = mid + 1
else: #중간값보다 작으면 왼쪽 탐색
high = mid - 1
return -1, count #검색하지 못했을때 -1을 반환
print(binary_search(array, 9))(3,1)
# 이진검색 (재귀함수 활용)
def binary_search(low, high, target):
# 종료조건
# target을 찾지 발견하지 못하면 종료
if low > high:
return -1
mid = (low + high) // 2 #중간값 선택
# target 이진 검색
# 발견을 했다면,
if array[mid] == target:
return mid
# 중간값보다 크면 오른쪽 탐색
elif array[mid] < target: #중간값보다 크면 오른쪽 탐색
return binary_search(mid + 1, high, target)
# 중간값보다 작다면 왼쪽 탐색
else:
return binary_search(low, mid - 1, target)(4) 분할 정복 기법 정리
- 병합정렬 : 기본이 되는 정렬 알고리즘
- 퀵정렬 : 매우 큰 데이터에 대해 좋은 성능을 보이는 알고리즘
- 이진검색 : 정렬된 데이터를 기준으로 특정값이나 범위를 검색하는데 사용
(5) 곱셈
- 문제설명
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. - 입력조건 : 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.(예시 : 10 11 12)
- 출력조건 : A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. (예시: 4)
# A, B, C 데이터 입력받기
a, b, c = list(map(int, input().split()))
def modular(a, b, c):
# B가 0일경우
if b == 0:
return 1
# B가 짝수인 경우
if b % 2 == 0:
half = modular(a, b // 2, c)
return (half * half) % c
# B가 홀수인 경우
else:
half = modular(a, (b-1) // 2, c)
return (half * half * a) % c
print(modular(a, b, c))10 11 12
4
(6) 연구소
- 문제 설명
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 NxM인 직사각형으로 나타낼 수 있으며, 직사각형은 1x1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
- 입력조건
- 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
- 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
- 빈 칸의 개수는 3개 이상이다.
- 예시
```
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
```
- 출력조건 : 얻을 수 있는 안전 영역의 최대 크기를 출력한다. (예시: 27)
```python
n, m = 7,7
data = [[2,0,0,0,1,1,0], [0,0,1,0,1,2,0], [0,1,1,0,1,0,0],
[0,1,0,0,0,0,0], [0,0,0,0,0,1,1], [0,1,0,0,0,0,0],
[0,1,0,0,0,0,0]]
floor = [[0]* m for _ in range(n)] #벽을 설치한 뒤의 맵 정보
# 이동방향 (상하좌우)
directions = [(-1,0), (1,0),(0,-1),(0,1)]
# dx = [-1, 1, 0, 0]
# dy = [0, 0, -1, 1]
result = 0
# virus가 퍼졌을때 어떻게 맵이 변하는지
def virus(x,y):
for dx, dy in directions:
nx, ny = x+dx, y+dy
# 상하좌우중에 바이러스가 퍼질수 있는
if 0 <= nx < n and 0 <= ny < m:
if floor[nx][ny] ==0:
# 바이러스를 배치하고 다시 재귀적으로 수행
floor[nx][ny] = 2
virus(nx,ny)
# 퍼진 후에 안전영역 크기 구하기 (맵에서 0을 카운트)
def count_safe():
score = 0
for i in range(n):
for j in range(m):
if floor[i][j] == 0:
score +=1
return score
# 벽을 3개 세우자. (DFS) 벽을 세운후 카운트
# 새롭게 계산된 카운트가 클 경우 answer(최종결과값) 업데이트 (answer의 초기값은 0)
def dfs(count): # 벽의 개수를 인자로 받음
global result
# 벽을 3개 설치된 경우
if count == 3:
for i in range(n): #입력된 정보를 현재 Floor 정보로 저장
for j in range(m):
floor[i][j] = data[i][j]
# 각 바이러스의 위치를 전파
for i in range(n):
for j in range(m):
if floor[i][j] == 2: #바이러스가 있는 좌표에 대하여 바이러스 전파
virus(i,j)
# 안전영역의 최대값 계산 (최대값인 경우 업데이트)
result = max(result, count_safe())
return
# 빈공간에 울타리 설치
for i in range(n):
for j in range(m):
if data[i][j] == 0:
data[i][j] = 1
count +=1
dfs(count)
data[i][j] = 0
count -= 1
dfs(0)
print(result)27
hyeeun-techlog