tnsbro   9달 전

이 문제를 3번에 실패 끝에 풀게 되었습니다. 처음 문제를 보고는 길이가 N인 배열을 위해서는 길이가 N-2인 배열과 길이가 N-1인 배열에 대한 정보가 필요할 것이라 생각해 무작정 모두를 기록하고 중복을 확인하였습니다. 아예 틀린 접근이라고는 할 수 없지만 그 과정에서 제가 간과한 중요한 포인트는 길이가 N-2인 배열과 길이가 N-1인 배열에서 뒤에 하나의 요소만 붙이면 된다는 것이었습니다. 이를 생각 못 하고 배열 사이에 넣을 수 있는 모든 경우를 다 확인해버려 시간초과로 2번. 그 후 아예 그냥 조합의 경우의 수로 접근해서 시간초과로 1번 실패했네요. 그 후 게시판을 보고 놓친 포인트를 알 수 있었는데, 특히 이 문제가 요구하는 핵심은 단순 하드코딩이 아니라 아이디어? 관찰을 통한 발상 및 깨달음? 인 것 같은데 이 역량이 잘 길러지지 않는 것 같아요. 이런 부분을 어떤 방법으로 점점 발전해나갈 수 있는지 따끔한 조언 부탁 드립니다.

zenith82114   9달 전

처음 보는 개념/유형을 제대로 못 푸는 것은 이상한 일이 아니니, 적당한 시도 후 해답을 보고 잘 정리해서 다음부터는 풀 수 있게 되면 충분합니다.

말씀하시는 아이디어나 관찰력은 특정 알고리즘만 파기보다는 다양한 스타일의 문제들을 골고루 풀어야 빠르게 훈련됩니다. solved.ac 프로필 그래프에 보이시듯 푸신 문제들이 수학, 구현 등 특정 분야에 치중되어 계신데, 최소 골드에 도달할 때까지는 클래스나 단계별 풀어보기를 따라가시기를 추천합니다.

wizardrabbit   9달 전

질문자님께서 말씀하신 역량을 저는 발상과 관찰을 통해 아이디어를 잘 찾아내는 역량, 그리고 가망이 없는 풀이를 구현으로 옮기지 않고 거르는 역량으로 나눌 수 있을 것 같아요.

1. 발상과 관찰을 통해 아이디어를 잘 찾아내는 역량

발상과 관찰을 통해 아이디어를 잘 찾아내는 역량은 질문자님께서 알고 계신 여러 알고리즘 혹은 발상을 제대로 떠올려야 공략을 알아낼 수 있어요. 이건 질문자님의 연습과 경험에 기반하기 때문에 단기간에 오르지 않으며 꾸준히 문제를 푸셔야 오르는 역량이라 생각해요. 고민을 잘 해볼 수 있는 연습법을 잘 활용하시면 된다고 봅니다. 여긴 편법이 없다고 보아요.

  • 알고리즘 분류 및 답지를 보기 전 충분한 시간(30분 정도) 고민해보기
  • 풀지 못한 문제나 긴가민가한 문제는 빠른 시일 내 다시 풀어 복습하기
  • 다른 사람의 코드 꼭 참고하기
  • ...

박수현님의 코딩 테스트 및 알고리즘 문제해결 공부 방법 (고려대학교 KUCC, 2022년 4월) 자료를 추천드려요. 24페이지부터 문제를 풀며 연습하는 방법이 적혀 있어요.

여기까지만 보면 "그냥 열심히 연습해라" 로 끝날 조언이 되는데, 제가 사실 하고 싶은 이야기는 이게 아니에요. 어찌됐든 이 역량은 꾸준히 해야 오르고, 질문자님도 꾸준히 하실 것이기 때문이에요.

2. 가망이 없는 풀이를 구현으로 옮기지 않고 거르는 역량

저는 사실, 이 이야기를 해 보고 싶었어요.

가망이 없는 풀이를 구현으로 옮기지 않고 거르는 역량은 문제를 푸는 데 있어 적합하지 않은 풀이를 배제할 뿐만 아니라, 그것을 분별할 수 있는 역량이에요. 이게 무슨 뜻이고 뜬금없이 왜 언급되느냐? 라고 생각하실 거에요.

질문자님께서는 본 문제의 풀이가 다이나믹 프로그래밍이라는 것을 알아내기 전에 여러 시도들을 해 보셨는데, 효율성 문제로 시간 초과를 받으셨다고 말씀해주셨어요. 질문자님께서는 그 접근들을 구현으로 옮기기 전 효율성에 대한 걱정과 분석을 혹시 해 보셨나요?

시간복잡도를 아마 들어보셨을 거에요. 시간복잡도를 간단하게 요약하면 알고리즘의 실행 시간이 입력 데이터의 크기에 따라 어떻게 변하는지를 나타내는 척도라 할 수 있어요. 이걸 알면 무엇이 좋냐면, 생각한 아이디어(알고리즘)을 문제 조건을 보았을 때 실행시간을 지키며 작동할 수 있는가를 이론적으로 미리 알 수 있게 돼요. 실전적으로 활용할 때에는 초당 컴퓨터가 할 수 있는 연산 수를 1억 ~ 수억 번 쯤으로 잡고, 현재 시간복잡도를 생각했을 때 연산 횟수가 어떻게 될 지를 생각해 보는 거에요(하지만 각 연산의 비용은 크게 차이가 나므로 실행시간을 정확히 예측하는 것은 부적합하며, 가망이 없는 알고리즘을 거를 때 좋습니다.)

예를 들어 볼까요? 최악의 경우 $N = 5\,000$로 주어지고, 제한 시간이 $1$초인 문제가 있어요. 이 문제를 $N$값을 사용하는 이중 반복문으로 만든다면, 이중 반복문이라 시간복잡도가 $O(N^2)$인 등 다소 좀 꺼림칙해 보이지만, 연산 횟수의 경우 $2000$만 번 가량이 되기에 이 방법을 충분히 활용할 수 있음을 알 수 있어요. 반면 삼중 반복문을 사용($O(N^3)$)한다면 연산 횟수는 $1250$억이나 되기에 시간 제한을 절대 지킬 수 없음을 구현하기 전 알 수 있어요.

"이 문제는 왜 다이나믹 프로그래밍일까요? 일일이 모든 경우를 브루트포싱하는 것 안 될까요?" 에 대한 대답도 시간복잡도가 해 줄 수 있어요. 세상 모든 문제가 브루트포스 알고리즘으로 풀린다면 다른 거창한 알고리즘은 굳이 필요하지 않을 거에요. 하지만 이 문제에서는 효율성이 따라주지 않기 때문에 필요했어요. 다른 문제들도 다른 접근 방법을 고수해야만 하는 상황을 이해하셔야 그 다음으로 나아가실 수 있다 생각해요.

3. 결론

아이디어와 경험은 문제를 푸시면서 계속 얻어가세요. 단기간에 늘지 않아요.

그 대신, 시간복잡도를 이용해 생각하는 모든 풀이에 대해 꼼꼼한 검증을 마치고 접근해보세요. 이건 단기간에도 적용이 될 거에요.

접근 방식을 고민하고 잘못된 접근 방법을 걸러내며 문제풀이에 임하는 것은 진짜 정답인 풀이를 사용하는 것에 대한 정당성을 더 쉽게 깨닫고 정답 범위를 좁히는 데에 많은 도움을 줄 거에요!

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