배움 저장소

programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr i번째 집을 방문하면 i-1번째 집을 방문할 수 없고 i-2번째 집을 방문할 수 있다. i번째 집을 방문하지 않으면, i-1번째 집을 방문할 수 있다. 배열을 만들어, 도둑이 집을 방문하며 얻은 최대값을 저장하면된다. 이때 i번째 집은 방문 하거나 방문 하지 않거나 선택할 수 있다. 최대값을 반환하면 되므로 다음과 같은 식을 세울 수 있다. i번째 최적값은 (i-2번째 최적값 ..

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 먼저 떠오른 방법은 DFS, 정확성 테스트를 통과하였으나 효율성 테스트를 통과하지 못했다. 2차원 백터 위에서 동적할당 기법을 사용하면 된다는 생각은 했는데, 최단 거리 조건을 어떻게 넣을지 몰라 헤매다가 다른 풀이를 찾아보았다. 그런데 최단 거리 조건은 고려할 필요가 없었다. 왔던 자리를 돌아가지 않으면 최단거리 조건을 만족하기 때문이다. DP 기법을 사용할 때 ..