꼬들꼬들한 컴퓨터 공부 블로그

백준 17070번 문제 "파이프 옮기기1" 이다. https://www.acmicpc.net/problem/17070문제예제 입출력 입력출력30 0 00 0 00 0 0140 0 0 00 0 0 00 0 0 00 0 0 0350 0 1 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0060 0 0 0 0 00 1 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 013 문제 접근한눈에 봤을 때 dp문제라는 생각이 들었다. 현재 칸의 경우의 수가 이전 칸의 경우의 수를 합해서 만들어지기 때문이다. 파이프는 3가지 형태로 놓일 수 있다. (가로, 세로, 대각선)   파이프를 이동시켰을 때 가로로 놓이는 경우는 위의 두 경우 밖에 없다. 이전 칸에 ..

백준 12865번 문제 "평범한 배낭" 이다. https://www.acmicpc.net/problem/12865 문제 예제 입출력 입력출력4 76 134 83 65 1214 문제 접근 분명 다이나믹 프로그래밍 문제인것 같기는 한데 잘 풀리지 않아 구글링을 참고하였다. 알아본 결과 '최적 조합 찾기' 의 유명한 경우로 '배낭문제'(knapsack problem) 였다. 일반적인 풀이를 참고하여 문제를 풀었다. knapsack problem 의 해법은 아래 포스팅에서 자세히 정리하였으니 참고하자. https://ggo-dong.tistory.com/44 쪼갤 수 없는 배낭 문제 (0-1 Knapsack Problem)- 알고리즘 소개 배낭 문제 (knapsack problem) 은 대표적인 DP 문제 중 ..

- 알고리즘 소개 배낭 문제 (knapsack problem) 은 대표적인 DP 문제 중 하나이다. 가치가 서로 다른 여러 물건이 주어졌을 때, 정해진 용량 안에서 최대의 가치를 얻어내는 문제를 의미한다. '가치가 서로 다른 여러 물건' 을 짐으로, '정해진 용량만큼 선택하는 것' 을 배낭으로 비유해서 '정해진 크기의 배낭 안에 최대 가치의 물건을 담는 조합을 찾아내는 문제' 로 설명한다.  배낭 문제는 '0-1 knapsack problem' 과 'Fraction knapsack problem' 으로 나뉜다. 0-1 은 짐을 쪼갤 수 없는 문제를 의미하며, Fraction 문제는 하나의 짐을 쪼갤 수 있는 문제를 의미한다. 이 중 짐을 쪼갤 수 없는 0-1 문제가 오늘 살펴볼 알고리즘이다. - 알고리즘..

백준 9251번 문제 "LCS" 이다. https://www.acmicpc.net/problem/9251  문제 예제 입출력 입력출력ACAYKPCAPCAK4 문제 접근 LCS 를 구하는 알고리즘은 따로 포스팅 한 바 있다. https://ggo-dong.tistory.com/26 LCS(최장 공통 부분 수열) 구하기- 알고리즘 소개 LCS(Longest Common Subsequence, 최장공통부분수열) 이란 이름 그대로 "두 수열의 부분수열 중 가장 길이가 긴 수열" 을 의미한다.  부분수열은 원래의 수열에서 뽑아 만든 새로운 수ggo-dong.tistory.com  따라서 자세한 설명은 하지 않겠다.문제 풀이 풀이 방법은 다음과 같다. 1. 주어지는 두 수열을 입력받는다. 2. LCS 알고리즘을 이..