[파이썬 알고리즘] 구현 알고리즘 개요

구현 Implementation 이란

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

구현 문제는 보통 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 지칭한다.

구현 유형 예시

---

a. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제

• 언어에 따라 내장 함수가 다르기 때문에 난이도 차이가 있다.

b. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

c. 문자열을 특정한 기준에 따라서 끊어 리스트에 넣어야 하는 (파싱을 해야 하는) 문제

• 문자열을 이용한 문제는 파이썬에서 쉽게 처리할 수 있다.

d. 적절한 라이브러리를 찾아서 사용해야 하는 문제

• 모든 순열과 모든 조합을 찾는 문제라면 파이썬의 itertools라는 표준 라이브러리를 통해 간결하게 해결 가능하다.

공부한 교재에서는 시뮬레이션과 완전 탐색 문제를 다룰 것이라고 한다.

시뮬레이션 & 완전 탐색

• 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법

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

위 두 유형의 문제에서 자주 활용되는 것들을 알아보자.

2차원 공간

---

2차원 공간이 자주 활용된다.

왼쪽 위의 방(0, 0)이 보통 행렬의 첫번째 원소이다.

일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다.

행렬이란? 2차원 데이터를 표와 같은 형태로 쉽게 나타내줄 수 있게 하는 수학적 개념 중 하나이다.

방향 벡터

---

2차원 공간에서의 방향 벡터가 자주 활용된다.

만약 상하좌우(동북서남) 이동 시에 다음 위치를 확인 하고 싶을 때 아래와 같은 로직이 사용된다.

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

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

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

구현 시 고려할 점

코딩 테스트 환경에서는 시간 제한과 메모리 제한 정보가 주어진다.

이는 어떻게 고려해야 할까?

메모리 제약

---

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

아래는 파이썬의 정수 자료형 데이터의 개수에 따른 메모리 사용량이다.

최적화를 고려하기 보다는 더 적은 크기의 메모리를 사용하는데만 주의를 기울여도 된다.

시간 제한

---

파이썬의 경우 1초에 2,000만 번의 연산을 수행한다고 가정하여 풀면 된다.

Notice: 이 게시물은 한빛미디어의 이것이 코딩 테스트다 영상과 교재를 참고하였습니다.