본문 바로가기

Problem/DP

[C/C++] BOJ 1010 :: 다리놓기 BOJ 1010 :: 다리놓기 문제 링크 : https://www.acmicpc.net/problem/1010 나의 풀이 다리 만들기는 아래와 같은 규칙이 있다. dp[n][m] = dp[n-1][m-1] + dp[n][m-1] 이를 이용하여 모든 table을 채운 뒤, input에 따른 dp[N][M]을 출력한다. 사용되지 않는 0행을 이용해서 table을 채우기 위해 0행을 모두 1로 채워주었다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1010/BOJ_1010.cpp 12345678910111213141516171819202122232425262728293031// 백준알고리..
[C/C++] BOJ 14002 :: 가장 긴 증가하는 부분 수열 4 BOJ 14002 :: 가장 긴 증가하는 부분 수열 4 문제 링크 : https://www.acmicpc.net/problem/14002 나의 풀이 1. 현재 idx의 수가 부분 수열의 마지막 수가 될 때, 이전 수의 arr의 idx와 부분 수열의 길이를 저장하는 구조체 배열을 만든다. 2. 다이나믹 프로그래밍 방식으로 부분 수열을 구하면서 수열의 이전 값을 갖는 arr의 idx를 저장한다. 3. 가장 긴 증가하는 부분 수열의 마지막 값에서부터 이전 값을 차례대로 스택에 넣은 뒤, 스택에서 빼내면서 출력한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_14002/BOJ_14002.c..
[C/C++] BOJ 11055 :: 가장 큰 증가 부분 수열 BOJ 11055 :: 가장 큰 증가 부분 수열 문제 링크 : https://www.acmicpc.net/problem/11055 나의 풀이 1. 가장 큰 증가 부분 수열을 저장할 1차원 배열을 생성한다. 2. 기준 idx를 두고 그 앞 범위를 탐색하며 증가 부분 수열일 될 때, 그 합을 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11055/BOJ_11055.cpp 1234567891011121314151617181920212223242526272829303132333435// 백준알고리즘 11055번 :: 가장 큰 증가 부분 수열#includeusing namespace..
[C/C++] BOJ 11722 :: 가장 긴 감소하는 부분 수열 BOJ 11722 :: 가장 긴 감소하는 부분 수열 문제 링크 : https://www.acmicpc.net/problem/11722 나의 풀이 1. 가장 긴 감소하는 길이를 저장할 lds 배열을 만든다. 2. 기준 idx까지 앞 쪽의 원소들을 탐색하면서 감소하는 부분 수열이 될 경우, 기준 idx의 lds를 갱신한다. 나의 코드 Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_11722/BOJ_11722.cpp 123456789101112131415161718192021222324252627282930313233// 백준알고리즘 11722번 :: 가장 긴 감소하는 부분 수열#includeusing..
[C/C++] BOJ 11053 :: 가장 긴 증가하는 부분 수열 BOJ 11053 :: 가장 긴 증가하는 부분 수열 문제 링크 : https://www.acmicpc.net/problem/11053 나는 아직 for문 여러 개를 사용해서 다이나믹 프로그래밍 하는 것에 서툰 것 같다!! 옛날에 살짝 공부했던 적이 있는 LIS 기초 부분인데도 제대로 풀지 못했다 ㅠㅠ.. 알고리즘에 대한 공부를 명확히 하고 문제를 다시 풀어봐야 겠다!! 나의 풀이 1. 배열의 기준점을 두번째 index에서 가장 긴 곳까지 두면서 비교한다. 2. 배열의 0번에서 기준점까지 점진적으로 비교하면서 증가하는 수열이 될 때에 dp배열을 갱신시킨다. 3. 모든 dp배열을 채운 후, 그 중 가장 큰 값을 찾아 출력한다. 나의 코드 Github : https://github.com/j2wooooo/Da..
[C/C++] BOJ 1932 :: 정수 삼각형 BOJ 1932 :: 정수 삼각형 문제 링크 : https://www.acmicpc.net/problem/1932 나의 풀이 1. 정수삼각형의 값을 2차원 배열에 저장한다. 2. 각 층마다 최댓값을 저장한다.삼각형의 가장 왼쪽 값은 바로 윗층의 같은 열의 값 + 현재 값을 저장한다.삼각형의 가장 오른쪽 값은 바로 윗층의 현재 열 - 1 의 값 + 현재 값을 저장한다.나머지 값은 그 둘 중 최댓값 + 현재 값을 저장한다. if (j == 0) arr[i][j] += arr[i-1][j]; else if (j == i) arr[i][j] += arr[i - 1][j - 1]; else arr[i][j] += max(arr[i - 1][j], arr[i - 1][j - 1]); 3. 마지막 층 중에서 최댓값을..
[C/C++] BOJ 11052 :: 카드 구매하기 BOJ 11052 :: 카드 구매하기 문제 링크 : https://www.acmicpc.net/problem/11052 나의 풀이 학부 고급알고리즘 시간 때 배운 Knapsack 알고리즘을 생각하며 풀었다! 1. 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값은 카드 1개가 포함된 카드팩의 가격이므로 그 값을 그대로 저장한다. 2. 카드 2개부터는 지금까지 저장한 카드를 갖기위해 지불해야 하는 금액의 최댓값과 카드팩의 가격을 이용하여 비교한 후 갱신한다. Ex) 카드 2개를 갖기 위해 지불해야 하는 금액의 최댓값은 1) 카드 0개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카드 2개가 포함된 카드팩의 가격 = 5현재 저장되는 최댓값은 52) 카드 1개를 갖기 위해 지불해야 하는 금액의 최댓값 + 카..
[C/C++] BOJ 2306 :: 유전자 BOJ 2306 :: 유전자 문제 링크 : https://www.acmicpc.net/problem/2306 처음에는 다이나믹 프로그래밍이니까 무조건 하나의 반복문 루프 안에서 끝내야 한다는 생각에 사로잡혀 한 번의 루프로 끝낼 수 있는 규칙을 찾지 못해 난관에 빠졌었다, 생각을 바로잡고 문제에 나와있는 규칙을 적용하여 재시도한 결과, 얼추 규칙에 맞는 프로그래밍을 할 수 있었다. 그러나 계속 틀렸습니다. 가 떠서 백준 슬랙을 통해 문의한 결과 ㅠㅠ 간과한 점을 알 수 있었다. 나는 2번 조건과 3번 조건을 각각의 반복문으로 진행시켜 주었는데 그러면 atat와 같은 KOI 유전자의 길이를 제대로 도출해낼 수 없었다. 따라서 같은 루프 안에서 2번 조건과 3번 조건을 함께 판단하는 것으로 코드를 변경함으로..

티스토리툴바