벨에삐

동적 계획법(DP) 파트를 읽어보면서 아쉬운 점이 있습니다. 일관성있게 top-down 방식으로 DP를 설명하고 코드 또한 top-down 방식으로 적혀 있다는 점입니다. 때문에 알고스팟 문제들을 구글에 검색해도 대부분 종만북의 독자라고 추측이 가능할만큼 책의 소스코드와 거의 흡사하고 전부라고 하기엔 조심스럽지만 대부분 top-down 방식으로 코드가 작성되어 있습니다. 삼성SW 역량테스트와 같이 스택 메모리가 1MB로 작게 제한되어 있는 경우 top-down dp처럼 함수 call이 깊어질 수 있는 알고리즘의 경우 stack overflow 가능성이 높습니다. 책 후반부 bottom-up dp에 대해서 잠깐 다루긴 하지만, 대부분의 설명이 top-down 방식으로 알고리즘을 설계하는 과정을 다루고 있습..

https://www.algospot.com/judge/problem/read/LIS algospot.com :: LIS Longest Increasing Sequence 문제 정보 문제 어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. www.algospot.com #include using namespace std; int C, N, subseq[501], mx; int dp[501]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> C; while(C--){ memset(dp, 0, sizeof(d..

https://www.algospot.com/judge/problem/read/JUMPGAME algospot.com :: JUMPGAME 외발 뛰기 문제 정보 문제 땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상 www.algospot.com [BOJ] 1890번: 점프 와 유사한 문제입니다. #include using namespace std; int C, N, board[101][101], jumpDist; bool dp[101][101]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> C; while(C--){ memset(d..

https://www.algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 www.algospot.com #include using namespace std; int C, n, tri[101][101], dp[101][101]; int solve(){ // dp[i][j] : (i,j)까지의 최대합 // dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + tri[i][j]; for(i..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저, 이하 종만북) 책으로 동적 계획법(dynamic programming, 이하 dp)을 공부하다가 백준에서 비슷한 예제를 찾아 풀어보았습니다. 제가 dp 문제를 풀 때 풀이 방식은 다음과 같습니다. (https://blog.encrypted.gg/974 바킹독님 영향을 받았습니다.) 1) 문제를 풀기 위한 table을 정의 2)..

프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저)에서 저자는 문제 해결의 마지막 단계로 를 강조하고 있습니다. 문제를 한 번만 풀어서는 그 문제에서 배울 수 있는 것들을 다 배우지 못한다. 문제를 풀 때마다 코드와 함께 자신의 경험을 기록으로 남기는 것을 추천하고 있는데, 지금까지는 엑셀을 이용해 문제를 풀면서 배운 점들을 정리해왔습니다. 그러나 문제의 양과 난이도가 높아지면서 볼륨도 커지고 있어 한계를 느끼고 블로그를 활용하고자 합니다. 문제를 풀고 접근한 방식, 해법을 찾는 데 주요했던 깨달음, 실수하거나 놓쳤던 부분들을 기록하려 합니다. 여유가 된다면 공부한 내용들을 정리해 공유하는 것도 좋을 것 같습니다. 제가 공부하고 얻어가는 점들이 다른 누군가에게도 도움이 된다면 더할 나위 없겠습니다.