코테 문제 분석 연습
무작정 코드를 작성하기 보단 문제 분석에 시간을 충분히 사용해야 한다. 대부분 2시간에서 4시간 정도 문제 풀 시간을 주므로 전체 시간의 50~60% 정도는 문제 분석에 시간을 쓰는 것이 좋다.
1. 문제를 쪼개서 분석
•
문제 전체를 한번에 분석하는 것보다 문제를 동작 단위로 쪼개서 분석하는 것이 유리하다.
2. 제약 사항을 파악하고 테스트 케이스를 추가
•
문제에는 보통 제약 사항이 있다. 제약 사항을 정리해두고 이를 고려하여 테스트 케이스를 추가하는 연습을 하는 게 좋다.
•
이 과정은 어떤 알고리즘을 사용할지 고민할 때 유용하고, 추후 코드를 구현하는 단계에서 예외를 거를 때 도움이 된다.
3. 입력값을 분석
•
입력값의 크기를 확인하면 문제를 제한시간 내에 풀 수 있는 알고리즘과 그렇지 않은 알고리즘을 미리 걸러낼 수 있다. 예를 들어 입력 데이터가 100만 개라면 O(N * N) 알고리즘으로는 맞는 코드를 작성해도 시간 내에 출력값이 나오지 않으므로 테스트를 통과할 수 없다. 그러니 구현 전에는 반드시 입력값을 분석해야 한다.
4. 데이터 흐름이나 구성 파악
•
데이터의 삽입과 삭제가 빈번하게 일어나는 상황에서 최댓값 혹은 최솟값을 반복하여 구해야 한다면 힙(heap) 자료구조를 고려하는 게 좋을 수 있다.
•
데이터가 50개 미만이고 입력값을 깔끔하게 정리하기 어렵다면 하드 코딩을 고려하기도 한다.
•
또, 데이터 값의 차이가 크면 데이터값 자체를 배열의 인덱스로 활용하는 건 피하는 게 좋다.
◦
{1, 10100, 5000} 으로 데이터가 구성되어 있으면 데이터값을 인덱스로 썼을 때 2~4999, 5001~10099의 공간은 사용하지 않는 공간이지만 메모리에 할당하게 되므로 낭비이다.
의사 코드로 설계하는 연습
의사 코드는 프로그램의 논리를 설명하고 알고리즘을 표현하기 위해 작성한 일종의 지침이다.
•
원칙 1 : 프로그래밍 언어로 작성하면 안 됨
•
원칙 2 : 일반인도 이해할 수 있는 자연어로 작성해야 함
•
원칙 3 : 일정한 형식이 없음(자유롭게 작성)
1. 세부 구현이 아닌 동작 중심으로 작성
의사 코드는 동작 중심으로 작성하는 것이 중요하다. 세부 구현을 고민하는 순간부터 의사 코드는 설계가 아닌 구현이 주 목표가 된다. 이러면 의사 코드를 작성하는 장점이 사라진다.
예를 들어 성적 관리프로그램을 만든다고 가정할 때 성적을 입력받는 부분을 의사 코드로 작성한다고 하면 다음과 같이 작성하면 된다.
•
국어, 영어, 수학 점수를 입력받는다.
2. 문제 해결 순서로 작성
의사 코드가 완성되면 이를 토대로 코드를 구현할 것이므로 의사 코드는 문제 해결 순서대로 작성해야 한다. 또 의사 코드 자체는 실제 구현할 코드의 주석이 되기도 하므로 이렇게 순서대로 작성하면 나중에 자신의 코드를 분석하기에도 상당히 용이하다. 예를 들어 영어 점수를 입력받아 60점 기준으로 통과, 실패를 판별하는 의사 코드는 다음과 같이 작성하면 된다.
1.
영어 성적 입력
2.
영어 성적이 60점을 넘는지 확인(분기)
a.
2-1: 60점 이상이면 통과
b.
2-2: 60점 미만이면 실패
3. 충분히 테스트한다
구현전 마지막 단계는 충분히 테스트해야 한다는 것이다. 구현 단계로 갈수록 잘못된 부분을 수정하는 데 드는 비용은 점점 커지므로 의사 코드가 미리 생각해본 테스트 케이스를 통과할 수 있을지를 고민해봐야 한다. 충분한 고민 후에 의사 코드가 대부분의 테스트 케이스를 통과할 수 있을 것 같을 때 구현을 시작하면 된다.