문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 어떻게 풀 것인가? 처음에는 보석과 가방이라는 문제만 보고 배낭(Knack) 알고리즘 문제인줄 알았으나, 문제를 풀다보니 아닌 것을 알았다. 나는 정렬과 우선순위 큐를 이용하여 문제를 풀었다. 보석의 경우 문게로 내림차순 정렬을 하고 무게가 같을 경우 오름차순으로 정렬하고 가방은 무게를 기준으로 오름차순을 정렬하였다. 각 가방의 무..
문제 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 어떻게 풀 것인가? 문제를 처음 봤을 때 가장 먼저 DP가 떠오르긴했다 다만, 문제는 떠오른다고 풀릴리가 없다는 것이 DP문제 아닐까.... 그래서 문제를 차근차근 다시 읽어보니 우선적으로는 배낭 문제가 떠올랐다. 사실 그래서 얼마 전에 정리한 배낭 문제에 대한 포스팅을 다시 읽으며 문제를 해결했다. (이는 아래 참고에 블로그 링크를 걸어 두었다.) 자 배낭문제는 조합 최적화(Combination ..
문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 어떻게 풀 것인가? 처음에는 단순 그리디 방식으로 접근했다. 하지만 그렇게 했다가는 시간초과가 발생한다. 문제를 보자. 시간 제한은 0.5초이다. 자 이렇게 시간제한이 빡빡하다는 것은 DP로 접근해야함이다. 그렇다면 DP 배열에 무엇을 넣어야할까? 점화식 수식을 넣어야한다. 그렇다면 점화식은 무엇을 넣어야 하는가? 이 문제에서 원하는 것은 가장 적게 연산하여 1을 도출하는 것이다. 그렇다. 점화식을 생각해본다면 dp[i] = min(dp[i / 3], dp[i / 2], dp[i - 1]) (i ..
문제 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 어떻게 풀 것인가? 문제를 처음 읽었을 때는 어떠한 문제를 파악하는지 꽤나 오랜 시간이 걸렸다. 하지만 주어진 문제의 출력 부분을 보고는 백트래킹을 이용한 중복 조합 문제를 생각했다. 조합과 순열은 수학적인 부분이지만 조합을 실제 코드로 구현한 부분에서 visited 부분을 제거한다면, 중복조합이 됨을 알 수 있다. 아래에 링크에 남겨두었지만, 저 코드를 그대로 사용한다면, 시간 초과가 발..
문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 어떻게 풀 것인가? 문제를 처음에 보자마자 DP가 떠오르긴 하였다. k-1 길이의 오르막 수에서 마지막 수보다 크거나 같은 수를 이어 붙이면 길이가 k인 오르막 수를 구할 수 있다. 예를 들어서, 123 -> 1233, 1234, ..., 1239 이렇게 수의 길이 k에 대해 직전 항으로 다음 항을 만들 수 있으므로 다이나믹 프로그래밍으로 문제를 해결할 수 있다. 길이 k와 마지막 자리 숫자 i로 ..
문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 어떻게 풀 것인가? 문제에서 주어진 그림과 같이 8방향에 대하여 BFS 탐색을 진행하면서 목적지에 도달하면 즉시 bfs에서 result값을 저장하고 리턴한다. 풀면서 놓쳤던점 X 이 문제를 통해 얻어갈 것 BFS의 다양한 방향 탐색 내 코드 import java.lang.StringBuilder import java.util.* // 백준알고리즘 7562번 나이트의 이동 private var ..
문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 어떻게 풀 것인가? 문제를 찬찬히 읽어보자. 2가지의 방법이 떠오른다. 1. 브루트 포스, 2. 백트래킹 여기서 시간복잡도를 떠올려보자. 연산자는 4개이고, 주어질 수 있는 수는 10개이다. 4^10 = 1,048,576 즉, 아무리 최악이어도 1초는 넘기지 않는다. 그래서 브루트 포스보다는 백트래킹을 연습하기 위해서 백트래킹으로 접..
문제 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 어떻게 풀 것인가? 주어진 수 대로 두 학생의 키를 비교하면 된다. 즉, 주어진 예제의 정답처럼 답이 나오지 않더라도, 순서만 맞다면 정답이 처리된다. 학생이 각각 노드라고 생각하고 주어진 조건을 간선이라고 생각한다면 위상정렬로 문제를 풀어야 한다. 다른 분들의 풀이를 참고하니 단순 배열이나 리스트를 이용한 정렬을 이용하면 시간초과가 발생한다고 한다..
