Red Salmon

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

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

이 문제는 그냥 완전 탐색 문제이다. 심지어 N이 1백만뿐이다. 다돌려봐도 무방하다.

나는 1부터 돌려보아서 조건이 성립하는지 확인하도록 만들었다.

다만 문제는 생성자수가 존재하지 않을 경우가 있으므로 0을 출력하는 부분을 반드시 만들어야 할 것이다.

딱히 풀이도 없다. 그냥 보이는대로 풀면 된다.

출처 : 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/1965

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

구직활동으로 거의 안풀었고 풀어도 올리지 않다가 이제 다시 블로그 작성 시작!

먼저 이 문제는 어떻게 봐도 다이나믹프로그래밍이라는것을 어필하고 있는 문제이다. 최대 개수를 구하라는 것은 완탐 or DP일텐데 만약 완탐으로 접근한다면 각 입력마다 최대값을 구하기 위해 선택을 하고 또 하는 과정이 있어야 할 것이고 TL을 피하기 위해선 메모이제이션이든 뭐든 미리 기록해놔야할것이다. 즉, 할수있을지 없을지도 미지수이고 굉장히 복잡해진다.

그러므로 간단히 DP를 써보도록 한다. 이 문제의 알고리즘은 LIS(Longest Increasing Subsequence)라는 알고리즘이다. 

이는 최장 증가 수열을 구하는 문제인데 예전에 캐쳐 미사일 문제를 풀때 공부해뒀던 것이다.

간단히 알고리즘을 적어보면 다음과 같은 과정을 밟게 된다.

1. 정답을 담을 배열을 만든 후 입력받은 배열의 한 요소씩 검사를 시작한다.

2. 만약 현재 정답배열의 사이즈가 0이거나 정답배열의 마지막 값보다 현재 검사하는 요소값이 크다면 새로이 추가를 한다.

3. 2번의 과정에 속하지 않는다면, 한칸씩 앞으로 이동하며 2번의 조건이 성립할때까지 인덱스를 탐색한다.

4. 그리고 최종적으로 배열의 크기를 출력하면 된다. 

이게 알고리즘의 전부인 굉장히 단순한 풀이이다. 예를 들면 다음과 같다.

예제를 보면 

1 6 2 5 7 3 5 6 인데

처음 1 6까진 증가수열이므로 그대로 두고 2가 들어오면

1 2 가 되며 6이 사라진다.

그리고 5 7까지는 그대로 다시 추가되어 1 2 5 7 이 구성된다.

그 후 3이 들어오게 되면 1 2 3 7 이 되고 순차적으로 5와 6이 추가되어 1 2 3 5 6

으로 최종 5가 출력되게 된다.

물론 이 풀이는 그닥 빠른 방법이 아니며 더 빠른 방법이 있다. 하지만 이 방법만 알아도 많은 문제를 풀 수 있으므로 알아두는게 좋다.

구현 방법은 사람마다 다를 것이기 때문에 굳이 나처럼 풀지 않아도 된다. 늘 강조하지만 알고리즘은 하나여도 풀이 방법은 수만가지가 나오는것이 프로그래밍이다.

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.08/1707.cpp

정답 소스에 1707이라는 실수를 하였다. 그냥 넘어가야지..

암튼 이문제는 서픽스어레이를 활용한 문제이다. 물론 KMP를 써도 풀릴것 같은데 내가 해보니 참 어려웠다.

그리고 suffix array를 쓰는게 훨~ 씬 간단하게 풀린다.

하지만 아직 suffix array 구현 방법을 모르겠다 ㅠㅠ 공부중이다. 나중에 공부가 끝나면 다시 풀어봐야겠다.

내가 푼 방법은 테스트케이스가 적기 때문에 가능한 풀이법이다.

결론은 LCP를 활용하였지만, suffix array가 생명인 것이다.

그런데 찾고보니 최적의 알고리즘은 O(n)으로도 할 수 있다는데 도대체 어떤 방식인지 궁금하였다. 

암튼 이 문제도 1년이 넘는 시간만에 드디어 풀었다.