문제 1 더보기 import java.util.*; public class Main { // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 public static int[] d = new int[100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 정수 N을 입력받기 int n = sc.nextInt(); // 모든 식량 정보 입력받기 int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) d[0] = arr[0]; d[1] = Mat..
다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(Top Down, Bottom Up)으로 구성된다. 동적 계획법이라고 부른다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 피보나치 수열 피보나치 수열은 아래와 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계..
1. 떡볶이 떡 만들기 답안 예시 더보기 import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 떡의 개수(N)와 요청한 떡의 길이(M) int n = sc.nextInt(); int m = sc.nextInt(); // 각 떡의 개별 높이 정보 int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // 이진 탐색을 위한 시작점과 끝점 설정 int start = 0; int end = (int) 1e9;// 십억 // 이진 탐색 수행 (반복적) int resu..
이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 이진 탐색 동작 예시 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2N에 비례한다. 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다. 2단계를 거치면 8개가량의 데이터만 남는다. 3단계를 거치면 4개가량의 데이터만 남는다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다. 이진 탐색 소스..
1. 음료수 얼려 먹기 답안 예시 더보기 import java.util.*; public class Main { public static int n, m; public static int[][] graph = new int[1000][1000]; // DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문 public static boolean dfs(int x, int y) { // 주어진 범위를 벗어나는 경우에는 즉시 종료 if (x =n || y = m) { return false; } // 현재 노드를 아직 방문하지 않았다면 if (graph[x][y] == 0) { // 해당 노드 방문 처리 graph[x][y] = 1; // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출 dfs(x - ..
BFS(Breadth-First Search) BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐 자료구조를 이용하며, 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. BFS 동작 예시 BFS 소스코드 예제 from collections import deque # BFS 함수 정의 def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque([start]..
