Let's Begin Programming

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제 역시 혼자 풀지 못하고 다른 분들의 글을 참고했다. 다이나믹 프로그래밍 문제들은 간단해보이지만 다이나믹 프로그래밍을 이용해야겠다는 생각과 어떤 식으로 해결 방법을 구성할 지가 답을 보고도 쉽게 이해되지 않는다. 두 문자열을 비교해서 같은 부분 문자열의 최대 길이를 찾는 문제이다. 이전에 풀었던 증가하는 부분 수열 문제와 비슷하다고 생각해서 문자 하나씩 확인하..

개발 공부 (알고리즘) 2021. 4. 15. 03:45

www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 감이 안 와서 다른 분들의 블로그를 참고했다. 결과적으로 이전에 했던 가장 긴 증가하는 부분수열을 구하는 방법을 이용하면 됐다. 문제는 전깃줄이 겹치지 않도록 전깃줄을 제거하는 최소 갯수를 구하는 것이다. 주어지는 전깃줄 정보가 순서대로 주어지지 않기 때문에 먼저 A 기준으로 정렬을 해준다. 그리고 A에 연결된 B의 정보를 훑으면서 증가하는 수열을 찾는다. 전깃줄이 꼬이지 않는 경우는 B의 숫자가 계속 증가하는 경우다..

개발 공부 (알고리즘) 2021. 4. 14. 23:49

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이전에 풀었던 11053번 가장 긴 증가하는 부분 수열 문제의 응용버전이다. 바이토닉 수열은 증가하는 부분과 감소하는 부분이 동시에 존재한다. 증가하는 수열과 감소하는 수열을 둘로 나누어서 메모하는 아이디어는 생각했지만 실제로 어떻게 구현할 지를 생각하지 못했다. 다른 분의 글을 참고해서 이해했다. 예를 들어 본다. 1 2 3 2 1 이라는 바이토닉 수열이 있다. 증가하는 부분은 1 2 3 감소하는 부분은 3 2 1 이다. 이전에..

개발 공부 (알고리즘) 2021. 4. 13. 01:45

www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 처음에는 단순하게 반복문을 돌리면서 이전의 최댓값보다 더 큰 값이 나오면 추가한 다음 전체의 길이를 출력하는 방법을 이용했다. 결과적으로 접근법은 유사했으나 문제 이해를 못했던 것 같다. 일단 구해야하는 수열은 증가하는 수열이다. 그리고 그 수열 중에서 가장 길이가 긴 수열을 구해야 한다. 먼저 각각의 숫자를 순서대로 탐색한다. 증가..

개발 공부 (알고리즘) 2021. 4. 13. 00:07

www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 스스로 풀지 못해서 다른 분의 글을 참고했다. mygumi.tistory.com/98 백준 2156번 포도주 시식 [DP] :: 마이구미 이번 글은 백준 알고리즘 문제 2156번 "포도주 시식" 을 다뤄본다. 일단 문제를 보자. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 mygumi.tistory.com 포도주의 양이 주어지고 마실 수 있는 규칙..

개발 공부 (알고리즘) 2021. 4. 12. 03:07

www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 이 문제 또한 전형적인 다이나믹 프로그래밍 문제이다. 어렵게 생각하지 않고 그냥 내가 이 삼각형에서 최대로 합을 구하려면 어떤 방식으로 따라가는 지를 생각했다. 아래 층으로 내려가면서 나는 계속 선택할 것이다. 무엇을 더해야 최대가 될까 무조건 현재에 최대인 값을 고르는 것이 능사는 아니다. 왜냐하면 선택을 하면 다음 층에서 선택지는 무조건 두 가지로 좁혀지기 때문이다. 만약에 현재 가장 최대인 값을 따라 갔는데 다음 층에서부터 그 길에 작은 값들만 나온다면 합계는 최대가 안 될 가..

개발 공부 (알고리즘) 2021. 3. 17. 04:35

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이 문제는 처음에 생각했을 때 모든 경우의 수를 고려하는 백트래킹 방법이 떠올랐다. 단순하게 문제에 나온 조건을 그대로 따라가는 것이다. 첫 집을 칠할 때는 가장 비용이 적은 색을 선택하고 그 색의 인덱스를 저장한다. 이후에는 그 인덱스에 해당하는 색을 제외하고 다른 색 중에서 더 적은 비용을 가지고 있는 색을 선택한다. 하지만 이 방법은 다이나믹 프로그래밍과 맞지 않다고 생각했다. 이 문..

개발 공부 (알고리즘) 2021. 3. 12. 00:58

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제를 읽고 그림 예시를 보니 규칙성이 눈에 띄었다. 처음에는 어떻게 풀어야 할 지 해결 방법이 떠오르지 않았지만, 무언가 규칙이 존재할 것 이라는 생각을 지울 수 없었다. 이 문제가 다이나믹 프로그래밍 분류에 있는 문제라고 생각해서 떠올랐을 가능성이 크다고 생각한다. 1, 1, 1, 2, 2, 3, 4, 5, 7 ,9 위 수열은 문제에 나와있는 파도반 수열 P(10)의 숫자들이다. 규칙을 찾기 위해서 계속 삼각형 ..

개발 공부 (알고리즘) 2021. 3. 12. 00:49