출처https://www.acmicpc.net/problem/15724처음엔 주지수라길래 무술 중에 하나인 주짓수인줄 알고 주짓수랑 알고리즘을 어떻게 연관지을까 궁금했지만 단순히 땅에 사는 사람들의 합을 구하는 문제였다..풀이 전략누적합을 구하는 문제이므로 처음에는 직접 구해야 하는 사각형의 범위를 지정해서 범위 내의 모든 cell값을 전부 더하는 방식을 시도했다. 하지만, 뒤에서 얘기하겠지만 이렇게 하게 될 경우 시간 초과 문제가 발생하기 때문에 DP를 활용해서 풀이할 것이다.풀이이 문제의 예시를 그려보면 위의 그림과 같다. DP로 누적합을 구하는 알고리즘의 경우 형태만 알아놓으면 정말 쉽게 풀 수 있다.Main code를 보면,for (int i=1; i이게 누적합을 구하는 알고리즘인데, 해석을 해보..

출처https://www.acmicpc.net/problem/9251풀이 전략'알고리즘및문제해결기법' 수업에서 Dynamic Programming [A.K.A DP]에 대해 배우면서 예시로 배웠던 LCS [Longest Common Sequences, 최장부분공통수열] 알고리즘을 사용하여 문제를 풀 것이다.이 문제를 풀기 위해서는 점화식을 알아야 하고, 점화식을 잘 모른다면 표를 그릴줄만 알아도 점화식 유도는 충분히 할 수 있을 것이라고 생각한다.풀이사실 LCS 알고리즘은 왠만한 코딩테스트 준비용 서적에 거의 다 나와있을 정도로 코딩테스트에도 자주 빈출되고, 그만큼 유명한 알고리즘이기 때문에 점화식을 외워놓는다면 쉽게 풀 수 있을 것이다.위의 그림에서 표를 해석하면, i=0, j=0인 부분 (파란색 형광..

출처https://www.acmicpc.net/problem/2293풀이 전략동전의 합을 만족하는 경우의 수를 구하는 문제이다. 다른 알고리즘으로도 풀 수 있겠지만, 중복을 허용하지 않는다는 점과 동전의 금액이 그때그때 입력 받는다는점이 DP로 해야하는 이유라고 생각해서 DP로 풀이를 하였다.풀이먼저, 1원만 있을 때 만족하는 경우의 수와 2원이 추가되었을 때의 경우의 수를 보면 2원이 추가되었을 때 특징이 보이는데, 2의 배수인 2, 4, 6, 8, 10에서 경우의 수가 1씩 증가한다는 점이다. 그러나 이것 만으로 점화식을 구하면 틀릴 가능성이 존재하기 때문에 5원을 추가했을 때의 경우의 수도 구해보았다.5원을 추가했을 때를 보면 4원까지는 2원을 추가했을 때의 경우의 수와 동일하다가 5원을 추가했을 ..

출처https://www.acmicpc.net/problem/2573풀이 전략[백준 2636 - 치즈] https://www.acmicpc.net/problem/26362024.09.10 - [Baekjoon] - [C++] 백준 2636 - 치즈 [Gold4] [C++] 백준 2636 - 치즈 [Gold4]출처https://www.acmicpc.net/problem/2636풀이 전략먼저 문제 해석을 해보면, 1로 입력 받은 치즈가 시간이 지날 수록 녹아 내리는데, 녹아 내리는 부분을 보면 공기(0)과 맞닿아 있는 부분이라는 것을 알phj6724.tistory.com이 문제와 상당히 유사한 방식으로 접근을 해야 한다.다만 다른 점은, 이 문제에서는 빙산이 둘로 쪼개지는 순간의 시간을 출력해야 하기 때문에..

출처https://www.acmicpc.net/problem/7869풀이 전략세 가지 조건으로 나누어서 풀이를 한다.번호조건1원이 전혀 겹치지 않는 경우2원이 일부만 겹치는 경우3한 원이 다른 원에 포함되는 경사실 세 가지 조건이지만, 1번의 경우는 0을 출력하면 되고, 3번의 경우는 반지름이 작은 원의 넓이를 출력하면 되기 때문에 사실상 2번을 구하는 식만 구현하면 된다.고등학교 수학시간에 많이 나왔던 도형의 넓이를 구하는 문제이지만, 원이 겹치는 넓이를 구해야하기 때문에 은근 까다로울 뿐더러 double 자료형을 써야하기 때문에 신경써야할 부분이 많은 문제이다.잠시 고등학교 수학 시간으로 돌아가보면, 원의 넓이를 구하는 공식은 2πr2이라는 것은 누구나 다 알 것이다. 그리고 원의 일부인 호의 넓이를..

출처 https://www.acmicpc.net/problem/24042풀이 전략이 문제의 경우 일반적인 dijkstra 문제와는 살짝 다르다.신호등이 바뀌는 순서를 고려할 뿐더러 만약 경로에 순서가 늦는 신호등이 있는 경우 신호등의 주기만큼 기다려야 한다.따라서 일반적인 Dijkstra 알고리즘의 틀에서 cost를 계산하는 부분을 잘 계산해야한다.풀이왼쪽에 있는 첫 번째 예제의 경우 1-4 로 가는 최단 경로는 1-4 방향 신호등이 4번째에 바뀌기 때문에 정답은 4인 것을 쉽게 알 수 있다.그러나 오른쪽에 있는 두 번째 예제의 경우 1-8로 한번에 가는 경로가 없기 때문에 여러 신호등을 거쳐 가야하므로 고려해야할 부분이 많다.먼저 정답이 되는 경우의 계산 방식을 보면,1-2 횡단보도가 7번째에 바뀌기 ..