"(백준/ C++) 1010 - 다리 놓기 / 다이나믹 프로그래밍, 재귀"https://www.acmicpc.net/problem/1010 N을 늘려보면서 비교를 해보니 규칙을 쉽게 발견 할 수 있었다. N(강 서쪽)의 맨 위 다리가 M(강 동쪽)에 위치할 수 있는 조건은 N은 빠짐 없이 모두 연결은 되야 하므로 M - N + 1이 된다. DP [ N ][ M ] 이라고 만들 때, 아래 그림과 같이 규직을 찾을 수 있는데 N이 1일때는 M의 개수 만큼 경우의 수가 생긴다. 이 조건은 함수의 return(반환) 조건으로 사용하면 된다.또 N과 M이 같을 때는 모든 다리를 연결 하므로 언제나 하나의 경우의 수이다. 이거 또한 함수의 return(반환)조건으로 사용한다. N(강 서쪽)의 맨 위 다리를 M(강 ..

"(백준/ C++) 2629 - 양팔저울"https://www.acmicpc.net/problem/2629 아마 .. 양팔저울 문제 설명에 냅색 알고리즘으로 푸는 문제라고 적혀 있지 않으면 오랫동안 못 풀었을거 같다.. ^^;;  냅색과 같이 나올수 있는 무게의 경우를 만드는 방식으로 풀이를 했다. 점화식은 (가)저울에만 추를 둘수 있다고 생각 하고 경우의 수를 고려하였다. (가)에 A추가 있는 경우 → (가) A추 + 구슬 = (나) B추 → (가) 구슬 = (나) B추  -  A추 (나)에 A추가 있는 경우 → (가) 구슬 = (나) B추 + A추(가), (나)에 A추가 모두 없는 경우 → (가) 구슬 = (나) B추 처음에는 이분탐색으로 찾으려 했으나 메모리 문제로 실패 ! DP[비교대상개수][무게..

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net * 문제 풀이 알고리즘 문제 내에 있는 예제를 예시로 들면, {1 5 2 1 4 3 4 5 2 1} 에서 가장 긴 바이토닉 부분 수열은 {1, 2, 3, 4, 5, 2, 1} = 답 7이 됩니다. 밑에 작성한 알고리즘은 왼쪽에서 부터 증가하는 부분 수열의 DP(InC)와 오른쪽에서 부터 증가하는 부분 수열의 DP(DeC)를 구해서 그 합 중 가장 큰 수가 해답이 되도록 작성하였습니다. InC = { 1, 2, 2, ..

문제 URL : programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제 풀이: 기본이고 백준에서 너무 흔한 DP문제라서 쉽게 풀었다. 메모리 제이션을 사용했다. 약간 헷갈리지 말아야 할거는 원본의 데이터를 더해주는 것이 아니라 우리가 채워나가고 있는 Tri를 더 해줘야하는 것을 까먹지 말자 !!