탐색이란?

  • 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
  • 대표적인 그래프 탐색 알고리즘으로 DFS와 BFS가 있음

스택(Stack) 자료구조

  • 먼저 들어 온 데이터가 나중에 나가는 형식(LIFO, Last In First Out)
  • 입구와 출구가 동일(박스 안에 물건 쌓기)

큐(Queue) 자료구조

  • 먼저 들어 온 데이터가 먼저 나가는 형식(FIFO, First In First Out)
  • 입구와 출구가 다름(터널과 유사)

재귀 함수

  • 재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수

  • 단순한 재귀 함수 예제

    • '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력
    • 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지 출력
def recursive_function():
	print('재귀 함수를 호출합니다.')
    recursive_function()

recursive_function()
  • 따라서 재귀 함수는 종료 조건을 필수로 포함해야 함!
def recursive_function(i):
    	#100번째 호출을 했을 때 종료되도록 종료 조건 명시
        if i == 100:
        	return
            
        print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
        recursive_function(i+1)
        print(i, '번째 재귀함수를 종료합니다.')
        
     recursive_function(1)

팩토리얼 구현 예제

  • n! = 1x2x3x···x(n-1)xn
  • 0! = 1, 1! = 1
def factorial_iterative(n):
 	result = 1
   # 1부터 n까지의 수를 차례대로 곱하기
   for i in range(1, n+1):
   	result *= i
   return result
   
   #재귀적으로 구현한 n!
 def factorial_recursive(n):
 	if <= 1: #n이 1이하인 경우 1을 반환
   	return 1
	#n! = n * (n-1)!를 그대로 코드로 작성하기
   return n * factorial_recursive(n-1) 

최대공약수 계산(유클리드 호제법) 예제

  • 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘
  • 유클리드 호제법
    • 두 자연수 A, B에 대하여(A>B) A를 B로 나눈 나머지를 R이라고 하자.
    • 이때 A와 B의 최대 공약수는 B와 R의 최대공약수와 같다.
def gcd(a,b):
	if a % b == 0:
    	return b
    else
    	return gcd(b, a%b)
print(gcd(192, 162))

재귀 함수 사용의 유의사항

  • 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있음
  • 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있음
  • 재귀 함수가 반복문보다 유리할 수도 있고 불리할 수도 있음
  • 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓임. 그래서 스택을 사용해야 할 때 스택 라이브러리 대신에 재귀 함수를 이용하는 경우도 있음

DFS(Depth-First Search, 깊이 우선 탐색)

  • DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
  • 스택 자료구조(또는 재귀함수)를 이용함
    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
    2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
    3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복







# 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)
 
 # 각 노드가 연결된 정보 표현
 graph = [
 	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
 ]
 #  각 노드가 방문된 정보를 표현
 visited = [False] * 9
 
 # 정의된 dfs 함수 호출
 dfs(graph, 1, visited)

BFS(Breadth-First Search, 너비 우선 탐색)

  • BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘
  • BFS는 큐 자료구조를 이용
    1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
    2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
    3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복






from collections import deque

#BFS 메서드 정의
def bfs(graph, start, visited):
	#큐 구현을 위해 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
                
#각 노드가 연결된 정보를 리스트 자료형으로 표현
graph = [
	[],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
 ]
 
#각 노드가 방문된 정보를 리스트 자료형으로 표현
visited = [False] * 9

bfs(graph, q, visited)

문제 1



# 입력 받음
N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]

count = 0

# DFS로 특정 노드를 방문하고 연결된 노드들 방문
def dfs(x, y):
  # 주어진 범위를 벗어나는 경우에는 즉시 종료
  if x <= -1 or x >= N or y <= -1 or y >= M:
    return False
  # 현재 노드를 아직 방문하지 않았다면
  if graph[x][y] == 0:
    # 해당 노드 방문 처리
    graph[x][y] = 1
    # 상, 하, 좌, 우의 위치 재귀 호출
    dfs(x - 1, y)
    dfs(x, y - 1)
    dfs(x + 1, y)
    dfs(x, y + 1)

    return True
  return False


for i in range(N):
  for j in range(M):
    if dfs(i, j) == True:
      count += 1

print(count)

문제 2

예시 답안)

어렵다...

참고 : https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3

0개의 댓글