dachaes   2년 전

5525 번을 풀다가 KMP 의 지옥에 빠져서 글 하나 남깁니다...ㅎ

유튜브에 KMP 관련 강의를 보다보니 코테에 잘 안나오니까 개념만 알아두라고 조언해주는 걸 몇 번 봤어요.

운 안좋게 문자열 매칭 알고리즘을 써야하면 라빈-카프를 사용하라고도 하더라구요.

지피티로 검색해보니 이 문항은 슬라이딩 윈도우 알고리즘으로도 풀린다는데요..

KMP 나 라빈-카프를 익히지 않고, 윈도우 알고리즘이나 투포인터만 공부하고 넘겨도 될까요...?

zenith82114   2년 전

제 생각은 sliding window 방식만 보고 지나가셔도 될 것 같습니다. KMP를 써도 핵심 직관은 비슷하고 KMP 연습하기 더 좋은 문제가 많습니다.

pieces98   2년 전

주어진 문자열에서 어떻게 P_k를 찾고, P_k안에 P_N이 몇개 들어있는지를 고민해보시면 될것 같습니다.

.

개인적으로는 실버-골드 문제에 KMP를 가져오는 것은 닭잡는데 소잡는 칼 가져오는 격이라고 생각합니다.

뭐, 풀리기야 하겠는데, 그것을 이해하고, 실수없이 구현하는데 더 많은 비용이 든다고 생각이 됩니다.

.

문자열 알고리즘은 이걸 언제 배우고 써먹느냐는 이슈가 있죠. 트라이, KMP, 라빈-카프, 아호-코라식, ...

제가 2024년 상반기동안 백준 Open Contest를 참여 해보면서 저런 개념을 필수로 요구하는 문제는 2문제? 정도 봤습니다. 모두 플레 이상의 문제였고요. 그 문제에 가기 전에 시간이 다 되는 경우가 대부분이었습니다. 

사실, 초창기에는 'solved티어를 높이면 Open Contest도 잘 되겠지'하고 무작정 생각했었는데, 하다보니 골드3이하를 주어진 시간 내에 안정적으로 풀어낼 수 있느냐가 더 중요하더라고요. 실제로 티어를 높이기보다는 주어진 시간안에 골드3이하 문제를 안정적으로 풀어내는 것을 연습했을 때 Open Contest 성적이 더 많이 올랐습니다.

코딩테스트는 잘 모르겠습니다. 하지만 비슷할 것이라는 생각이 드네요. 코딩테스트가 문제에 저 중 하나를 요구하는 문제가 있다? 개인적으로는 그냥 그걸 빼고 최대한 푸는게 더 성적이 잘 나올거라고 생각합니다. 만약 문제수도 적고 하필 저것들로만 이루어진 문제들이 있다? 그 정도 변별력 판단을 못하는 코딩테스트를 내는 출제자가 문제가 있을거라는 생각이 드네요(물론 뭐 문자열을 전문적으로 다뤄야하는 자리라면 모르겠지요).

.

아무튼 제 개인적인 결론은 코딩 테스트에서 안정적으로 상위권에 가기 위해서 중요한 것은 "몇몇 특별한 방법론이 아닌 하나의 방법론을 다양하게 적용해보는 것"이 중요하다고 생각합니다. 그러한 관점에서 이 문제를 풀기 위해 KMP를 배우는 것은 큰 의미가 없다고 생각되네요. 

그런데 코테 그 이후를 생각하면은 잘 모르겠습니다. 제 친구 중 한명은 최근 인터뷰 자리에서 KMP에 관련된 질문을 받아본적 있다고는 하더라고요. 

wizardrabbit   2년 전

코딩 테스트 합격만을 목표로 하시는 취준생이시라면 kmp, 라빈-카프 알고리즘의 학습은 대체로 필요하지 않습니다. 이러한 알고리즘들은 기본적으로 코딩 테스트 출제 범위 바깥이며, 알고리즘 대회에서나 주로 출제되는 개념들입니다. 그 대신 말씀해 주신 두 포인터, 슬라이딩 윈도우와 같은 비교적 기초적인 알고리즘을 더 깊게 학습하실 것을 권합니다.

난이도가 비교적 낮은 알고리즘이라지만 절대로 무시할 수 없고, 쉬워 보이는 알고리즘이더라도 깊게 이해하는 것이 중요한 이유는 아래와 같습니다.

  1. 핵심적인 알고리즘들을 개념만 이해하고 연습이 부족했을 때, 실전에서 이러한 알고리즘이 필요한 문제임을 눈치채지 못하고 공략하지 못할 확률이 높습니다. 실전에서는 어쨌든 이 문제들이 어떤 알고리즘 분류인 지 알려주지 않습니다.
  2. 연습이 부족한 상태에서 코딩 테스트에 임할 경우 내가 이 알고리즘을 알고 있다고 하더라도, 조금만 응용되면 문제를 건드리지 못할 확률이 높습니다. 코딩 테스트의 문제라 하더라도 깊게 연막이 씌워져 있는 문제들은 충분히 있을 수 있습니다. 이 문제의 경우에도 kmp를 사용할 필요가 없으며 시간 복잡도에 대한 이해, 문자열에서 "IOIOI..."로 이루어진 문자열을 선택하는 약간의 문자열 구현 능력, 그리고 규칙을 찾는 것으로 문제를 풀 수 있습니다.

저는 kmp, 라빈-카프와 같은 알고리즘을 학습하는 것이 쓸모없다고 이야기하는 것이 절대로 아닙니다. 그렇지만 취준생분들에게는 시간이 없습니다. 이러한 알고리즘을 학습하기 전, 먼저 핵심적인 알고리즘들에 충분히 익숙해지고, 익숙해지기 위해 많은 문제들을 풀어보셔야 하며, 실전에 가까워지셨다면(알고리즘을 새롭게 학습하는 시기가 아닌 충분히 이 알고리즘에 익숙해진 상태) 알고리즘 분류를 보지 않더라도 시간 복잡도를 기반으로 

  • "이러한 알고리즘은 사용하면 시간 초과를 받기 쉽겠구나"
  • "이러한 알고리즘을 사용하면 아무리 비효율적이더라도 시간 내에 돌아갈 수 있겠다! 이 방법으로 시도해 보자"

와 같이, 스스로 풀이를 떠올리실 수 있어야 합니다.

답지에서 "무슨무슨 알고리즘을 써야 합니다" 여서 그 알고리즘을 사용하는 것이 아닌, "이렇게 하면 제 풀이의 시간복잡도는 ~~~이므로 입력 조건이 ~~~여도 통과할 수 있어요" 와 같이 누군가가 알고리즘 분류를 알려주지 않더라도 자신의 접근 방법을 이야기할 수 있는 것이 중요하다고 생각합니다. 여러 핵심적인 알고리즘들에 익숙해지셨고, 다양한 문제를 공략하실 수 있으시다면, 그 때 kmp나 라빈-카프와 같은 난이도가 높은 알고리즘에 도전해 보세요. 이전과 달리 알고리즘의 필요성을 이해하기에 더 좋을 것입니다. 기존에 알고 있던 다른 알고리즘들과 비교하기에도 정말 적합하고요.

핵심적인 알고리즘들을 더 연습해 보시고, 다양한 문제들을 많이 풀어보세요. 이곳 백준 게시판에서 문제 추천을 요청하시는 것도 좋은 방법입니다. 

dachaes   2년 전

이렇게까지 조언 해주시다니 솔직히 굉장히 감동받았습니다...

댓글 달아주신 모든 분들 정말정말 감사드립니다!

댓글을 작성하려면 로그인해야 합니다.