728x90 전체 글129 [JAVA]백준 2618번: 경찰차 www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 1. 문제 설명 (1,1)과 (N, N)에 두 대의 경찰차가 대기하고 있다. 그 후 W개의 사건들의 좌표들이 주어질 때 사건들이 발생한 순서대로 경찰차들이 이동하는 거리의 합의 최솟값을 출력하고 경로를 출력하는 문제이다. 2. 풀이 점화식보다 재귀함수로재귀 함수로 푸는 것이 더 간단해서 재귀 함수로 문제를 풀었다. 재귀 함수의 경우 O(N^2)의 시간복잡도를 가지지만 점화식의 경우 O(N^3)을 가.. 2021. 2. 11. [JAVA]백준 9252번: LCS 2 www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 문제 설명 두 문자열의 최장 공통부분 수열의 길이를 출력하고 최장 공통부분 문자열을 출력한다. 2. 풀이 LCS(최장 공통부분 수열)의 길이를 구하고 역추적하여 최장 공통부분 문자열을 출력하는 문제이다. 혹시 LCS의 길이를 구하는 것부터 막힌다면 아래 문제를 먼저 풀어보는 걸 추천한다. www.acmicpc.net/problem/9251 9251번: LCS.. 2021. 2. 7. [JAVA]백준 14003번: 가장 긴 증가하는 부분 수열 5 www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 1. 문제 설명 수열 A가 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 구하고 가장 긴 증가하는 부분 수열을 출력하는 문제이다. 2. 풀이 가장 긴 증가하는 부분 수열을 푸는 방법에는 여러 가지가 있는데 DP를 이용한 방법과 이분 탐색을 이용한 방법이 있다. DP를 이용하는 방법의 경우 O(N^2)의 시간 복잡도가 걸리고 이분 탐색의 경우 O(NlogN)의 시간 복잡도를 가진.. 2021. 2. 5. [JAVA]백준 12852번: 1로 만들기 2 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. 문제 설명 정수 X에 사용할 수 있는 연산이 3가지가 있다. X/2, X/3, X-1 위의 세가지 연산을 사용하여 주어진 정수 N을 1로 만들려고 할 때 연산을 사용하는 횟수의 최솟값과 1로 만드는 방법을 출력하는 문제이다. 2. 풀이 DP를 이용해서 최솟값을 구하고 그 순간들의 선택을 배열로 저장하여 역추적할 수 있다. dp 배열에는 현재 정수 N을 1로 만들 수 있는 최솟값을 저장하고 trace 배열에는 연산을 사용하였을 때 N 전의 값이 무엇인지 저장한다. X/3 연산을 사용하여 연산 횟수의 최솟값을 구하.. 2021. 2. 5. 이전 1 ··· 15 16 17 18 19 20 21 ··· 33 다음 728x90
