코테, 코딩 테스트 재귀 함수(DFS, BFS활용) 정리 - [재귀함수/알고리즘]

재귀 함수

정의한 함수안에 정의한 함수를 다시 호출하는 방식

재귀함수를 사용하려면 반드시 함수내의 종료조건을 명시해줘야함 

def test_recursive(i):
	# 종료되는 조건을 반드시 추가해야 종료됨
    if i == 10:
    	return
    
    print("재귀함수")
	test_recursive(i+1)

예를들어 백준문제 N-Queen문제같이 백트래킹 문제풀때 활용

9663 문제 python N-Queen [백준-골드4/백트래킹]

유클리드 호제법 예제

두 수의 최대공약수를 구하는 알고리즘

A, B 두 수에서 큰수에서 작은수를 나누어서 0이 될 때 까지 반복

Ex. 245, 189 두 수의 최대공약수

189 / 245 몫 : 1, 나머지 : 56

56 / 189 몫 : 3, 나머지 : 21

56 / 21 몫 : 2, 나머지 : 14

21 / 14 몫 : 1, 나머지 : 7

14 / 7 몫 : 2, 나머지 : 0 

최대 공약수는 7

코드

조건

- A에서 B를 나눴을 때 나머지가 0이면 return B를 하여 탈출

-  A, B 대소관계를 통해 재귀함수를 호출할 때 위치를 변경

def mod(a, b):
    print(a,b)
    if a % b == 0:
        return b
    
    if a > b:
        a = a % b
        # A에 더 작은값이 들어가서 위치를 바꿔줌
        return mod(b, a)
        
    elif a < b:
        b = b % a
        return mod(a, b)

print(mod(189, 245))

DFS(깊이 우선 탐색)

깊은 부분을 우선적으로 탐색하는 알고리즘

트리의 경우

그래프의 경우 

그래프는 방문할 때 방문하는 기준에 따라서 인접한 노드가 어디로 갈지 정한다고 한다.
Ex. 더 작은 숫자순으로 방문 or 더 큰 숫자 or 알파벳 순으로 방문

코드

문제를 풀 때 그래프를 어떻게 문제의 의미에 맞게 순서를 조정하는지가 중요할듯 

dic = {
    1:'A',
    2: 'B',
    3: 'C',
    4: 'D',
    5: 'E',
    6: 'F',
    7: 'G',
    8: 'H',
    9: 'S',
}


def dfs(graph, v , visitied):
    visited[v] = True
    print(dic[v], end =' ')
#     print(visitied)
    
    for i in graph[v]:
    	# 방문 안한곳이면, False일때 조건문 
        if not visited[i]:
            dfs(grpah, i, visited)
            


# 그래프 안의 값을 문제의 기준에 따라 정렬
# Ex. S의 인접노드가 [1,3,7]일때 기준은 알파벳순 순서먼저 방문이기 때문에
# 1은 이미 방문했고, 3은 방문안해서 3을 먼저 방문
# 만약 기준이 알파벳 역순일 경우 [7,3,1]로 7을 먼저 방문할 것임
grpah = [
    [],
    [2,9], #A
    [1], # B
    [4,5,6,9], #C
    [3], #D
    [3,8], #E
    [3,7], #F
    [6,8,9], #G
    [5,7], #H
    [1,3,7], # S
]

visited = [False] * len(grpah)
dfs(grpah, 1, visited)

BFS(너비 우선 탐색)

가까운 노드부터 우선적으로 탐색하는 알고리즘

그래프의 경우

노드를 탐색하는 조건은 알파벳순으로 너비우선탐색 

A -> B -> S -> C -> G -> D-> E-> F-> H

코드

from collections import deque

dic = {
    1:'A',
    2: 'B',
    3: 'C',
    4: 'D',
    5: 'E',
    6: 'F',
    7: 'G',
    8: 'H',
    9: 'S',
}

def bfs(graph, start, visited):
    # 최초 큐 생성
    queue = deque([start])
    visited[start] = True
    
    # 큐가 비어있을 때까지 반복
    while queue:
        v = queue.popleft()
        print(dic[v])
        
        for i in graph[v]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True
        
    
grpah = [
    [],
    [2,9], #A
    [1], # B
    [4,5,6,9], #C
    [3], #D
    [3,8], #E
    [3,7], #F
    [6,8,9], #G
    [5,7], #H
    [1,3,7], # S
]

visited = [False] * len(grpah)
bfs(grpah, 1, visited)

 

깨달은점

평소에 개발할땐 재귀함수 안쓰다... 코테준비하니까 재귀함수를 응용하는 문제들이 너무 빈번하게 등장해..어떻게 쓰는지 조금 익숙해질 필요가 있는거 같다.  최근에 NC와 컴투스 두 기업에 인턴지원할겸 코테를 봤는데 힙정렬 알고리즘을 그대로 적용하는 문제가 나왔다. DFS, BFS도 안보고 그냥 짤 수 있을정도로 숙지하고 문제에 적응하는 방법을 늘려놔야 나중에 코테볼때 편할거같다.