그래프 탐색 알고리즘(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..
https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 움직임을 x, y 좌표평면으로 표현할 수 있다. 오른쪽 한칸 : y가 1 증가 (0, +1) 아래로 한칸 : x가 1 증가 (+1, 0) 좌하단으로 한 칸 : x가 1 증가, y가 1 감소 (+1, -1) 우상단으로 한칸 : x가 1 감소, y가 1 증가 (-1, +1) 시작 위치는 1/1로 (1,1)로 표시할 수 있다. 움직이는 방향을 표시하기 위해 mx, my 변수를 사용하여 위 움직임에 해당하는 값을 대입했다. 처음에는 우상단으로 움직이게 했으며(이를 위해 mx에는 -1, my에는 1을 초기값으로 주었다.) 좌표평면 범위(..
문제 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;..
더보기 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // N을 입력받기 int n = sc.nextInt(); sc.nextLine(); // 버퍼 비우기 String[] plans = sc.nextLine().split(" "); int x = 1, y = 1; // L, R, U, D에 따른 이동 방향 int[] dx = {0, 0, -1, 1}; int[] dy = {-1, 1, 0, 0}; char[] moveTypes = {'L', 'R', 'U', 'D'}; // 이동 계획을 하나씩 확인 for (int i = 0; i < pla..
