[알고리즘] 구현 알고리즘 - 시뮬레이션 및 완전 탐색

구현이란?

 알고리즘을 공부하는데 구현은 뭐지? 그런 생각이 들었다. 구현이란 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정을 말한다고 한다. 알고리즘 문제를 푸는 입장에서 당연한 것이 아닌가 싶었지만, 풀이를 떠올리기 쉽지만 구현(소스 코드로 옮기기) 이 어려운 문제들을 구현 문제라 부른다고 한다. 다음과 같은 구현 문제에 대한 특징들이 있다.

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

 생각해낸 풀이 방법을 코드로 구현함에 있어서 실수 연산, 문자열 처리, 복잡한 로직 등의 장애물을 돌파하는 것이 관건인 유형이라 볼 수 있다. 문자열 처리 혹은 자료형 크기 등과 관련하여 프로그래밍 언어마다의 차이점이 분명 크게 존재한다. C나 Java를 제대로 배워본 적이 없어서 잘 모르겠지만 해당 언어들은 상대적으로 더 어렵다고 한다. 코딩 테스트용 언어로 파이썬을 많이 채택하는 이유도 간편한 내장 라이브러리들을 꼽을 수 있다. 그러나 어떤 언어를 사용하더라도 충분한 연습 혹은 해당 언어에 대한 이해도가 있다면 큰 문제는 없어 보인다. 나도 코딩 테스트를 준비하는 입장으로 언어를 하나 골라야 하는데 파이썬과 자바스크립트 중에 하나를 고르기가 어렵다. 익숙한 것은 파이썬이지만 요즘 자바스크립트를 중점적으로 공부 중이라 헷갈린다. 둘 다 할까? 🥲

 어쨌든 구현은 구현하기 어려운 문제라고 이해했다. 문자열 처리나 실수 연산 등의 프로그래밍 언어적 익숙함만으로 구현 문제를 해결할 수 있다면 당연히 구현이라는 알고리즘 카테고리를 나눌리 없다. 그래서 구현이 어려운 문제는 시뮬레이션이나 완전 탐색과 같은 형태로 출제되는 것으로 보인다. 다른 블로그 글에서는 구현 및 시뮬레이션과 완전 탐색으로 분류하기도 하던데, 이코테에서는 구현 속에 시뮬레이션과 완전 탐색이 들어가 있다.

시뮬레이션

 이제 세부적으로 들어가보자. 시뮬레이션부터 살펴보면 일련의 명령에 따라 개체를 차례대로 이동시키는 것을 의미한다. 일반적으로 2차원 공간과 방향벡터를 다루는 문제들이 출제된다. 알고리즘 문제에서 말하는 2차원 공간은 행렬(Matrix)로 보면 된다. '고등학교 수학 시간에 배운 것을 활용하면 되겠다'라고 생각하기엔 주의할 점이 있다.

 수학 시간에 배운 행렬이라면 (0, 0)의 위치는 1행 1열로 표현한다. 하지만 코딩 테스트를 볼 때에는 (0, 0)과 같이 생각해야 편하다. 왜냐하면 프로그래밍 언어에서 배열의 첫 번째 원소의 인덱스가 0이기 때문이다. 물론 (1, 1)로 생각해도 무방하다. 이것 또한 익숙해지면 큰 문제는 아닐 것 같다. 이제 예시 문제를 보며 이해해보자.

완전 탐색

 완전 탐색은 모든 경우의 수를 확인해서 해답을 구하는 것을 말한다. 이 방법은 무식하다는 의미로 "Brute Force"라고도 부른다고 한다. 말 그대로 다 체크하기 때문에 확실한 방법이라고 볼 수 있다. 아주 쉬운 예시로 핸드폰 비밀번호 4자리를 찾기 위해서 0000부터 시작하여 9999까지 눌러보며 추론하는 것을 들 수 있다. 이러한 완전 탐색 사용을 고려할 때 생각해보아야 할 부분이 있다.

 바로 효율성에 대한 문제이다. 이전에 포스팅한 그리디 알고리즘 유형의 문제들도 완전 탐색으로 풀 수는 있을 것이다. 하지만 시간 복잡도면에서 큰 차이가 발생한다. 그래서 경우에 따라 실행 시간이 비례하므로 입력되는 값의 범위가 작을 때 유용하게 사용할 수 있다. 완전 탐색은 생각보다 큰 범주였는데 세부적으로 분류하면 다음과 같은 알고리즘들도 포함된다.

1. 단순 Brute-Force
2. 비트마스크 (Bitmask)
3. 재귀함수
4. 순열
5. BFS / DFS

 - 자세한 사항은 더보기 클릭 -

단순 Brute-Force

 단순히 반복문과 조건문으로 모든 경우를 확인하며 답을 구하는 방법으로 이러한 문제는 잘 나오지 않는다고 한다.

