구현 알고리즘

본 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬' 책을 기반으로 포스팅 하였습니다.

 

구현 알고리즘이란?

구현 알고리즘이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' 이다.

 

구현 문제

구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 를 의미한다.

예시) 완전 탐색, 시뮬레이션 유형

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

 

구현하기 어려운 문제

1. 알고리즘은 간단하나 코드가 지나칠 만큼 길어지는 문제
2. 특정 소수점 자리까지 출력해야하는 문제
3. 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등등

※ 구현 문제를 조금더 쉽게 풀기 위해서는 문법 숙지와 라이브러리 경험이 필요하다.

 

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

보통 프로그래밍 언어에서 정수형을 표현할 때는 int형을 주로 사용한다.

int형의 크기는 4바이트이며 표현 범위는 -2,147,483,648 ~ 2,147,438,647인데 이 말은 int형으로 처리하면 2,147,438,647보다 큰  수는 처리하지 못한다.

이때 이보다 더 큰 수를 처리하기 위해서는 크기가 8바이트인 long long과 같은 자료형을 사용하는데 이 또한 9,223,372,063,854,775,807보다 큰 수를 처리할 수 없다.  

그러나 대부분 코딩테스트 문제에서는 long long에서 다룰 수 있는 수보다 더 큰 정수를 처리하는 문제는 잘 출제되지 않는다.

 

구현 문제에 접근하는 방법

보통 구현 유형의 문제는 사소한 입력 조건등을 문제에서 명시애주며 문제의 길이가 꽤 긴 편이다.

하지만 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이며 문법에 익숙하다면 쉽게 풀 수 있다.