Red Salmon

출처 : https://www.acmicpc.net/problem/1520

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2017.05/1520.cpp

이 문제는 1년전에 틀렸던 문제였다. 결론만 보자면 매우 간단한 문제이다. 아마 1년전에 틀렸던건 작년 초에 내가 메모이제이션을 정의하지 못했던 시절인것 같다.

물론 너무 오랜만에 문제를 풀다보니 오래걸렸다.

먼저 문제의 요점을 파악해보자면 현재보다 낮은 지점으로 가야하고, 최대크기가 500x500이라는 것이다. 높이가 1만이라는건 크게 개의치 않아도 될 것 같다.  뿐만 아니라, 정답이 10억이하의 음이아닌 정수라고했으니 int범위안에 정답이 있을 것이다. 

그럼 이제 문제의 풀이를 보자.

500x500.. 적다면 적고 크다면 큰 매트릭스이다. 아마 일반적 dfs로 접근하면 시간초과가 날 확률이 매우 높다.(그래서 1년전에는 시간초과를 맞았다.)

그래서 BFS로 풀어보니 메모리가 너무 커지는 문제가 발생한다. (큐가 너무 커지는 문제..)

그래서 우리에겐 메모이제이션 개념이 있는것이다. 이미간 지점에 대해서는 더이상 계산을 하지않게 하는 방법!

이방법을 사용한다면 위의 두 문제를 해결할수있다. 나는 DFS로 풀었다.

먼저 memo를 할 배열을 만들고 -1로 전부 초기화를 한다. 이건 가지 않았다는 말이다.

그리고 dfs를 돌면서 만약 이 지점이 이미 값이 있다면 바로 리턴을 한다. 왜냐면 이미 방문한 지점에 대해서는 값이 갱신되어 있기 때문에 더이상 추가적인 계산이 필요없다. 어떤 점이든 정점에 다다르면 1을 리턴한다.

조금 더 풀이해보면 포문에

cnt+=dfs(nx, ny)라고 되어 있는데

이미 간 지점이라면 이미 이 지점에서 몇가지 경우의수로 도착을 하였다. 이걸 알려줄 것이고 없다면 쭉 돌다가 1을 리턴하니 이걸 추가할것이다. 즉 4방향에 대해서 모든 cnt가 더해진다.

그리고 최종적으로 해당 좌표의 cnt값이(목적지까지 가는 가짓수) 나올텐데 이를 memo에 기록해둔다. 그럼 각 지점마다 정점에 도달하는 수가 dfs를 통해 기록이 될 것이고 최종적으로 0, 0에서 출발하여 정점까지 다다를때의 경우의수가 기록되어 정답이 나오게 되는 것이다.

 메모이제이션은 참 간단한 개념이지만, 익숙해지는데 조금 걸리는것 같다. 하지만 한번 익숙해지면 참 써먹을 곳이 많고 특히!! sw회사 알고리즘 필기시험을 준비한다면 반드시 알아두어야 할 개념이다. 특히 삼성sw역량평가의 경우 2번문제에서 몇번 나왔었다. 일반적인 dfs, bfs로는 풀리지않고 메모이제이션을 써야 풀리는 경우. 

뭐 어쨌든 알고리즘은 많이 푸는게 장땡이다.

출처 : https://www.acmicpc.net/problem/6603

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2017.05/6603.cpp

진짜 오랜만에 다시 풀어봤다. 아주 감을 잃었다 ㅋㅋㅋ 이제 주마다 꾸준하게 한두개씩은 다시 풀어야겠다. 취직하니 확실히 안하게 되는군..

암튼 문제는 간단히 재귀를 돌리는 것이다. 더이상의 설명은 필요없으므로 생략한다.

출처 : https://www.acmicpc.net/problem/10844

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/10844.cpp

정말 많은 생각을 하게 한 문제이다.

DP인것은 알았으나 어떤식으로 작성해야할지 정말 감이 오지 않았다.

역시 이럴땐 하나씩 다 해보는것이 최고이다.

나는 N이 1부터 3까지 전부 만들어 보았다. 시작값은 0이 될수없으므로 1부터 시작하여 

가장 앞자리가 1, 2, 3...9 까지 전부 구해보았다. (많은 DP문제가 이런식으로 접근한다.)

이렇게 하고나서 규칙을 찾기 위해 많은 시간을 소모했다. 

결국은 삼각형 구조였는데, 나는 삼각형구조를 생각은 했으나 직각삼각형 구조를 생각하여 쉽게 풀리지 않았던것 같다.

개인적인 경험으로 DP에서 이렇게 배열을 조합해야 한다면 결코 어렵게 풀리지 않으며, 특히 수가 나열된상태에서 찾는것이라면 상하좌우대각선포함해서 1칸씩 움직이는 범위안에 규칙이 존재하는것 같다.

뭐 결국은 풀어서 다행이다.

출처 : https://www.acmicpc.net/problem/13418

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.12/13418.cpp

이 문제의 요점은 결국 모든 점을 최소값으로 지나야 한다는 것이다. 

즉 크루스칼 혹은 프림알고리즘을 사용해야 한다. 

정점의 값은 오름막이 0 내림막이 1이다. 나는 처음에 이를 반대로 생각하여 오답을 도출했다.

그래서 이를 수정하기위해 w값을 w=!w로 반전해주어 값을 주었다.

그리고 값은 n^2을 해야 한다는 것을 명심해야 한다.

기본적인 프림 혹은 크루스칼알고리즘을 구현할수있다면 큰 문제없이 풀 수 있는 문제이다.