본문 바로가기

전체 글

(45)
[백준 11779: JAVA] 최소비용 구하기 2 / 다익스트라, 역추적 개요 기본적인 최단거리 문제에서 경로 추적이 포함되어 있는 문제이다. 경로의 가중치가 양수이기 때문에 다익스트라를 선택하였고 경로 추적을 위해 부모 노드를 저장하여 풀이하였다. 다익스트라를 잘 모른다면 아래의 문제를 먼저 심도 있게 풀어보는 것이 좋을 것 같다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인..
[백준 9019: JAVA] DSLR / BFS, 역추적 개요 1. BFS를 이용하여 최단거리를 탐색한다. 2. 부모 노드의 값을 저장한다. 3. 연산목록을 구하기 위해 연산배열 정보를 저장한다. 4. 2와 3을 이용하여 연산목록을 역순으로 구한다. 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2..
[백준 13913: JAVA] 숨바꼭질 4 / DP, BFS, 역추적 개요 숨바꼭질 시리즈에서 경로 탐색이 추가된 문제이다. 경로 탐색을 하기 위해서 찾은 경로의 부모 노드를 저장하여 풀이하였다. 동생의 위치에 도달한 경우는 동생의 위치부터 수빈이의 위치가 나올 때까지 loop를 돌며 경로를 탐색한다. 또한, 이때 경로를 stack에 저장하였는데 그 이유는 문제에서 수빈 -> 동생의 경로 순서대로 출력해야 하기 때문에 LIFO 구조가 필요했기 때문이다. 또한, BFS를 이용해서 최단거리를 탐색하였다. 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이..
[백준 12738: JAVA] 가장 긴 증가하는 부분 수열 3/ 이분 탐색 개요 이 문제는 2가지 정도의 풀이가 존재한다. 1. 동적 프로그래밍 2. 이분 탐색 하지만, 이 문제의 입력에서 n의 값이 1,000,000 이기 때문에 이분 탐색으로 풀이하여야 시간 초과를 피할 수 있다. 간단히 설명하자면 우리가 구하고자 하는 증가 수열을 List 자료구조에 저장하고 새로 들어온 값에 대해서 list 안에서의 위치를 찾아 list를 갱신해주는 것이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 풀이 개요에서 말했듯이 이분탐색을 이용해서 수열의 적당..
[백준 14003: JAVA] 가장 긴 증가하는 부분 수열 5/ 이분 탐색+ 역추적 개요 이 문제는 이분 탐색으로 풀이할 수 있다. (dp로는 입력의 최댓값이 너무 커서 시간 초과가 날 것이다.) 시간은 O(nlog(n))이 될 것이다. 사실 이 문제는 기존의 아래 문제에서 경로의 개념만 추가된 것이다. 그러므로 아래의 문제를 먼저 풀어 보는 것을 추천한다. https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 위 문제에서 공통으로 적용되는 이분탐색을 통해 증가수열의 길이를 구하는 것은 아래의 풀이에서..
[백준 14002: JAVA] 가장 긴 증가하는 부분 수열 4/ 동적 프로그래밍 + 역추적 개요 이 문제는 dp와 이분 탐색으로 풀이할 수 있다. 하지만 문제의 입력의 최댓값이 1000이기 때문에 나는 dp로 풀이할 것이다. dp로 풀이할 때는 이전에 구한 값을 통해 풀이하게 된다. 또한 시간은 O(n^2)이 될 것이다. 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 풀이 dp[i] = k → i번째 수열까지의 최대 증가수열의 길이 = k 라고 생각하고 접근하면 된다. 예를 들어 수열 {1, 2, 1, 3, 4, 3}이 주어지고 인덱스가 1부터 시작하여 6까지 ..
[백준 12852: JAVA] 1로 만들기 2 / 동적 프로그래밍 + 역추적 개요 dp를 이용해서 구하며, dp[i] = k → i까지 가는데 걸리는 최소 비용 = k로 배열을 선언하고 풀이하였다. 따라서 점화식은 dp[i] = min(dp[i * 3], dp[i * 2], dp[i + 1]) + 1 이 된다. 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 풀이 1. dp[n] ~ dp[1]까지를 구한다. 2. dp값을 기준으로 (* 2, * 3, +1 이 가능한지) 와 (dp값의 차이가 1인지) 를 확인하며 후보들을 스택..
[백준 2482: JAVA] 색상환 / 동적 프로그래밍 개요 dp로 문제를 풀 수 있다. 이 문제는 dp를 생각하면 금방 풀이할 수 있지만, 약간의 조건이 추가되어 있기 때문에 생각을 좀 해야 했다. 한 칸씩 떨어져 있어야 하고 첫 색과 마지막 색도 떨어져야 하기 때문에 조금 까다로워 보일 수 있다. dp는 일반적으로 이전의 값들을 이용하여 현재 원하는 값을 도출해내는 방식이기 때문에 어떻게 값을 도출해낼지 점화식을 만들어 보면 다음과 같다. 1~n번째까지 색이 있다면, n번째 색을 선택한 경우 + n번째 색을 선택하지 않은 경우로 구할 수 있다. 이걸 생각하고 문제를 풀어보자. 문제 색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교..