2. 구현

구현(Implement)

개요

머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제들이 많다. 또한 문제가 길거나, 문제의 조건이 많은 것들이 구현으로 구분된다.

구현 문제는 프로그래밍 문법의 숙지가 미흡하거나, 라이브러리 사용 경험이 부족하면 문제 풀이가 더욱 어렵다.

예를 들면 순열을 구현해야 하는 문제에서 C++의 STL을 모르거나 PYTHON의 itertools를 모른다면 생짜로 구현해야 하는 상황이 올 수도 있는것이다.

구현 문제에서는 다른 것 보다 특히 메모리 제약사항을 눈여겨 보아야 한다. C언어라면 정수의 표현 범위일 것이며, 파이썬이라면 리스트의 크기 정도가 될 수 있다.

대체로 문제에서는 128~512MB의 메모리로 제한하는데, 이때는 들어오는 값의 범위를 잘 고려해서 알고리즘을 설계해야한다.

일반적으로 코딩테스트에서는 파이썬으로 제출한 코드가 1초에 2,000만번의 연산을 수행한다 라고 했을때 무리가 없다

✔예를 들어 시간제한이 1초이고 데이터 개수가 100만개라면 $$O(N\log N)$$ 이내의 알고리즘을 이용해야한다.

완전 탐색(Brute Force)

개요

가능한 모든 경우를 훑는 방법이다. 가장 강력하면서 시간은 그만큼 많이 든다.
모든 경우를 다 훑을 수 있어 확실한 정답을 가져올 수 있고, 구현이 어렵지 않지만, 효율적이지 못하며, 실행시간이 오래걸린다는 단점이 있다.

완전탐색 종류

• 비트마스크 : 비트 단위로 값을 보존하는 것, 값 하나로 여러개의 상태를 표시할 때 사용하는 최적화 기법이다.

• 순열

• 백트래킹 : DFS를 진행하다가 조건이 맞지 않으면 바로 전 상태로 돌아가는 것.

• DFS / BFS : 그래프 탐색 기법

위 알고리즘 또는 기법들은 따로 빼어 포스팅 할 예정이다.

문제

야구 게임
BOJ-1018 문제

체스판 다시 칠하기
BOJ-1018 문제

부분수열의 합
BOJ-1182 문제
BOJ-1182 풀이

치킨 배달
BOJ-15686 문제

연구소 3
BOJ-17142 문제

불 끄기
BOJ-14939 문제