DFS(Depth-First Search) 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. DFS 동작 예시 DFS 소스코드 예제 # DFS 함수 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현..
재귀 함수(Recursive Function) 자기 자신을 다시 호출하는 함수 단순한 형태의 재귀 함수 예제 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다. 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다. # 파이썬 def recursive_function(): print('재귀 함수를 호출합니다.') recursive_function() recursive_function() class Main { static void recursive_function() { System.out.println("재귀 함수를 호출합니다."); recursive_function(); } public static void main(String[] args) { recursive_function(); ..
그래프 탐색 알고리즘(DFS/BFS) 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘으로는느 DFS와 BFS가 있다. DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. DFS와 BFS에 대해 알아보기 전에 반드시 알고 가야 할 자료구조 두 가지가 있다. 스택 자료구조 먼저 들어 온 데이터가 나중에 나가는 형식(후입 선출, LIFO)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. 스택 동작 예시 삭제 시 마지막에 들어왔던 7이 나간다. 스택 구현 예제 import java.util.*; public class Main { public static void main(String[] args) { Stack..
문제 1 더보기 Python n, k = map(int, input().split()) # N과 K를 입력 받기 a = list(map(int, input().split())) # 배열 A의 모든 원소를 입력받기 b = list(map(int, input().split())) # 배열 B의 모든 원소를 입력받기 a.sort() # 배열 A는 오름차순 정렬 수행 b.sort(reverse=True) # 배열 B는 내림차순 정렬 수행 # 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교 for i in range(k): # A의 원소가 B의 원소보다 작은 경우 if a[i] < b[i]: # 두 원소를 교체 a[i], b[i] = b[i], a[i] else: # A의 원소가 B의 원소보다 크..
선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 탐색 범위는 반복할 때마다 줄어든다. 가장 작은 데이터를 찾기 위해 탐색 범위 내에서만 확인한다. 이중 반복문을 통해 선택 정렬을 구현할 수 있다. 더보기 Python array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # 스와프 prin..
문제 1 더보기 import java.util.*; public class Main { // 특정한 시각 안에 '3'이 포함되어 있는지의 여부 public static boolean check(int h, int m, int s) { // h의 10의 자리는 0,1,2 밖에 없으므로 확인할 필요 없음 if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3) return true; return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); // H를 입력받기 int h = sc.nextInt(); int cnt = 0;..
