Algorithm283 [코딩테스트 연습] 등굣길 문제: https://programmers.co.kr/learn/courses/30/lessons/42898# DP 문제입니다. dp[i][j] = dp[i-1][j] + dp[i][j-1] 의 관계가 성립함을 알 수 있습니다. 단, 전처리에서 중요한 것이 있는데요. 맨 처음 경로 계산을 위해 가장 자리 값들을 1로 셋팅 할 때 아래와 같이 할 수 있습니다. 집 1 1 1 1 1 1 학교 그런데, 특정 지점에서 웅덩이가 등장했다면, 그 뒷 지점은 전부 방문할 수 없으므로 0으로 놔둬야 합니다. 집 웅덩이 0 0 1 1 1 집 이 부분만 신경써주면 무난히 DP로 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42.. 2020. 6. 17. [코딩테스트 연습] 멀리 뛰기 문제: https://programmers.co.kr/learn/courses/30/lessons/12914 DP 문제입니다. 푸는 방식은 다양하겠지만 값을 저장함으로써 중복되는 연산은 O(1)에 리턴하는 로직이 중요합니다. 효진이는 한 번에 1칸 또는 2칸을 뛸 수 있으므로, N번째 칸까지 점프하는 방법을 구한다면 1. N-1번째 칸에서 + 1 점프하는 방법 2. N-2번째 칸에서 + 2 점프하는 방법 JUMP[N] = JUMP[N-1] + JUMP[N-2] 의 점화식이 성립하게 됩니다. 문제 조건처럼 1234567로 나눌 때 모듈러 연산자 법칙을 적용하면 답을 얻을 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG1.. 2020. 6. 15. [코딩테스트 연습] 하노이의 탑 문제: https://programmers.co.kr/learn/courses/30/lessons/12946 대표적인 재귀문제입니다. N개의 하노이 탑을 1번 기둥에서 3번 기둥으로 옮기려면 1. 1~N-1번째 하노이탑을 1번 기둥에서 2번 기둥으로 옮기고 2. N번째 하노이탑을 1번 기둥에서 3번 기둥으로 옮깁니다. (이 때 실제 갱신이 일어납니다) 3. 1~N-1번째 하노이탑을 2번 기둥에서 3번 기둥으로 옮깁니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG12946.cc 2020. 6. 15. [코딩테스트 연습] 섬 연결하기 문제: https://programmers.co.kr/learn/courses/30/lessons/42861 MST 문제입니다. 크루스칼 알고리즘을 통해 해결했습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42861.cc 2020. 6. 11. 이전 1 ··· 51 52 53 54 55 56 57 ··· 71 다음
