두부의 코딩일기

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 N가지 종류의 동전이 주어지면 동전을 최대한 적게 사용해서 K원을 만들어라. 다이나믹 프로그래밍(dp) 문제로 아래의 조건만 신경써주면 딱히 어려운 게 없는 문제라고 생각한다. 1️⃣ 각각의 동전을 여러 개 사용할 수 있음 2️⃣ 정확하게 K원을 만들지 못 하면 -1을 출력함 예제로 점화식을 찾아보겠다. 1원 동전 1 2 3 4 5 6 7 8 ..

https://www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 해당 문제는 다이나믹 프로그래밍(dp)로 문제의 조건은 아래와 같다. 1️⃣ 파이프는 하나씩 사용이 가능하고, 수도배관 길이는 강까지의 거리(D)와 동일해야 한다. 2️⃣ 수도배관을 완성했을 경우, 가장 적은 용량을 가진 파이프가 해당 수도배관의 용량이다. 3️⃣ 동일한 길이를 가진 여러 개의 수도배관 중에 가장 큰 용량을 구하라. 파이프의 길이를 정확하게 강까지의 거..

최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 정의 주어진 수열에서 원소들의 순서를 유지하면서 증가하는 가장 긴 부분 수열을 찾는 알고리즘으로 별도로 정렬이 필요 없다. 위 그림은 주어진 배열에서의 증가하는 부분 수열을 나타낸 예시로 최장 증가 부분 수열(LIS)은 두 번째로 보이는 그림이다. 최장 증가 부분 수열 작동 원리 최장 증가 부분 수열을 찾기 위해서는 다이나믹 프로그래밍(dp)을 사용해야 된다. dp[i]는 i번째 수를 마지막 원소로 가지는 최장 증가 부분 수열의 길이다. i번째의 LIS 길이를 구하는 방법은 0부터 i-1번째까지의 값에서 i번째 수보다 값이 작고 dp값이 가장 큰 값의 +1이다. 위의 그림으로 예제를 보겠다. arr 배열에 첫 번째 ..

https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net ✅ 골드 Ⅳ 🔶 풀이 N x M 크기의 고급 나무 재료가 주어졌을 때, 'ㄱ'자 모양 부메랑들의 강도 합이 최댓값을 구하라. N과 M의 크기가 작으므로 완전 탐색으로 해결할 수 있다. 우선 백트래킹을 사용하기 위해서 dfs를 이용한다. idx를 0부터 순차적으로 늘리면서 좌표값 (x, y)를 제어해 줬다. int x = idx/M; int y = idx%M; idx가 N*M에 도..

https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net ✅실버 Ⅳ 🔶 풀이 굴다리 길이(N)와 가로등 개수(M), 가로등 설치 위치가 주어지고, 굴다리의 모든 곳을 비추어라. 가로등 높이가 1 증가할 때마다 길이 1만큼 더 주위를 비출 수 있다. 이분 탐색을 이용해서 가로등의 적정 높이를 찾아주면 된다. 가로등의 높이를 기준으로 굴다리의 모든 곳을 비출 수 있는지 확인하면서 가능하다면 최댓값(right)를 mid-1로, 불가능하다면 최솟값(left)를 m..

플로이드-워셜 (Floyd-Warshall) vs 다익스트라 (Dijkstra) 다익스트라 플로이드-워셜 사용 목적 단일 출발점 최단 경로를 찾음 모든 정점 쌍 간의 최단 경로를 찾음 가중치 제약 음의 가중치를 가진 간선을 처리할 수 없음 음의 가중치를 가진 간선을 처리할 수 잇음 기본 구조 그래프의 인접 리스트 혹은 인접 행렬을 사용함 그래프의 인접 행렬을 사용함 시간 복잡도 O(V+E)logV (우선 순위 큐를 사용했을 경우) O($N^{3}$) 알고리즘 유형 그리드 알고리즘 동적 프로그래밍 플로이드-워셜 개요 플로이드-워셜은 a → b 로 가는 비용과 a → c → b 로 가는 비용 중에 더 적은 값을 최단 거리로 판단하는 알고리즘으로 다음과 같은 점화식을 가진다. dpab= Math.min(dpa..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net ✅ 실버 Ⅰ 🔶 풀이 N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하시오. 다이나믹 프로그래밍 문제다. 예제 2번으로 규칙을 찾아보겠다. 카드팩은 총 5개이고, 카드 5개를 구매하기 위해 지불해야 하는 최대 금액을 찾으면 된다. P1 = 10, P2 = 9, P3 = 8, P4 = 7, P5 = 6 card[1] = 10, card[2] = 9, card[3] = 8, card[4] = ..

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net ✅ 골드 Ⅴ 🔶 풀이 최소 한 개의 모음과 두 개의 자음으로 구성된 길이 L의 암호를 출력하라. 백트래킹으로 풀어야 된다. 해당 문제에서는 알파벳이 증가하는 순서로 배열되었을 것이라고 한다. 정렬은 필수다. 우선, 이미 선택한 알파벳보다 큰 알파벳을 선택해서 임의의 L 길이를 가진 암호를 만든다. L 길이가 완성됐다면 최소 모음 1개, 자음 2개를 가지고 있는지 판단해 준다. public static ..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ✅ 골드 Ⅲ 🔶 풀이 각 각의 마을에서 파티가 열린 마을 X를 방문했다가 다시 돌아왔을 때 가장 많이 시간을 소비한 학생을 구하라. 모든 가중치가 양수이고, 한 정점에서 다른 모든 정점까지의 최단 거리를 구해야하므로 다익스트라. 다익스트라를 두 번 나누어서 해결했다. 1. X에서 각 마을까지의 최단 거리 2. 각 마을에서 X까지의 최단 거리 (역방향) 위 두가지를 구..

세그먼트 트리(Segment Tree)의 필요성 특정 구간 내 쿼리를 효율적으로 처리하기 위한 자료구조다. ✅ 구간 쿼리 : 배열 또는 리스트와 같은 시퀀스 데이터에서 특정 구간에 대한 정보를 검색하거나 수정하는 작업을 말한다. 위와 같이 arr[50]의 배열이 있다고 가정했을 때, arr[3] ~ arr[10]까지의 합을 구하고, 특정 값을 변경하려는 행위가 필요하다고 가정해보자. 1. 단순 반복문을 통한 덧셈 연산 이 방법은 O(N)의 시간복잡도를 가지고 있으며, 이를 M번 수행한다고 가정한다면 O(NM)의 시간복잡도를 가지게 된다. 특정 값 A → B로 변경하는 것은 O(1)의 시간복잡도를 가지고, 이를 M번 수행한다면 O(M)의 시간복잡도를 가진다. ▶ 시간복잡도: O(NM) + O(M) = O(..