비트마스크 (Bitmask)

컴퓨터가 내부적으로 모든 자료를 2진수로 표현하는 특성을 이용하여 정수의 2진수를 표현을 자료구조로 쓰는 기법을 말한다. 이를 이용하면 수행 시간, 코드 길이, 메모리 등의 방면에서 이점이 있다. 예를 들어 [1, 3, 5, 7, 9]를 원소로 가지는 집합을 2진수로 표현하자면 101010101(2)과 같이 나타낼 수 있다. 이처럼 나올 수 있는 모든 경우의 수가 두 종류로 분류될 때 유용하게 사용된다.

재귀호출 (Recursive Call)

 재귀함수, 재귀용법, 재귀트리 등 다양한 이름이 있는 것 같다. 함수 안에서 동일한 함수를 호출하는 형태를 말하며 대표적인 예시로 팩토리얼이 있다. 10! = 10 * 9! 임을 유념하고 다음 팩토리얼을 리턴하는 함수를 보면 쉽게 이해할 수 있다.

def get_factorial(num):
	if num <= 1:
    	return 1
    return num * get_factorial(num-1)

재귀 탈출 조건, 현재 함수의 상태를 저장하는 parameter 여부, return문을 잘 신경 써주어야 한다.

순열 (permutation)

 서로 다른 n개 중 r개를 골라 순서를 고려하여 나열한 경우의 수를 말한다. 순서를 고려한 경우의 수는 nPr = n(n-1)(n-2)...(n-r+1) 과 같이 계산된다. n = r이라면 경우의 수는 n!이며 O(N!)으로 높은 시간복잡도를 가진다. 따라서 문제에 따라 주어지는 n의 크기를 잘 고려하여 결정해야한다.

BFS 및 DFS

 너비 우선 탐색(Breath-First Search)과 깊이 우선 탐색(Depth-First Search)도 자주 나오는 알고리즘이다. 코딩 테스트에 자주 출제되는 문제 유형들 중 하나이다. 추후 자세히 다룰 예정이며 우선 둘의 차이점을 잘 나타낸 이미지를 첨부한다.

DFS와 BFS

예시 문제

 다양한 예시 문제들이 많이 있는데 그 중 왕실의 나이트 문제가 재미있어보여서 선택하겠다. 문제는 다음과 같다.

Q.왕실 정원은 8 x 8 좌표 평면이고 어떤 한 칸에 있는 나이트가 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력

- 나이트는 두 가지 방식으로 이동 : 수평으로 두 칸 이동 후 수직으로 한 칸 이동 혹은 수직으로 두 칸 이동 후 수평으로 한 칸 이동
- 정원 위치 : 행 1~8, 열 a~h로 표현

풀이 추론

 좌표가 알파벳으로 주어졌으므로 아스키 코드를 활용하여 알파벳 순서를 지정하여 (1, 1)을 시작으로하는 2차원 행렬로 문제에 접근한다. 지정 범위를 벗어나는 것은 제외하면 나이트가 이동 가능한 8가지의 경우가 존재한다. 즉 8가지 방향 벡터를 설정하여 주어지는 지점으로부터의 이동 가능한 위치를 특정할 수 있다. 간단히 정리하자면 다음과 같다.

1. 현재 나이트 위치를 숫자로된 좌표값으로 변환하기
2. 이동할 좌표까지의 8종류 벡터 설정하기
3. 이동 가능한 좌표 구하기

문제 풀이 

input_data = input()
row = int(input_data[1])
col = ord(input_data[0]) - ord('a') + 1

directions = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)]

count = 0
for dir in directions:
	new_row = row + dir[1]
	new_col = col + dir[0]
	if 1 <= new_row <= 8 and 1 <= new_col <= 8:
		count += 1

print(count)

결론

 구현 알고리즘의 개념은 간단해서 쉬울 줄 알았다. 그런데 생각보다 넓은 범위의 개념이라서 세세한 항목까지 한번에 다루기엔 핵심에서 벗어나는 느낌이다. 그래서 세부적인 것은 간단히 다루었다. BFS와 DFS의 경우 바로 다음으로 다룰 예정의 알고리즘이기도 하니, 앞으로 차차 알아가보면 될 것 같다.

 구현, 시뮬레이션, 완전 탐색 알고리즘은 개념을 이해하는 것은 쉬웠다. 하지만 이와 관련된 문제들을 직접 겪는다면 까다로운 문제들로 보인다. 아무래도 관련 문제들을 많이 풀어보면서 익숙해져야 제대로 공부했다고 말할 수 있다고 본다. 두루뭉실한 개념이라도 일단 맛본 것에 의미를 두겠다.

참조

https://www.youtube.com/watch?v=2zjoKjt97vQ

https://doing7.tistory.com/70