Codility 스타일 코딩 테스트 연습

실제 시험은 보통 어떤 방식인가요

Codility 테스트는 하나로 정해져 있지 않습니다. Codility는 플랫폼입니다. 각 고용주가 테스트에 포함할 과제와 허용 언어, 제한 시간을 정합니다. 본인에게 주어질 테스트의 내용은 고용주가 보낸 안내문을 확인하는 것이 가장 좋습니다.

Codility가 설명하는 내용. Codility에 따르면 각 과제는 정해진 기준에 따라 자동으로 점수가 매겨집니다 (Codility). 프로그래머를 위한 무료 레슨 (Codility)을 보면 짧은 문제, 작성해야 할 함수, 명시된 입력 제한 등 과제의 형식을 확인할 수 있습니다. 예를 들어 BinaryGap 레슨 과제는 최대 2,147,483,647까지의 입력에 대해 "효율적인 알고리즘"을 작성하도록 요구합니다 (Codility). 레슨 중 하나의 제목은 Time Complexity입니다 (Codility).

Codility 테스트에 관해 흔히 알려진 내용 (응시자와 가이드에서 전하는 정보이며, 저희가 접속해 확인할 수 있었던 Codility 페이지에서는 확인되지 않았습니다):

• 전체 테스트에 타이머 하나가 적용되고 과제는 몇 개이며, 제한 시간은 흔히 30분에서 2시간 사이입니다.
• 비공개 정답 판별 테스트: 과제에 나온 예시 외에도 응시자에게 공개되지 않는 사례를 기준으로 코드를 확인합니다.
• 알고리즘 과제는 큰 입력에서의 성능도 중요합니다. 정답이지만 느린 풀이로는 점수를 잃을 수 있습니다.
• 제한 시간 안에 얼마나 빨리 푸는지는 점수에 반영되지 않습니다.

모의고사에서 다루는 내용. 전체 모의고사 하나는 쉬운 과제부터 어려운 과제까지 90분 동안 코딩 과제 3개를 푸는 구성입니다. Python, JavaScript, Java 또는 C++로 풀이를 작성하고 실행하면, 비공개 테스트 사례로 채점되며 통과한 사례마다 점수를 받습니다. 노트북 사용을 권장합니다. 제출하기 전까지 이전 문항으로 돌아가 풀이를 수정할 수 있습니다.

모의고사의 차이점. 실제 Codility 과제는 정답 여부와 함께, 많은 과제에서 큰 입력에 대한 성능도 확인하는 것으로 알려져 있습니다. 저희는 크기가 작은 비공개 사례로 정답 여부와 경계 사례를 확인하므로 느린 풀이도 시간 초과되지 않습니다. 각 과제의 해설에는 큰 입력에 어떤 시간 복잡도가 필요한지 설명되어 있습니다. 무료 문제 10개는 정답 여부, 복잡도, 경계 사례, 속도에 관한 객관식 문제로, 이러한 검사를 통과하는 데 필요한 사고방식을 연습합니다.

풀이 예제가 포함된 문제 유형

각 유형의 문제에서 풀이 예시를 하나씩 살펴보고, 많은 사람이 빠지는 함정도 알아봅니다.

1. 올바른 풀이 찾기. 과제: 목록에 있는 고유한 값의 개수를 반환합니다. 풀이: len(set(A)). 빈 목록을 포함한 모든 목록에서 맞는 답을 반환하며, 빈 목록의 결과는 0입니다. 함정: 정렬된 목록으로 직접 반복문을 작성하고 첫 번째나 마지막 항목을 놓치는 것입니다. 내장 기능으로 해결할 수 있다면 경계 사례도 처리하는지 확인한 다음 사용하세요.

2. 시간 복잡도. 한 풀이에서는 A를 반복하면서 반복문 안에서 max(A[:i])를 호출합니다. 슬라이스와 max는 각각 최대 i개의 항목을 확인하므로 총 작업량은 약 N의 제곱을 2로 나눈 단계, 즉 O(N의 제곱)입니다. 대신 최댓값을 계속 업데이트하면 O(N)이 됩니다. 함정: 반복문이 하나라고 보고 O(N)이라고 판단하는 것입니다. 반복문 안에 슬라이스, 합계, 개수 세기, 검색이 있는지 확인하세요.

3. 어떤 입력에서 오류가 날까요? 과제: A에 없는 가장 작은 양의 정수를 반환합니다. 한 풀이는 max(A) + 1을 반환합니다. A = [1, 2, 3]을 넣으면 4를 반환하므로 맞습니다. A = [1, 3]을 넣으면 4를 반환하지만 2가 빠져 있으므로 답은 2입니다. A = [-3, -1]을 넣으면 0을 반환하지만 답은 1입니다. 함정: 한 사례에서 제대로 작동하는 것을 확인한 뒤 멈추는 것입니다. 빠진 값이 있는 경우, 모두 음수인 경우, 허용된다면 빈 목록, 항목 하나, 모두 같은 값, 허용된 최댓값을 의도적으로 경계 사례로 확인하세요.

4. N이 최대 100,000일 때 충분히 빠른 풀이. 대략적인 기준으로 이 크기에서는 O(N) 또는 O(N log N)을 목표로 하세요. O(N의 제곱)은 약 100억 단계로, 일반적인 제한 시간보다 훨씬 오래 걸립니다. 함정: 어떤 접근법이든 즉시 끝나는 것처럼 보이는 항목 10개로만 테스트하는 것입니다. N이 커질수록 작업량이 어떻게 늘어나는지 생각하세요.

