728x90 알고리즘118 [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. [JAVA]백준 2602번: 돌다리 건너기 www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 1. 문제 설명 돌다리 2개가 주어지고 마법의 두루마리 문자열이 주어졌을 때 마법의 두루마리 문자열의 순서대로 돌다리를 건너야 한다. 돌다리 건너는 규칙은 네 가지가 있는데 1. 왼쪽에서 오른쪽으로 이동하며, 주어진 마법의 두루마리 문자열에 적힌 순서대로 모두 밟고 가야 한다. 2. 돌다리 2개를 번갈아 가면서 건너야 한다. 3. 건너뛰는 칸의 수는 상관이 없다. 4. 한 칸 이상 오른쪽으로 전진해야 한다. 문자열과 돌다.. 2021. 1. 29. [JAVA]백준 1937번: 욕심쟁이 판다 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 1. 문제 설명 n*n 크기의 대나무 숲이 있을 때 판다가 어떤 지역에서 대나무를 먹는다. 그리고 그다음 지역은 현재 지역보다 대나무가 많이 있는 지역이어야 한다. 그렇지 않으면 판다는 죽는다고 할 때 판다의 최대한 오래 살 수 있는 일수를 구하는 문제이다. 2. 풀이 시작 위치가 정해져 있지 않기에 dfs로 곧장 푸는 것보다는 dfs+dp로 푸는 것이 효율적이다. 현재 위치에서 상, 하, 좌, 우 중.. 2021. 1. 28. 이전 1 ··· 15 16 17 18 19 20 21 ··· 30 다음 728x90
