211110 구현 개념

• 구현 개념
  • 구현시 고려해야할 메모리 제약 사항
    • 리스트의 크기 제약
  • 채점 환경
  • 구현 문제에 접근하는 방법
  • 예시 문제

구현 개념

코딩 테스트에서 구현Implementation 이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 그러므로 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않는다.

우리는 알고리즘 문제를 해결할 때, 문제를 읽고 문제풀이 방법을 고민한다. 고민 끝에 문제에 대한 정확한 풀이 방법을 우리가 원하는 프로그래밍 언어로 정확히 구현했을 때 비로소 정답 처리를 받을 수 있다. 이를 위해 프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한다.

흔히 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제' 를 의미한다. 흔히 개발할 때 프로그래밍 언어의 문법에 능숙하고 코드 작성 속도(타자) 가 빠른 사람을 보고 '피지컬이 좋다' 고 하는데, 구현 유형의 문제는 '피지컬을 요구하는 문제' 라고 할 수 있다.

대체로 사소한 조건 설정이 많은 문제일 수록 코드로 구현하기가 까다롭다. _{ex) 알고리즘은 간단한데, 코드가 지나칠만큼 길어지는 문제 / 특정 소수점 자리까지 출력해야하는 문제 / 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는 (파싱을 해야하는) 문제 등}
이는 언어의 문법을 잘 이해하고, 경험이 있어야만 바로 떠올릴 수 있는 해결방법이다.

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

구현시 고려해야할 메모리 제약 사항

리스트의 크기 제약

대체로 코딩 테스트에서는 128 ~ 512MB 로 메모리를 제한하는데, 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야하는 문제가 출제되곤 한다. 이럴 때는 메모리 제한을 염두해 두고 코딩해야한다. 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하도록 하자.

그러나 일반적인 코딩 테스트 수준에서는 메모리 사용량 제한보다 더 적은 크기의 메모리를 사용해야한다는 점 정도만 기억하면 된다.

채점 환경

문제에서 요구하는 메모리 제한과, 실행 시간 제한은 코딩테스트를 출제하는 기관,문제마다 조금씩 다르다. 일반적인 코딩 테스트 환경에서는 다음과 같은 채점 시스템의 시간 제한 및 메모리 제한 정보가 적혀있다.

• 시간 제한: 1초
• 메모리 제한 : 128MB

자신의 코드가 1초에 2,000만 번의 연산을 수행 한다고 가정하고 문제를 풀면 실행 시간 제한에 안정적이다. 알고리즘 문제를 풀 때는 시간 제한과 데이터의 개수를 먼저 확인한 뒤에 문제를 어느 정도의 시간 복잡도의 알고리즘으로 작성해야 풀 수 있을 것인지 예측할 수 있어야 한다.

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건 등을 문제에서 명시해주며, 문제의 길이가 꽤 긴 편이다. 문제의 길이를 보고 지레 겁먹는데, 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문법에 익숙하다면 오히려 쉽게 풀 수 있다.

_{API 개발 문제 또한 구현 유형과 상당히 맞닿아 있다. 예를 들어 카카오 공채 때 API 개발 문제가 출제된 적 있는데, 이때 카카오 문제 풀이 서버와 통신하는 프로그램 모듈을 작성해야했다.}