5. 제한 조건 읽기. 값이 최대 1,000,000,000이고 N이 100,000이라면 합계는 100조까지 커질 수 있습니다. Python의 정수는 이를 처리하지만, 정수 크기가 고정된 언어에서는 오버플로가 발생합니다. 함정: 값의 범위를 무시하는 것입니다. 값의 범위는 오버플로 가능성뿐 아니라 개수 세기 배열 같은 기법을 사용할 수 있는지도 알려줍니다.

준비 방법

1. 먼저 안내문을 확인하세요. 과제 수와 전체 제한 시간, 허용 언어를 확인하세요. 이 항목들은 고용주가 정하므로 미리 짐작하지 마세요.
2. 잘 아는 언어 하나를 사용하세요. 목록, 딕셔너리, 집합, 정렬, 문자열 메서드를 찾아보지 않고 사용할 수 있도록 익혀 두세요.
3. 코딩 전에 제한 조건을 확인하세요. 과제에 명시된 입력 크기와 값의 범위를 보면 풀이가 얼마나 빨라야 하는지, 어떤 경계 사례가 중요한지 알 수 있습니다. Codility의 레슨 과제도 마찬가지입니다 (Codility).
4. 정확하게 푼 다음 속도를 높이세요. 먼저 간단하고 정확한 풀이를 작성하세요. 시간 복잡도가 O(N squared)이고 N이 100,000까지 커질 수 있다면 누적 합, 딕셔너리, 집합 또는 정렬을 활용해 복잡도를 낮출 방법을 찾아보세요.
5. 경계 사례를 직접 테스트하세요. 과제에 나온 예시는 여러 사례 중 하나일 뿐입니다. 허용되는 경우 빈 입력, 항목 하나, 모두 같은 값, 음수, 최솟값과 최댓값, 가장 큰 N을 테스트하세요.
6. 자주 쓰이는 패턴을 익히세요. 누적 합, 슬라이딩 윈도우, 딕셔너리를 이용한 개수 세기, 투 포인터, 먼저 정렬하기, 간단한 그리디 선택은 짧은 알고리즘 과제의 상당 부분을 다룹니다. Codility의 무료 레슨에서 문제 형식을 살펴보세요 (Codility).
7. 시간을 재고 완성된 풀이를 작성하세요. 전체 모의고사에서는 직접 코드를 작성하고 실행해 비공개 사례를 확인합니다. 같은 방식으로 연습 문제를 풀어 보며 시간 안에 작성하는 데 익숙해지세요.
8. 실제 속도에 맞춰 연습하세요. 전체 시간 제한 모의고사를 풀어 시험 당일 세 과제를 하나의 타이머에 맞춰 푸는 상황에 익숙해지세요.

일반적인 채점 방식

채점 방식은 고용주마다 다릅니다. Codility에 따르면 각 과제는 정해진 기준에 따라 자동으로 채점되며 (Codility), 어떤 결과를 충분하다고 볼지는 고용주가 결정합니다. 모두에게 적용되는 합격 기준은 없습니다.

일반적으로 알려진 채점 기준의 작동 방식은 다음과 같습니다. 과제 점수는 공개되지 않은 정답 확인 테스트와, 많은 알고리즘 과제의 경우 대량 입력에 대한 성능 테스트를 바탕으로 산출됩니다. 이 결과가 과제별 백분율로 합산되고, 다시 테스트 점수로 합산됩니다. 작은 입력에서는 맞지만 큰 입력에서 너무 느린 솔루션은 성능 점수를 잃을 수 있고, 경계 사례 하나에서 실패하면 정답 점수의 일부를 잃습니다. 그래서 모의 테스트에서는 "정답인가요?"와 "충분히 빠른가요?"를 따로 묻습니다.

연습 점수는 과제별로 나뉘어 표시되는 자체 문항의 정답 수입니다. 이를 통해 어디에 집중할지 확인할 수 있습니다. 이 점수는 연습 점수이며, Codility 점수나 고용주의 결과가 아니고 합격 여부를 예측하지 않습니다.

흔한 실수

• 예제를 그대로 믿기. 문제의 예제는 숨겨진 여러 사례 중 하나입니다. 예제를 통과해도 점수 대부분을 얻지 못할 수 있습니다.
• N을 무시하기. 올바른 O(N squared) 풀이도 N = 100,000일 때 성능 검사에서 실패할 수 있습니다. 먼저 제한을 확인하세요.
• 반복문 안에 숨은 작업. 반복문 안에서 리스트를 슬라이스하거나 합계, 개수, 인덱스를 구하거나 "in"으로 확인하면 비용이 커집니다.
• 마지막 항목을 놓치기. 범위에서 인덱스를 하나씩 잘못 계산하거나 리스트 끝에서 종료하는 반복문은 흔한 실패 원인입니다. 마지막 단계를 직접 따라가 보세요.
• 시작값이 잘못되기. 최댓값을 0으로 시작하거나 최솟값을 임의의 큰 수로 시작하면 음수나 매우 큰 값에서 문제가 생깁니다. 첫 번째 항목에서 시작하세요.
• 문제가 전제하는 순서를 바꾸기. 정렬은 유용하지만, 답이 위치나 "리스트에서 첫 번째"에 따라 달라질 때는 적절하지 않습니다.
• 한 문제에 시간을 모두 쓰기. 먼저 모든 문제에 대해 올바른 버전을 제출한 다음, 시간이 허락하면 속도를 개선하세요.