[알고리즘, 코딩테스트] 문제풀이 방법론에 대하여

기본

절대 답을 먼저 살피지말고 직접 풀이한다

 

본론

1.경청(정독)하라

- 기본중에 기본이다. 모든 조건과 상황(반복되는것인가 정렬이 이미되어있는것인가 등)을 정확히 알아야한다.

 

2.예제를 직접 작성하라

- 머릿속에서만 생각한 후 곧바로 문제를 풀지말고 예제를 작성하여 테스트하라

- 이때, 

   문제에맞는 실제 숫자와 문자열을 사용하며, 특별한 케이스의 예제는 지양한다

- 크기가 크며 구체적인 예제를 만든다.

 

3.무식하게 먼저 푼다.

- 2번예제를 통해만들어진

   문제에적합하고, 크기가크며, 구체적인예제를 바탕으로 직관적으로 풀어본다.

- 복잡한 제약조건은 단순화해도 괜찮다.

- 첫 알고리즘이 형편없어도 괜찮다. 

4번에서 개선해나가면 된다.

 

 

4.최적화한다.

- 1번에서 인지한 정보중 놓친 정보가 있는지 체크한다.

- 2번의 방향성으로, 더 추가적인 예제로 테스트를한다.

- BUD를 활용하여 최적화한다.

- 시간,공간복잡도를 생각하여 최적화한다.

 

*BUD란?

병목현상(Bottlenecks)

- O(n)작업과 O(nLogN)작업이 같이 이루질 때, O(n)작업을 O(logN)으로 줄이는것은 의미가없다.

  즉, 실제로 병목현상이 발생하는 구간을 최적화해야한다.

- 반복적으로 일어나는 구간을 O(1)에 가깝게 최적화하는것은 굉장한 효율을 불러온다.

불필요한작업(Unnecessary Work)

중복되는 작업(Duplicated Work)

 

5.검토하라.

- 코딩을 시작하기전에 '완벽'에 가까운 상태를 만들어 둔 후 코딩을 시작해야한다. 다시검토하자.

- 완벽에 가까우려면 코드도 얼추 나와야한다. 

 

6.코드를 작성하라.

- 1~5번의 과정을 통해 나오는 코드는 첫 시작부터 설계가 된것이다.

- 모듈화된 코드를 작성하고, 검증이 필요한 코드도 추가한다.

- 이 때, 좋은 변수명을 사용한다.

- 의사코드보다는 실제코드에 가깝게 작성해야한다.

 

7.테스트한다.

- 2번, 4번의 예제로 테스트한것은 일반적인경우였을 것이다.

- 이 때에는 상세한부분까지 테스트를한다.

7.1.개념적 테스트부터 시작한다.

   (코드를 한줄한줄 읽어내려가며 분석한다. 면접관에게 설명하듯이)

7.2.코드가 평소와 다르게 돌아가는부분을 유심히 살핀다

   (예를들어, for(int i=0; 이 아니라 for(int i=2; 로 동작하는 코드와 같이 일반적이지 않은 부분들을 의미)

7.3.버그가 자주 발생하는 부분을 체크

   (NULL체크, 정수나눗셈, 등)

7.4.특별한경우를 테스트한다.

   NULL, 단일원소, 극단적인일벽 등 ..)

 

8.코딩한다.

 

 

즉 1~7번까지 손으로 해야한다.

코딩은 마지막 표현의 수단일 뿐.

시간은 오래거리지만 문제를 즈려밟겠네요.

 

 

 

이런 방법론을 적용해보고자 시스템을 구축하려고합니다.

 

1.

먼저 github에 레포를 팔것인데,

이곳에는 알고리즘문제풀이내용을 저장할것입니다.

 

2.

각 문제는 디렉토리구조로 저장됩니다.

알고리즘 > 문제정보(백준넘버, 프로그래머스넘버, 문제이름) > 코드파일, 이미지파일

 

3.

이때의 이미지파일은 방법론 1~7의 경과입니다.

 

4.

이미지파일을 기반으로 코드를 작성하고,

이후의 리팩토링에 대해서는 깃헙의 커밋내용에 의존합니다.

(종이에 작성하는것의 한계로, 지속되는 리팩토링을 종이에 반영하면 지저분해질것이라 판단)

 

 

 

해보긴할건데,

솔직히 잘 될지는모르겠습니다.

뭐 하다보면

이 방법을 버리거나

그대로 따르거나

아니면 저에게맞는 더 나은 방법을 찾아가곘죠.