[구현] 알고리즘 개념

구현

• 코딩테스트에서 자주 출제되는 유형
• (1) 정확한 풀이 방법, (2) 프로그래밍 언어 문법의 이해를 바탕으로 완벽한 구현
• 구현 : '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'
• 알고리즘 설계 후, 먼저 풀 문제가 없을 때 푸는 문제
• 피지컬을 요구하는 문제
• 언어의 문법(라이브러리)을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법
• 코테에서 1~2번 문제는 대부분 그리디 or 구현 → 합격을 좌우

구현하기 어려운 문제

• 코드가 지나칠 만큼 길어지는 문제
• 특정 소수점 자리까지 출력해야 하는 문제
• 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등

유형

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

 

 

프로그래밍 언어 별 메모리 제약 사항

C/C++ 과 자바

int : -21억 ~ 21억, 4byte

 

 

파이썬

• 프로그래머가 직접 자료형을 지정할 필요 없음
• 매우 큰 수의 연산을 기본으로 지원
• 자료형의 표현 범위 제한에 대해 깊게 이해하지 않아도 됨

단, 코딩 테스트에서는... 대체로128 ~ 512MB 메모리 제한

데이터 처리량이 많을 때는 메모리 제한 고려

리스트 여러 개일 때, 크기 1,000만 이상인 리스트가 있으면 메모리 용량 제한 걸릴 수 있음 → 드뭄

 

 

시간 복잡도

시간 제한이 1초이고, 데이터의 개수가 100만 개인 문제

일반적으로 시간 복잡도 O(NlogN) 이내의 알고리즘 적용해야 함

→  문제를 보고, 어느 정도의 시간 복잡도 알고리즘으로 작성해야 풀 수 있을 것인지 예측~

 

 

 

접근 방법

'구현' 유형에서는 문자열, 정수 처리 문제가 많기에 파이썬 유리함