문제 출처 : https://www.acmicpc.net/problem/16172 문제 해결에 필요한 알고리즘 : KMP ( Knuth Morris Pratt ) 알고리즘 해설 알파벳과 숫자로 이루어진 문자열에서 숫자를 무시하고 검색하여 문자열이 포함되어있는지 판단하는 문제이다. 문자열 길이가 1,000,000 이므로 일반적인 탐색방법으로는 해결이 불가하다. 그래서 빠른 검색알고리즘인 KMP를 적용하면 된다. KMP 알고리즘은 한번의 순회로 문자열을 검색하는 방법이다. 간단한 예시로 nabananbananaba 라는 문자열에서 nanaba를 검색한다고 했을 때 일반적인 알고리즘이라면 첫 na까지 검색하고 b가나와 맞지않으므로 a부터 검색을 시작한다. 하지만 이미 na까지 검색을 했다면 a로 탐색을 시작하..
문제 출처 : https://www.acmicpc.net/problem/16174 문제 해결에 필요한 알고리즘 : DP ( Dynamic Programming ), BFS ( Breadth First Search ) 알고리즘 해설쩰리가 움직이기 시작하는 위치인 (0, 0) 부터 queue에 넣어 순차적으로 탐색을 시작한다. 쩰리는 오른쪽 또는 아래쪽만 이동이 가능하기 때문에 선택가능한 선택지는 두가지이하다. 맵 밖을 나가지 않으면서 이미 방문했던 칸이 아닌 곳을 계속 queue 에 넣어주며 (N - 1, N - 1)을 도달할 수 있는지 확인하면 된다. (N - 1, N - 1)좌표로 이동했다면 승리, 이동하지 못했다면 패배가 된다. 정당성 증명이미 방문한 칸을 다시 탐색하지 않아도 되는 이유는 결과가 중..
문제 출처 : https://www.acmicpc.net/problem/1931 문제 해결에 필요한 알고리즘 : 그리디 알고리즘 해설회의의 정보를 받아 정렬한다. 정렬 기준은 회의가 끝나는 시간이 빠른 순으로 정렬한다.그 이후 선택가능한 회의 중 가장 빨리 끝나는 회의를 고르면 된다. 회의 정보를 순회하면서 다음 회의 진행이 가능하다면 ( 이전회의시간과 겹치지 않는다면 ) 그 회의를 고르고 카운트를 세어준다. 끝나는 시간이 빠른 순으로 정렬되어있기 때문에 선택가능한 회의 중 가장 빨리 끝나는 회의를 고를 수 있다. 이렇게 모든 회의를 고르고 그 카운트를 세면 최대 사용할 수 있는 회의의 수를 알 수 있다. 정당성 증명선택가능한 회의 중 가장 빨리 끝나는 회의를 골랐을 때 이득인 이유는 귀류법으로 증명이 ..