[Algorithm] 3. 구현

[Algorithm] 3. 구현

 

 

1. 개념과 접근

 

1) 개념

 

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

problem - thinking - soultion

문제가 있고, 그것을 생각해서 해결점을 제시하는 것, 모든 문제가 구현 유형의 문제라고 할 수 있다. 모든 문제가 구현의 과정을 거쳐야 한다.

 

피지컬이 좋다 => 구현을 잘한다. (기초 체력과 같다.)

다만 협의적으로 볼 때, 구현이 어려운 문제를 ‘구현’ 유형의 문제라고 한다.

 

 

2) 접근 방법

 

풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제가 이에 해당한다.

 

ex.
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
적절한 라이브러리를 찾아서 사용해야 하는 문제

 

 

 

완전 탐색, 시뮬레이션은 ‘구현’ 유형이라고 할 수 있다.

 

완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법(브루트포스 알고리즘)

시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행하는 것.

 

참고로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용된다. 시뮬레이션, 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다. 이점을 잘 생각하고 접근하면 도움이 된다.

 

ex. 

# 현재 위치
x, y = 2, 2

# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

for i in range(4) :
# (다음 위치)
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)

 

 

2. 주요 고려 사항

 

메모리 제약을 신경써야 한다.

 

1) 변수의 표현 범위

 

C/C++ 언어는 자료형의 범위에 대해 많이 고려해야 한다.

int의 경우 자료형의 크기가 4바이트이며, -2,147,483,648~2,147,483,647의 수만 표현할 수 있다.

이보다 큰 수를 처리하기 위해서는 long long 변수를 사용해야 한다.

 

파이썬은 직접 자료형 지정이 필요없다. 매우 큰 수의 연산도 기본으로 지원한다.

 

다만, 파이썬에서 실수형 변수는 유효숫자에 따라 연산 결과가 원하지 않는 값이 나올 수도 있다.

ex. 0.3+0.6 = 0.89999999

 

이를 해결하기 위해서는 round 함수를 사용하면 된다.

 

 

2) 파이썬 리스트 크기

 

코딩 테스트의 메모리 제한과 연관이 있다. 128mb ~ 512mb로 메모리가 제한되는데, 수백만 개 이상 데이터를 처리해야 하는 문제를 만났을 때, 메모리 제한이 걸릴 수 있다.

 

데이터의 개수

1000 - 약 4kb

1,000,000 - 약 4mb

10,000,000 - 약 40mb

 

만약 저 개수만큼 크기를 가지는 리스트를 여러번 사용한다면, 사용하는 메모리의 양이 비례해서 많아질 것이다.

 

최적화와 관련 있는 만큼 알아두면 좋을 상식이지만, 일반적인 코딩 테스트에서는 저 용량 아래의 데이터만을 사용하면 된다는 생각만 가지고 임하면 된다.

 

 

3) 시간 제약 사항

 

파이썬은 1초에 2,000만번의 연산을 수행한다고 할 수 있다.

만약 크기가 1,000만인 1차원 리스트를 append()만 하는 반복문을 포함한 코드를 실행한다면, 

시간복잡도는 O(N)이 되기 때문에, 1초 안에 수행이 가능하지만, 리스트가 3,000만인 경우 append()수행이 불가능하다.

 

 

 

3. 대표적인 문제

 

https://www.acmicpc.net/problem/1259

1259번: 팰린드롬수

 

https://www.acmicpc.net/problem/2675

2675번: 문자열 반복