[Algorithm] 2. Brute Force
2024-06-25
완전탐색 알고리즘(Brute Force Algorithm)
완전탐색은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.
모든 경우의 수를 고려하지 않고 더 이상 탐색이 필요 없는 경우 그 루트를 끊어버리는 것은 미완전 탐색이다.
예를 들어서 재귀함수가 모든 경우의 수를 탐색하다 결과를 찾아서 탐색을 중지하는 경우처럼 루트를 끊는 경우를 가지치기(Pruning)라고 한다. 이를 수행하면 불필요한 탐색을 줄일 수 있다.
상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게 된다.
경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용하다.
하나도 빠짐없이 모든 경우의 수를 확인하고 있는지만 확인하면 된다.
단순 Brute Force
단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법.
이 방법만을 사용하는 문제는 거의 나오지 않는다.
배열 탐색이나 문자열 비교가 해당될 수 있다.
# 배열 탐색
def find_index ( arr , target ):
for i in range ( len ( arr )):
if arr [ i ] == target :
return i
return - 1
# 문자열 비교
def str_compare ( s1 , s2 ):
length_s1 = len ( s1 )
length_s2 = len ( s2 )
small_length = min ( length_s1 , length_s2 )
for i in range ( small_length ):
if s1 [ i ] != s2 [ i ]:
return ord ( s1 [ i ]) - ord ( s2 [ i ])
if ( length_s1 == length_s2 ):
return 0
elif length_s1 > length_s2 :
return s1 [ small_length ]
else :
return s2 [ small_length ]
비트마스크 (Bitmask)
나올 수 있는 모든 경우의 수 각각에서 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용될 수 있다.
즉 이진수를 활용한 비트 연산을 통해 경우의 수를 줄여가며 탐색하는 방식이다.
예를 들어 ‘원소가 n 개인 집합의 모든 부분 집합’을 구한다면, 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장해둘 수 있다.
이와 같은 특성을 이용하여 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크 라고 한다.
비트 연산을 사용하기 때문에 계산이 빨라서 경우의 수가 많은 경우 유용하다.
10개의 방문을 체크해야 한다면 보통 check = [False] * 10와 같이 리스트를 많이 사용한다. 비트 마스킹은 check = 0b0000000000 와 같이 표현해서 하위 주소인 오른쪽부터 0인지 1인지 확인하면 된다.
비트 연산자
AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환
OR(|) : 대응하는 두 비트가 하나라도 1일 때, 1 반환
XOR(^) : 대응하는 두 비트가 서로 다르면, 1 반환
NOT(~) : 비트의 값을 반전하여 반환
Shift
<< : 왼쪽으로 비트를 옮긴다. A << B 는 A * 2^B 와 같다.
>> : 오른쪽으로 비트를 옮긴다. A >> B 는 A / 2^B 와 같다.
1010 & 1111 = 1010
1010 | 1111 = 1111
1010 ^ 1111 = 0101
~ 1010 = 0101
1010 << 2 = 101000
1010 >> 2 = 10
비트 마스크와 집합
비트 마스크는 비트의 특징을 살려 집합 개념의 문제에서 활용 가능하다. 즉 비트열을 리스트처럼 활용하는 것이다. 이 때 인덱스는 오른쪽부터 시작하고, 맨 오른쪽 인덱스는 0이다.
이 비트를 10진수로 바꾸어서 생각하는 것이 아니라, 각 자리의 비트가 1이라면 해당 자리수의 숫자가 집합에 속하는 것이다.
예를 들어 집합 S가 0b1000 일 때 집합 S 의 원소는 3 뿐이다. 마찬가지로 0b1001 라면 원소는 0과 3이다.
원소 추가
집합(S)에 특정 숫자(n)를 추가한다면, S 의 n번 비트만 1로 만들어주면 된다.
S = 0
# S |= (1 << n)
S |= ( 1 << 0 )
S |= ( 1 << 3 )
print ( bin ( S )) # 출력: 0b1001
여기서 1 << n 은 비트열의 n 번째를 1로 만들어주는 거라고 생각하면 쉽다. 이를 기존 집합과 OR 연산을 통해 n 번 비트를 추가한다.
원소 삭제
S 에서 n 을 삭제한다면 S 의 n 번 비트를 0으로 만들어주면 된다.
S = 0
S |= ( 1 << 0 )
S |= ( 1 << 3 )
S &= ~ ( 1 << 3 )
print ( bin ( S )) # 출력: 0b1
여기서 ~(1 << n) 은 n 번 비트만 0으로 만들고 나머지는 1로 만들어주는 것이다. 이를 기존 집합과 AND 연산을 통해 n 번 비트를 삭제한다.
원소 토글
S 에 n 이 있다면 삭제, 없다면 추가하는 연산이다. XOR 연산은 두 비트가 서로 다를 때 1을 반환하므로 토글 개념을 구현할 수 있다.
원소 체크
S 에 n 이 있으면 1, 없으면 0을 출력하는 연산이다. AND 연산의 두 비트가 모두 1이어야 1을 반환하는 성질을 이용한다.
print ( 1 if S & ( 1 << n ) else 0 )
원소 비우기 및 채우기
원소를 비우기 위해선 S 의 모든 비트를 0으로 만들어준다. 그리고 채우기 위해서는 S 의 모든 비트를 1로 만들어준다.
S 의 길이보다 1큰 만큼 비트열을 만들어주고, 1을 빼주면 비트열의 길이를 한자릿수 줄이면서 모두 1로 만들어준다.
S = 0 # 비우기
S = ( 1 << ( len ( S ) + 1 )) - 1 # 채우기
집합 끼리의 연산
A | B # 합집합
A & B # 교집합
A & ~ B # 차집합
A ^ B # A 와 B 중 하나에만 포함된 원소들의 집합
집합의 크기
비트에서 1인 비트 수를 세주면 된다.
x % 2 는 마지막 비트(맨 오른쪽)를 의미하고, x // 2 는 마지막 비트(맨 오른쪽)의 삭제를 의미한다.
def bit_count ( x ):
if x == 0 :
return 0
return x % 2 + bit_count ( x // 2 )
모든 부분집합 순회하기
def generate_subsets ( elements ):
n = len ( elements )
subsets = []
# 총 2^n개의 부분집합을 생성. -> 비트열은 i+1 개가 생긴다.
for i in range ( 1 << n ):
subset = []
for j in range ( n ):
# i의 j번째 비트가 1인지 확인
if i & ( 1 << j ):
subset . append ( elements [ j ])
subsets . append ( subset )
return subsets
# 예시 테스트
elements = [ 'a' , 'b' , 'c' ]
all_subsets = generate_subsets ( elements )
for subset in all_subsets :
print ( subset )
# Output:
# []
# ['a']
# ['b']
# ['a', 'b']
# ['c']
# ['a', 'c']
# ['b', 'c']
# ['a', 'b', 'c']
0xFFFFFFFF는 16진수 표기법으로, 32비트 정수에서 모든 비트가 1인 값을 나타낸다.
0x는 숫자가 16진수로 표기된다는 것을 의미한다.F는 16진수에서 10진수 15를 나타낸다.FFFFFFFF는 16진수 F가 8개 있는 형태로, 32비트를 나타낸다. 즉 각각의 F는 4비트를 나타내므로, F 8개는 총 32비트를 나타내는 것이다.16진수 F는 이진수로 1111 이다.
FFFFFFFF는 16진수 F가 8개 있으므로, 이진수로 변환하면 1111 1111 1111 1111 1111 1111 1111 1111가 된다. 즉, 32비트 모두가 1인 값을 나타내며, 이는 10진수로 4294967295 다.
0xFFFFFFFF는 비트 연산에서 자주 사용된다. 모든 비트를 1로 설정하여 특정 비트를 마스킹하는 데 사용된다.
재귀함수
재귀함수는 자기 자신을 다시 호출하는 함수를 말한다.
DFS 를 구현할 때 자주 사용되는 방법 중 하나이다.
파이썬에서는 기본적으로 최대 재귀 깊이가 있기 때문에 별다른 설정을 하지 않고 함수를 재귀적으로 호출하면 오류가 발생한다.
실제로 컴퓨터 시스템 상에서 함수가 재귀적으로 호출이 되면 컴퓨터 시스템의 스택 프레임에 함수가 반복적으로 쌓여서, 가장 마지막에 호출된 함수가 처리가 된 이후에 그 함수를 불렀던 함수를 처리하는 방식이다. 즉 일종의 스택 자료 구조 안에 함수에 대한 정보가 차례대로 담겨서 컴퓨터 메모리에 올라가게 된다고 이해할 수 있다.
재귀 함수를 호출하면 마치 스택에 데이터를 넣었다가 꺼내는 것과 마찬가지로 각각의 함수가 스택 프레임에 담겨서 차례대로 호출되었다가 가장 마지막에 호출된 함수부터 차례대로 종료가 되어 맨 처음 호출했던 함수까지 종료된다.
재귀함수를 쓰면 while 이나 for 문을 사용하지 않고도 반복적 작업을 수행할 수 있다.
일반적인 경우, 재귀 함수를 문제풀이에서 사용할 때에는 재귀 함수의 종료 조건을 반드시 명시해야 한다. 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있기 때문이다. 따라서 언젠가는 프로그램이 정해진 값을 반환할 수 있도록 만들어줘야 한다. 따라서 재귀 함수의 시작 부분에 종료 조건을 명시해서 종료 조건을 만족한다면 함수가 종료되도록 만들어준다.
재귀 함수의 예시로 유클리드 호제법이 있다. 유클리드 호제법은 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘이다.
유클리드 호제법은 두 자연수 A, B 에 대하여(A > B) A 를 B 로 나눈 나머지를 R 이라고 할 때, A 와 B 의 최대공약수는 B 와 R 의 최대공약수와 같다는 것이다.
아래와 같이 구현할 수 있다.
def gcd ( a , b ):
if a % b == 0 :
return b
else :
return gcd ( b , a % b )
print ( gcd ( 192 , 162 ))
이처럼 재귀 함수는 수학적으로 정의된 점화식 같은 형태를 간단히 코드로 옮길 수 있게 해준다. 단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.
또한 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다. 반대도 가능하다. 다만, 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. 그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다. 대표적으로 DFS 를 간결하게 작성하기 위해서 재귀 함수로 DFS 를 활용하기도 한다.
비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 유용하게 사용할 수 있다. 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 방식이다.
피보나치 수열 또한 재귀함수의 형태로 풀릴 수 있다.
def fibo ( x ):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2 :
return 1
return fibo ( x - 1 ) + fibo ( x - 2 )
백트래킹(Back Tracking)
해결책으로 가는 도중에 막히게 되면 상위 지점으로 다시 돌아가서 다른 경로를 탐색하는 방식이다. 이를 통해 모든 가능한 경우의 수를 탐색하여 해결책을 찾는다.
백트래킹은 완전탐색과 유사하지만, 불필요한 탐색을 줄이기 위해 가능성이 없는 노드를 더 이상 탐색하지 않는다(가지치기, pruning). 이러한 방법으로 백트래킹은 대규모 문제를 효과적으로 해결할 수 있다.
백트래킹은 다음과 같은 형태를 띈다.
def 백트래킹 ( n ):
if 정답이면 :
출력 or 저장
else :
for 모든 자식 노드에 대해서 :
if 유망조건 ( m ):
자식노드로 이동
백트래킹 ( n + 1 )
부모노드로 이동
def 유망조건 ( m ):
if 조건에 안맞으면 :
return False
return True
해당 알고리즘을 사용할 때 주로 재귀함수를 사용하여 구현하며 스택으로 구현하는 경우도 있다.
재귀함수를 이용하는 경우, 해결책을 찾기 위해서 생성, 검사, 선택, 이동, 되돌아가기 등 과정이 재귀적으로 수행된다.
N Queens 문제가 대표적이다.
순열, 조합
순열(permutation)은 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)을 말한다.
파이썬의 경우 itertools 의 permutations 로 쉽게 구현 가능하다.
조합(combination)은 서로 다른 N개를 조합의 수 만큼 뽑는 경우의 수를 말한다.
파이썬의 경우 itertools 의 combinations 로 쉽게 구현 가능하다.
이 외에 중복 순열(product), 중복 조합(combinations_with_replacement) 도 있다.
시간복잡도 측면에서 총 경우의 수가 1억번이 넘어가지 않는 한도에서 쓰는 것이 좋다.
너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)
그래프를 이용한 비선형 탐색이다.
너비우선탐색(Breadth-First Search, BFS) 는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식이다.깊이우선탐색(Depth-First Search, DFS) 는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식이다.길 찾기 등에 주로 쓰이는 알고리즘이다. 단순 길찾기에는 BFS/DFS만 써도 무방하지만, 장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색을 병용하기도 한다.
지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고 A와 B 사이에 존재하는 경로 찾을 때,
DFS : 모든 친구 관계 다 살펴야한다.
BFS : A와 가까운 관계부터 탐색한다.
너비 우선 탐색(BFS, Breadth-First Search)
재귀적으로 동작하지 않는다.
그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사(검사하지 않으면 무한루프)해야 한다.
BFS 는 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐(Queue) 자료구조(FIFO)를 사용한다.
넓게 탐색한다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다.
깊이 우선 탐색(DFS, Depth-First Search)
재귀적으로 동작한다. 따라서 재귀 함수나 스택(Stack)을 활용한다.
그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사(검사하지 않으면 무한루프)해야 한다.
모든 노드 방문하고자 할 때 사용한다.
BFS 보다 간단하지만, BFS 비해서 검색 속도가 느리다.
맨 위로 이동 ↑
댓글 남기기