반응형 코딩테스트 준비219 최단 경로 알고리즘 총 정리(다익스트라,벨만-포드 알고리즘,A*알고리즘) 최단 경로 알고리즘이란?어떻게 하면 가정 적은 비용으로 목적지에 도착할 수 있을까?를 생각하는 알고리즘이다.1. 다익스트라 알고리즘(Dijkstra Algorithm)하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 단 모든 간선의 가중치는 0보다 크거나 같아야 한다.이 알고리즘의 핵심은 지금 까지 찾은 가장 짧은 길을 기억하고 그걸 이용해서 다음 길을 더 쉽게 계산하는 것이다. 즉 지금까지 찾은 가장 짧은 길을 계속 저장해두고 DP처럼 기존에 구한 결과를 재활용한다. 01 작동 과정distance[] ← ∞, distance[start] ← 0visited[] ← false반복: 현재 노드 ← 방문 안 한 노드 중 최소 distance 인접 노드의 거리 갱신 .. 2025. 4. 17. 백준 C# - 2225 +) 풀이 문제0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다.여기서 중요한 부분은 "0"부터 포함된다는 것이다. 그러므로 정수 1개로 0을 만드는 경우의 수도 1가지 존재한다. k = 사용할 정수의 개수n = 목표 합계 점화식 생각1. dp[k,n] 배열에 어떤 값을 넣을까?dp[k,n] = 정수 k개로 합이 n이 되는 경우의 수이다.2. i를 만들기 위해 바로 전 단계는 뭘까?1) 마지막 수가 0인 경우 2) 마지막 수가 1이상인 경우점화식dp[k,n] = dp[k-1,n] + dp[k,n-1];1) dp[k-1,n]정수 k개 중 하나가 0일때 나머지 k-1개로 n을 만들어야한다.2) dp[k,n-1]합이 n이 되도록 정수 k개를 만드려면 합이 n-1인 경우에 +1씩 해서 .. 2025. 4. 16. 탐색 알고리즘 총 정리(선형,이진탐색,해시탐색) 탐색 알고리즘이란탐색 알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법 01 선형 탐색(Linear Search)처음부터 끝까지 하나씩 비교하면서 찾는 방식int LinearSearch(int[] arr, int target){ for (int i = 0; i 시간복잡도최악 : O(N)최선 : O(1)02 이진 탐색(Bineary Search)정렬된 배열에서 중간값과 빅하며 절반씩 범위 줄이기조건 : 오름차순 or 내린차순으로 정렬된 데이터여야 한다.int BinarySearch(int[] arr, int target){ int left = 0, right = arr.Length - 1; while (left 시간복잡도 O(logn)03 해시 탐색(Hashing)키(key)를 해시.. 2025. 4. 16. 백준 C# - 1699 +) 풀이 문제정수 n이 주어졌을때 n을 제곱수들의 합으로 표현하는 방법 중에서 항의 개수가 최소인 경우의 수를 구해야한다.예시12 = 4 + 4 + 413 = 9 + 4 점화식 생각01 dp[] 배열에 어떤 값을 넣을까?i를 만들기 위한 최소 제곱수들의 합으로 표현할 때 필요한 항의 수02 i를 만들기 위해 바로 전 단계는 뭘까?이미 dp[i-j*j]값을 알고있음 그래서 이번 값에서 + 1그래서 나온 점화식dp[i] = min(dp[i-j²]+1) (단 j²예시) n = 5- dp[1]가능한 j: 1 (1²)dp[1] = min(dp[1], dp[1 - 1] + 1) = min(∞, dp[0] + 1) = 1dp[1] = 1- dp[2]가능한 j: 1 (1²)j=1: dp[2] = min(dp[2], dp[1] .. 2025. 4. 16. 백준 C# - 14002 +) 풀이 문제를 읽어보면입력이 1000이니까 1000*1000 = 1000000(백만)이므로 O(N²) 알고리즘으로도 이 문제는 충분히 통과 가능하다. 알고리즘01 문제 분석가장 긴 증가하는 부분수열 거의 동일하지만 한 가지 추가된 조건이 있다.단순히 수열의 길이만 구하는 것이 아니라 그 실제 수열의 내용도 출력해야한다. 02 경로 복원(Path Reconstruction)그 값을 만들기 위해 어떤 선택을 했는지를 저장해서 실제해를 구성할 수 있게 하는 방법이다. 경로 복원에 대한 정보 저장 - prev 배열prev[i] = dp[i]를 만들기 위해 선택된 이전 인덱스, 즉 dp[i]가 dp[j]+1로 갱신되었으면 prev[i] = j를 저장하는 것이다.10 20 10 30 20 50ilist[i] dp[i]pr.. 2025. 4. 11. 백준 C# - 15990 +) 풀이 문제 설명정수 N을 1,2,3 합으로 표현하는 방법의 수 조건 : 같은 수를 연속으로 두 번 이상 사용하면 안된다."1 + 1 + 2" ❌"1 + 2 + 1" ✅조건이 없는 경우 (연속된 숫자가 올 수 있는 경우) 백준 C# - 9095 +)풀이DP를 이용해서 풀어야한다. DP알아보러 가기 C# - 다이나믹 프로그래밍(DP) 다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 최적화 기법중 하나이다. 큰 문제를 작code-piggy.tistory.com점화식dp[n] = dp[n-1] + dp[n-2] + dp[n-3]조건이 있는 경우(연속된 숫자가 올 수 없는 경우)마지막 숫자만 확인하여 겹치게만 안하면 된다는 것이다. 다른말로 마지막 숫자만 체크하면 된다. dp[n][1] .. 2025. 4. 10. 이전 1 2 3 4 ··· 37 다음 반응형
