problem solving18 [ps 팁] 재귀는 마치 누군가가 종이에 숫자를 쓰고, 그 종이를 다음 사람에게 넘겨주는 방식과 같다 아래의 코드를 보면 DFS여서 매번 재귀할 때마다 함수 첫 번째 줄부터 다시 시작하는데저렇게 int cnt = 1;해 버리면 카운트를 하다가도 계속 1로 초기화되는 거 아닌가..? 처음엔 그렇게 보일 수도 있지만, 재귀 함수에서는 각 함수 호출마다 자신만의 지역변수 스코프(scope)를 가지기 때문에int cnt = 1;이거는 그 호출된 함수 하나에만 국한되는 초기화다private static int dfs(int V) { visited[V] = true; int cnt = 1; // 자기 자신 포함 for (int next : graph[V]) { if (!visited[next]) { cnt += dfs(next); // 재귀 호출 결과 누적 .. 2025. 3. 25. [ps 팁] 그래프 순회는 무조건 인접 리스트로 구현하는 게 유리할까? 결론부터 먼저 말하면..간선 리스트: MST 크루스칼 알고리즘인접 행렬: 최단 거리 플로이드-와샬 알고리즘인접 리스트: 그 외의 모든 것들!! 그냥 모든 ps 문제들은 인접 리스트로 구현하는 게 맞을까?틀리다! 각각의 구현 방식들에는 장단점들이 분명해, 올바르게 선택해야 좋은 효율을 낼 수 있다.https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep5-1-%EA%B7%B8%EB%9E%98%ED%94%84graph [알고리즘] ep5-1) 그래프(graph)ㅁ그래프(graph) ADT: (vertex, edge)의 쌍v: 정점 노드들의 집합e: 간선 노드들의 집합 정점: 공항을 표현하며 공항도시 이름을 저장간선: 두 공항 .. 2025. 3. 24. [ps java] BOJ 12865 평범한 배낭 해설 웰-노운 배낭(냅색) 문제이다 [골드5]https://www.acmicpc.net/problem/12865 [부분적 배낭 문제(the fractional knapsack problem)] - 각 항목의 일부만을 취할 수 있는 문제흔히 ps에서 "냅색"이라 말한다 구성: n항목의 집합 S- bi: 양수의 이득- vi: 양수의 부피목표: 최대 부피 한도 V내에서, 최대의 총이득을 주는 항목들을 선택32 + 15 = 47 0-1 배낭 문제(all-or-nothing knapsack problem) - 각 항목의 일부만을 취할 수 없는 문제0-1 배낭 문제는 탐욕적 선택 속성을 만족하지 않는다 >> DP로 해결 최적해는 이득 = 36 을 가져다주는 {A, E}지만, 탐욕해는 이득 = 24 를 가져다주는 {B.. 2025. 3. 18. [ps java] BOJ 9251 LCS 해설 LCS 웰-노운 DP 문제이다 [골드5]자주 쓰이는 곳이 많으니, 완벽히 숙지하자!https://www.acmicpc.net/problem/9251 LCS(Longest Common SubSequance): 최장 공통 부분 수열 문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 1ACAYKPCAPCAK예제 출력.. 2025. 3. 18. [ps java] BOJ 9465 스티커 해설 조금 생각해봐야 하는 DP 문제이다 [실버1]2개의 dp를 돌려야만 풀 수 있는 좋은 문제! https://www.acmicpc.net/problem/9465 문제상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스.. 2025. 3. 17. [ps java] BOJ 11053 가장 긴 증가하는 부분 수열 해설 LIS(Longest Increasing Subsequence)를 학습할 수 있는 웰-노운 DP 문제다! [실버2]https://www.acmicpc.net/problem/11053 문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.예제 입력 1610 20 10.. 2025. 3. 11. [ps java] BOJ 1149 RGB 거리 해설 DP를 학습할 수 있는 좋은 문제다! [실버1]https://www.acmicpc.net/problem/1149 문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초.. 2025. 1. 31. [ps java] BOJ 1912 연속합 해설 (카데인 알고리즘) DP를 학습하기 좋은 웰-노운 문제이다 [실버2] https://www.acmicpc.net/problem/1912 문제n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 11010 -4 3 1 5.. 2025. 1. 31. [ps java] 재귀 -> DP 변환 예시 코드(BOJ 9184) https://www.acmicpc.net/problem/9184재귀를 DP로 바꾸는 문제이다 [실버2]재귀 호출만 생각하면 신이 난다! 아닌가요? 아래와 같은 재귀 호출 알고리즘 코드가 있다하지만 a b c 에 15 15 15 만 입력하더라도 실행하는 데에 너무 많은 시간이 걸린다따라서 우리는 아래의 코드를 DP로 변형해 볼 것이다import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); whi.. 2025. 1. 19. 이전 1 2 다음
