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/2565

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

이 문제는 초등부 올림피아드 문제이다. 심지어 거의 10년전에 출제된 문제인데... 난 이걸 최근에 알았는데... 

내가 왜 구직활동이 힘든지 이해가 된다. 전국에는 뛰어난 인재가 참 많은거 같다.

근데 뭐 나도 LIS를 사용하니 금방 풀긴 했다. 물론 LIS인지 빨리 파악하는게 매우 중요하다.

나는 다음과 같은 방법으로 접근했다.

1. 우선 겹치지 않아야 한다. 그러면 A를 기준으로 봤을때 B가 순차적이면 되면 될거같다.

2. A를 기준으로 입력을 정렬해보자. 그럼 예제는 다음과 같이 된다.

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

이렇게 보니 딱 사이즈가 나온다. 위에 3개를 쳐내면 4부터 최장증가수열이 만들어 진다.

즉, 나는 최장증가수열을 구하고 n에서 빼면 되는 것이다.

문제는 많이 어려워보이지만 실질적으로는 별거 없는 것이다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2239.cpp

이문제와 거의 같다.

그래서 다시 bool변수로 바로바로 체크하게 하였고 결과적으로 정답을 맞았다. 그런데 bool함수를 더 두어 가로세로부분도 포문없이 검색하게하였다면 속도가 더빨라졌을거라고 생각한다.

굉장히 귀찮고 손이 많이 가는 문제였다. 하지만 기초적이고 생각할게 있는 괜찮은 문제라고 생각한다. 

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2573.cpp

참으로 진부한 bfs문제이다. 단, 주의해야할점이 분리가 되지 않는 경우도 있다는 점이다. 

난 이문제를 엄청 해맸는데 그이유는 단한글자 때문이었다. 그 한글자의 오류를 찾기까지 정말 오래걸렸다.

정답을 맞긴하였지만, 만약 시험을 보고있는 중이고 알고리즘에 대한 확신이 있는데 오답이라면 수정하기보다는 그냥 새로 처음부터 짜는게 훨씬 득이 될것이다.

물론 알고리즘 자체가 불확실하거나 빈틈이 있다면 새로 짜는것은 오히려 독이 될 수 있다.

암튼 이런문제는 2개의 배열을 준비해두고 이것들을 스위칭 시키는 방식으로 나는 자주 푼다. 물론 다른사람들은 다르게 풀겠지만 이것은 내스타일이다.

그래서 배열이 2개에 카피하는 배열을 두는데 여기에는 어느정도 리스크가 있다.

그러나 문제가 bfs를 요구한다면 이 방법은 거의 다 통과이다. 현재까지 bfs이지만 이런방법을 썼기때문에 TL이나 오답이 나온적은 없다. 

만약 틀렸다면, 알고리즘 자체가 틀렸을 것이다.