Let's Begin Programming

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

www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 이 문제 또한 전형적인 다이나믹 프로그래밍(DP) 문제이다. 다이나믹 프로그래밍 문제는 n =1 일 때, n = 2 일 때 .. 이렇게 직접 세보면서 풀리는 경우도 꽤 있는 것 같다. 이 문제를 보고나서 종이에 직접 경우의 수를 구해보았다. 문제에 나와있는 예시는 n = 1, 2, 4 인 경우가 나와 있기 때문에 3, 5, 6 까지 해보니까 확실한 규칙이 보였다. n = 3 인 경우, 먼저 모두 0 인 경우는 존재하..

개발 공부 (알고리즘) 2021. 3. 11. 02:43

www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 다이나믹 프로그래밍 문제로 주어진 조건을 그대로 구현하면 실행 시간이 굉장히 오래 걸린다. 이럴 때 사용하는 것이 메모이제이션(Memoization) 기법이다. 캐싱(Caching)이라고도 부르는 이 기법은 중복된 연산을 피하고자 하는 다이나믹 프로그래밍을 위해서 기존에 계산한 결과를 저장해놓고 만약 다시 그 값이 필요하다면 곧바로 이미 저장되어있는 값을 반환하는 기법이다. 이 문제에서 입력으로 들어가는 변수는 a..

개발 공부 (알고리즘) 2021. 3. 8. 00:35

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 증가하는 수열의 길이를 구하는 문제이다. 입력의 크기가 100만이기 때문에 수열을 완전 탐색하면서 길이를 셀 수 없다. 이번 문제를 해결하면서 밑에 블로그를 참고했다. [참고]suri78.tistory.com/199 [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python https://www.acmicpc.net/..

개발 공부 (알고리즘) 2021. 2. 23. 08:05

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이 문제도 파라메트릭 서치 유형의 이분 탐색 문제이다. 이 문제도 해결 방법이 쉽게 떠오르지 않아 다른 사람들의 설명을 많이 참고했다. 해설을 들어도 바로 이해가 되지 않아서 예시를 하나 하나 따라가보면서 이해하려고 노력했다. 이해하고 코드를 작성하고 보니 문제의 길이만큼 코드의 길이도 짧았다. 하지만 만약 코딩테스트나 시험에서 이 문제를 만났다면 쉽게 이분 탐색을 생각하지 못했을..

개발 공부 (알고리즘) 2021. 2. 23. 06:15