#2. 구현

구현이란?

머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하기 : 피지컬

딱히 뭐 설명할 말이 없다. 그냥 주어진 대로 구현하는 형식의 문제다!

이 파트에서 다루는 문제 유형

지금 읽고있는 킹동빈 님의 '이것이 취업을 위한 코딩 테스트다' 에서는 구현 파트에 아래의 두 유형의 문제를 엮었다.

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법
• 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행

구현 문제의 특징

구현 문제의 특징으로는, 사소한 입력 조건 등을 문제에서 제시해 준다. 그렇기 때문에 보통 문제 길이가 긴 편이라, 문제를 읽기도 전에 문제 길이에 압도당해 지레 겁을 먹는 경우가 많다.

 

그러지 말자! 딱히 어떤 알고리즘 지식을 알고 있어야만 풀 수 있는 문제도 아니고, 차근차근 읽어보면 은근 ㅈ밥 인 문제도 많다.

구현이 어렵게 느껴지는 이유

그럼에도 불구하고 우리가 구현 문제를 어려워 하는 이유는 크게 2가지다.

1. 실제로 문제가 더러운까다로운 경우
   • 사소한 조건 설정이 많다 (주로 시뮬레이션 문제)
2. 문법 이해 / 라이브러리 사용 경험이 부족한 경우
   • ex) 순열 및 조합 관련된 문제 : python의 itertools 와 같은 표준 라이브러리를 모르면 당황할 수 있음

1번과 같은 이유로 힘들어한다면, 주로 처음 설계를 아예 잘못 했거나, 잘 가다가 '이렇게 푸는거 맞나'하는 경우가 많을 것이다.

하지만 중요한 것은, 우리는 시간안에 해결해야 한다. 우선 처음 설계를 잘 해야 하는 것도 맞지만, 어지간히 잘못한 게 아니라면 고민할 시간에 차라리 빠르게 집중해서 구현을 끝내는 연습을 자주 하자. (이건 내 개인적인 의견이다. 그리고 코테 말고 실제 개발에서는 반대로!)

 

2번은 문제를 최대한 많이 풀어보고, 다른 사람들의 코드도 참고하면서 표준 라이브러리에서 제공하는 함수들에 익숙해지는 방법 밖에 없다. 내 손에 어떤 도구가 들려있는지도 모르면, 문제를 해결할 방법을 절대 쉽게 찾을 수 없다.

접근 방법

1. 우선 조건을 보고 모든 경우를 다 시도할 수 있는지 판단
   1. 생각한 알고리즘의 시간 복잡도 계산
   2. 시간 복잡도와 데이터 수 n을 고려한 총 연산 수 ≤ 2,000만 (파이썬 기준) → 모든 경우 시도 가능!
      ( 일반적인 채점 환경인 시간제한 1초 기준, 파이썬은 1초에 2,000만번 정도 연산을 수행할 수 있다고 생각하면 된다)
      

      * 참고 *
      N ≤ 500 : O(N³) 으로 가능
      N ≤ 4,000 : O(N²) 으로 가능  
      N ≤ 1,000,000 : O(NlogN) 으로 가능 (약 19,900,000이라 주의)  
      N ≤ 10,000,000 : O(N) 으로 가능  
        * 위 숫자는 대략적인 수치
        * 정확한 계산 보다는 빨리 파악하고 어떤 방식으로 풀 지 결정하는 용도
        * 그리고 대부분의 문제는 애매한 n은 주지 않는다. 즉 어떤 방식으로 풀어야 할 지 명확하게 판단 가능!

2. 모든 경우의 수 중에 처리해야 할 예외가 있는 지 판단
3. 쌉 코딩
   1에서 모든 경우의 수를 시도할 수 있다는 판단을 했으면, 의심 ❌ → 구현에 집중!

이렇게 적어놨지만, 시뮬레이션 문제는 대부분 시간 복잡도를 고려하지 않고 구현에만 집중해도 풀 수 있다. 완전 탐색 문제인가 라는 생각이 들면 위의 방법대로 시간 복잡도를 고려 해보고, 완전 탐색으로도 풀 수 있는지 생각해 보자. 그리고 풀 수 있다는 판단이 서면, 그때 부터는 구현에 집중하자!