해당 시리즈는 이것이 코딩 테스트다 라는 책의 내용을 기반으로 작성된 글이며 알고리즘의 기본 개념이 되는 방법론들의 기본 개념을 학습하고 포스팅 할 예정입니다. 모든 소스 코드는 여기서 확인하실 수 있습니다.
구현 알고리즘
정의
알고리즘 문제를 풀다 보면 이런 생각이 들 때가 있었을 것이다. 어떻게 풀어야 할지는 알겠는데 이걸 코드로 어떻게 옮기지..? 이러한 유형이 구현 알고리즘에 속한다. 즉 해당 유형에서는 풀이 과정은 생각해내기 상대적으로 쉬우나, 이를 코드로 구현함에 있어서 여러가지 장애물이 존재하는 알고리즘을 의미한다.
예를 들어 복잡한 문자열 처리나 큰 정수 처리가 포함된 문제는 C, Java 로 문제를 푸는 이들에게는 상대적으로 어려울 수 있다. 문자를 어떻게 처리 해야 할지는 생각했으나 이를 실제로 구현하는 과정에서 어려움이 존재하기 때문이다. 반대로 자신이 사용하는 언어에 충분히 익숙하고 자신의 생각을 코드로 작성할 수 있다면 쉬운 문제라고 볼 수 있다.
시뮬레이션과 같은 문제들이 구현 알고리즘에 속할 수 있다. 시뮬레이션이란 문제에서 제시하는 알고리즘을 단계별로 직접 수행해야 하는데 이 과정에서 어려움이 존재하기 때문이다. 아래의 예제를 보며 이해해보자.
예시
- 체스에는 나이트라는 캐릭터가 존재한다. 8 * 8 체스판 위에서 나이트는 L자의 형태로만 움직일 수 있으며 체스판 밖으로는 나갈 수 없다. 아래와 같은 체스판이 존재하고 X축은 순서대로
a b c d e f g h, Y축은 순서대로1 2 3 4 5 6 7 8이라고 가정하자. - 예를 들어
a1에 위치한 나이트는 오른쪽 두칸 + 아래로 한칸(C2), 아래로 두칸 + 오른쪽 한칸(B3) 으로 움직일 수 있다. (수평 혹은 수직으로 두칸 이동한 뒤 수직, 수평 방향으로 한칸 이동만 가능하다고 가정한다) - 현재 나이트의 위치가 주어지고 나이트가 갈 수 있는 모든 경우의 수는 몇가지인지 구하라. (그림 못 그려서 죄송합니다..)
해결
위 문제는 나이트가 이동할 수 있는 경로의 경우의 수를 모두 찾아서 판을 벗어나는 곳을 제외하면 된다. 하지만 이를 코드로 구현할 때 여러가지 어려움이 따를 수 있다.(물론 잘하시는 분들에겐 너무 쉬울 것이다) 아래의 코드를 보며 얘기해보자.
def solution():
location = input()
numbers = [1, 2, 3, 4, 5, 6, 7, 8]
chars = ['a', 'b', 'c', 'd', 'e', 'g', 'h']
x = numbers[chars.index(location[0])]
y = int(location[1])
answer = 0
dxy = [
(x - 2, y - 1), (x - 2, y + 1), (x - 1, y + 2), (x + 1, y + 2),
(x + 2, y + 1), (x + 2, y - 1), (x - 1, y - 2), (x + 1, y - 2)
]
for index in range(len(dxy)):
if (0 < dxy[index][0] < 9) and (0 < dxy[index][1] < 9):
answer += 1
return answer
print(solution())문제를 해결하는 과정에 있어서 아래의 두가지 방법을 생각하고 코드로 옮겨야 한다. 이는 익숙한 사람에겐 쉬울 수 있지만 초보자에겐 어려울 수 있다.
- X축(알파벳)을 숫자로 치환한다.
- 치환된 두 수를
dxy라는 변수에 위와 같은 형태로 담은 뒤 탐색을 시작한다.
흐름
개인적으로 구현 알고리즘을 해결할 때는 아래와 같은 방식으로 접근하면 좋을 것 같다. 즉 단계를 세분화하고 작은 단계를 해결하는 과정에서 발생하는 어려움을 학습하며 풀어 간다면, 실력이 늘지 않을까 라고 생각해 본다.(모든 알고리즘이 똑같을거 같기도 하네요..)
- 문제를 해결할 수 있는 방식을 생각한다.
- 이를 코드로 녹이는 과정을 세분화하여 작성한다.
- 세분화된 코드를 작성하는 과정에서 어려운 점을 구글링을 통해 학습한다.
- 문제를 해결한다.
