5525번 - IOIOI
주어진 문자열에서 어떻게 P_k를 찾고, P_k안에 P_N이 몇개 들어있는지를 고민해보시면 될것 같습니다.
.
개인적으로는 실버-골드 문제에 KMP를 가져오는 것은 닭잡는데 소잡는 칼 가져오는 격이라고 생각합니다.
뭐, 풀리기야 하겠는데, 그것을 이해하고, 실수없이 구현하는데 더 많은 비용이 든다고 생각이 됩니다.
.
문자열 알고리즘은 이걸 언제 배우고 써먹느냐는 이슈가 있죠. 트라이, KMP, 라빈-카프, 아호-코라식, ...
제가 2024년 상반기동안 백준 Open Contest를 참여 해보면서 저런 개념을 필수로 요구하는 문제는 2문제? 정도 봤습니다. 모두 플레 이상의 문제였고요. 그 문제에 가기 전에 시간이 다 되는 경우가 대부분이었습니다.
사실, 초창기에는 'solved티어를 높이면 Open Contest도 잘 되겠지'하고 무작정 생각했었는데, 하다보니 골드3이하를 주어진 시간 내에 안정적으로 풀어낼 수 있느냐가 더 중요하더라고요. 실제로 티어를 높이기보다는 주어진 시간안에 골드3이하 문제를 안정적으로 풀어내는 것을 연습했을 때 Open Contest 성적이 더 많이 올랐습니다.
코딩테스트는 잘 모르겠습니다. 하지만 비슷할 것이라는 생각이 드네요. 코딩테스트가 문제에 저 중 하나를 요구하는 문제가 있다? 개인적으로는 그냥 그걸 빼고 최대한 푸는게 더 성적이 잘 나올거라고 생각합니다. 만약 문제수도 적고 하필 저것들로만 이루어진 문제들이 있다? 그 정도 변별력 판단을 못하는 코딩테스트를 내는 출제자가 문제가 있을거라는 생각이 드네요(물론 뭐 문자열을 전문적으로 다뤄야하는 자리라면 모르겠지요).
.
아무튼 제 개인적인 결론은 코딩 테스트에서 안정적으로 상위권에 가기 위해서 중요한 것은 "몇몇 특별한 방법론이 아닌 하나의 방법론을 다양하게 적용해보는 것"이 중요하다고 생각합니다. 그러한 관점에서 이 문제를 풀기 위해 KMP를 배우는 것은 큰 의미가 없다고 생각되네요.
그런데 코테 그 이후를 생각하면은 잘 모르겠습니다. 제 친구 중 한명은 최근 인터뷰 자리에서 KMP에 관련된 질문을 받아본적 있다고는 하더라고요.
코딩 테스트 합격만을 목표로 하시는 취준생이시라면 kmp, 라빈-카프 알고리즘의 학습은 대체로 필요하지 않습니다. 이러한 알고리즘들은 기본적으로 코딩 테스트 출제 범위 바깥이며, 알고리즘 대회에서나 주로 출제되는 개념들입니다. 그 대신 말씀해 주신 두 포인터, 슬라이딩 윈도우와 같은 비교적 기초적인 알고리즘을 더 깊게 학습하실 것을 권합니다.
난이도가 비교적 낮은 알고리즘이라지만 절대로 무시할 수 없고, 쉬워 보이는 알고리즘이더라도 깊게 이해하는 것이 중요한 이유는 아래와 같습니다.
저는 kmp, 라빈-카프와 같은 알고리즘을 학습하는 것이 쓸모없다고 이야기하는 것이 절대로 아닙니다. 그렇지만 취준생분들에게는 시간이 없습니다. 이러한 알고리즘을 학습하기 전, 먼저 핵심적인 알고리즘들에 충분히 익숙해지고, 익숙해지기 위해 많은 문제들을 풀어보셔야 하며, 실전에 가까워지셨다면(알고리즘을 새롭게 학습하는 시기가 아닌 충분히 이 알고리즘에 익숙해진 상태) 알고리즘 분류를 보지 않더라도 시간 복잡도를 기반으로
와 같이, 스스로 풀이를 떠올리실 수 있어야 합니다.
답지에서 "무슨무슨 알고리즘을 써야 합니다" 여서 그 알고리즘을 사용하는 것이 아닌, "이렇게 하면 제 풀이의 시간복잡도는 ~~~이므로 입력 조건이 ~~~여도 통과할 수 있어요" 와 같이 누군가가 알고리즘 분류를 알려주지 않더라도 자신의 접근 방법을 이야기할 수 있는 것이 중요하다고 생각합니다. 여러 핵심적인 알고리즘들에 익숙해지셨고, 다양한 문제를 공략하실 수 있으시다면, 그 때 kmp나 라빈-카프와 같은 난이도가 높은 알고리즘에 도전해 보세요. 이전과 달리 알고리즘의 필요성을 이해하기에 더 좋을 것입니다. 기존에 알고 있던 다른 알고리즘들과 비교하기에도 정말 적합하고요.
핵심적인 알고리즘들을 더 연습해 보시고, 다양한 문제들을 많이 풀어보세요. 이곳 백준 게시판에서 문제 추천을 요청하시는 것도 좋은 방법입니다.
댓글을 작성하려면 로그인해야 합니다.
dachaes 2년 전
5525 번을 풀다가 KMP 의 지옥에 빠져서 글 하나 남깁니다...ㅎ
유튜브에 KMP 관련 강의를 보다보니 코테에 잘 안나오니까 개념만 알아두라고 조언해주는 걸 몇 번 봤어요.
운 안좋게 문자열 매칭 알고리즘을 써야하면 라빈-카프를 사용하라고도 하더라구요.
지피티로 검색해보니 이 문항은 슬라이딩 윈도우 알고리즘으로도 풀린다는데요..
KMP 나 라빈-카프를 익히지 않고, 윈도우 알고리즘이나 투포인터만 공부하고 넘겨도 될까요...?