나그네

9252번: LCS 2 문제 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 9251번 LCS의 확장 버전이다. LCS의 길이를 구하는 풀이는 아래 링크를 참고하길 바란다. https://khyunx.tistory.com/57 [백준 / BOJ] C++ 9251 LCS 9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Lon..

9251번: LCS 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 입력된 두 문자열을 비교하면서 LCS(최장 공통 부분 수열)의 길이를 찾는 문제. 가능한 모든 경우의 수를 확인하면 시간초과가 나기 때문에 dp를 이용해 풀어야 한다. 예제를 통해 설명을 해보자. 비교하는 두 문자열은 "ACAYKP"와 "CAPCAK"다. 최장 공통 부분 수열은 "ACAK"로 길이는 4다. 0 A C A Y..

1149번: RGB거리 문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 칠해야 하는 집의 수 N이 주어진다. 이후 각 집에 대하여 빨강, 초록, 파랑으로 칠했을 때의 비용이 한 줄에 주어진다. i번째 집의 색은 i-1, i+1번째 집의 색과는 달라야 한다. 조건에 맞게 모든 집을 칠했을 때 비용의 최솟값을 구하는 문제다. dp를 사용해 풀 수 있다. dp[1001][3] 크기의 0으로 초기화된 이중 배열을 만든다..

2565번: 전깃줄 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 두 전봇대에 선이 겹치지 않게 가장 많이 연결할 수 있는 전깃줄의 수를 구하는 문제다. 두 전봇대를 A와 B라고 하면 A 전봇대의 연결되는 위치를 기준으로 오름차순으로 정렬한다. 그리고 B 전봇대에 연결되는 위치가 가장 긴 증가하는 부분 수열(LIS)이 되도록 구하면 연결 가능한 전선의 수를 알 수 있다. 전체 전깃줄의 수에서 연결 가능한 전선의 수의 최댓값을 빼면 답을 구..

11722번: 가장 긴 감소하는 부분 수열 문제 https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열(LIS)의 변형이다. 아래 링크의 풀이에서 이전 원소들 중 작은 값이 아니라 큰 값을 찾으면 된다. https://khyunx.tistory.com/27 [백준 / BOJ] C++ 11053 가장 긴 증가하는 부분 수열 11053번: 가장 긴..

11053번: 가장 긴 증가하는 부분 수열 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열 LIS(Longest Increasing Subsequence)를 이용한 문제다. O(N^2)가 걸리는 dp를 사용한 풀이로 풀린다. dp는 해당 index에서 끝나는 가장 긴 증가하는 부분 수열을 의미한다. 모든 수는 길이가 1인 증가하..

9461번: 파도반 수열 문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 한 변의 길이가 1인 정삼각형으로 시작해 도형의 가장 긴 변의 길이를 한 변의 길이로 하는 정삼각형을 추가해가며 N번째 정삼각형의 한 변의 길이를 P(N)이라 하고 이를 출력하는 문제. 1번 풀이 P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 라는 문제 본문을 읽고 가장 먼저 [1, 1, 1]로 시작하며 i번째 ..

11660번: 구간 합 구하기 5 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 2차원 배열에서 (x1, y1)부터 (x2, y2)의 합을 출력하는 문제다. 가장 먼저 떠오른 생각은 행 별로 누적 합(prefix sum)을 먼저 구하는 것이었다. 이후 x1, y1, x2, y2를 입력받고 각 행별로(x1, ... , x2) 열의 누적 합(sum[y2] - sum[y1 - 1])을 답에 더해..

1003번: 피보나치 함수 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 규칙을 찾는 것이 중요한 문제다. N 0의 횟수 1의 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 여기서 0의 횟수와 1의 횟수를 각각 살펴보면 0의 횟수: 1, 0, 1, 1, 2, ... 1의 횟수: 0, 1, 1, 2, 3, ... 이므로 각각은 1, 0으로 시작하는 피보나치 수열과 0, 1로 시작하는 피보나치 수열이다. 따라서 각각에 대한 피보나치 수열을 구하는 문제다. 코드 #include using namespace std; int..