Brute Force

Kaydenna92·2022년 6월 2일
0

Algorithm

목록 보기
5/36

개념

모든 경우의 수를 체크하여 정답을 찾는 방법
가장 확실하고 기초적인 방법
예를 들어 비밀번호가 4자리인 자물쇠를 풀려면 0000 ~ 9999 까지 시도하는 것
But, 효율적인가에 대해서는? -> 문제의 유형에 따라 사용 할 것

활용

brute force - 반복
순열
재귀
BFS, DFS

순열

  • 개념 : 순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법
  • 순서가 중요하다. ex) [1, 2, 3] != [1, 3, 2]
    -> 순서에 따라 의미가 있고, 이 순서를 통해 연결되는 이전, 다음의 수열을 찾을 수 있는 경우를 계산 할 수 있다.
  • 서로 다른 N개의 데이터가 있고, 이를 순열로 나타내면 전체 순열의 가지 수는 N!
    -> 최초에 N개 중 1개가 올 수 있고, 그 이후에는 N-1, N-2 .... 1 개가 올 수 있다.
    -> 이를 모두 곱하면 N!
[1, 2, 3]을 사전 순으로 나열하는 순열이 있다고 가정해보자.
순서
[1 2 3] - 최초 순열 - 오름차순
[1 3 2]
[2 1 3]
[2 3 1]
[3 1 2]
[3 2 1] - 최종 순열 - 내림차순
※ 순열을 구현하는 방법

현재 순열을 구성하는 배열을 A라고 하고 i,j는 그 배열의 index 값을 의미한다고 하자. 예를 들어 A={7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index 값이다.

아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.

1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)
  → 현재 i값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 다는 것이다. 현재 기준 최종 순열을 찾음
      A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.

2. j >= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.
  → 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
      A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.

3. A[i-1]과 A[j]를 Swap한다.
   → i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 6, 5, 3, 1}

4. i이후의 순열을 모두 뒤집는다.
   → 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
      A={7, 2, 4, 1, 3, 5, 6}

재귀

자기 자신을 호출하는 함수
스택이라는 자료구조를 사용
반복문의 역할을 수행
큰 작업 하나를 동일하면서 간단한 작업 여러개로 나눌 수 있을 때 유용
무한 루프에 빠질 수 있음. (종료 조건 필요)

def solution(level):
	if level == 5: 
    	print('finish')
    	return 
    
    solution(level+1)
# decimal to binary

def to_binary(number):
	if number == 0:
 		return
    
    to_binary(number // 2)
    print(number%2, end='')
    
N = int(input())
to_binary(N)

Point
DFS에서는 필요없는 부분은 CUT해서 시간을 줄이고, recursion error가 나지 않게 하는 것이 매우 중요.

  • 깊이 우선탐색
    밑으로 계속 내려가다가 더이상 내려갈 곳이 없으면, return해서 다른 길을 탐색

이진트리 순회(DFS)

# 전위 순회 (부모 -> 왼쪽 -> 오른쪽) 1 2 4 5 3 6 7
def DFS(x):
   if x <=  7:
       print(x, end='')
       DFS(x * 2) # 부모노드에 2를 곱하면 왼쪽 자식 노드로 호출한 것
       DFS(x * 2 + 1) # 부모노드에 2곱, 1 더하기 하면 오른쪽 자식노드 호출
   else:
       return
   
	DFS(1)
# 중위 순회(왼쪽 -> 부모 -> 오른쪽) 4 2 5 1 6 3 7 
def DFS(x):
    if x <=  7:
        DFS(x * 2) # 부모노드에 2를 곱하면 왼쪽 자식 노드로 호출한 것
        print(x, end='') # 왼쪽 자식을 먼저 출력한 후 부모 출력
        DFS(x * 2 + 1) # 부모노드에 2곱, 1 더하기 하면 오른쪽 자식노드 호출
    else:
        return
    
DFS(1)
# 후위 순회 (왼쪽 -> 오른쪽 -> 부모)
def DFS(x):
    if x <=  7:
        DFS(x * 2) # 부모노드에 2를 곱하면 왼쪽 자식 노드로 호출한 것
        DFS(x * 2 + 1) # 부모노드에 2곱, 1 더하기 하면 오른쪽 자식노드 호출
        print(x, end='') # 왼쪽, 오른쪽 자식 노드를 처리하고 난 후, print
    else:
        return
    
DFS(1)

부분집합 구하기(DFS)

원소를 포함시킬지 안 시킬지 결정하는 체크 리스트를 하나 생성하기.

def DFS(x):
	if x == n + 1:
    	for i in range(1, n+1):
        	if check[i] == 1:
            	print(i, end=' ')
        print()
        return
        
    else:
    	check[x] = 1
        DFS(x+1)
        check[x] = 0
        DFS(x+1)
        
n = int(input())
check = [0]*(n+1)
DFS(1)
# [입력] 
3
# [출력]
1 2 3
1 2
1 3
1
2 3
2
3

중복순열 구하기(DFS)

n개 중에서 m개를 순서에 상관있게 뽑는데, 중복을 허락하여 뽑는 방법

def DFS(level):
    global cnt
    
    if level == M:
        for i in range(M):
            print(result[i], end=' ')
        cnt += 1
        
        print()
        return
        
    else:
        for i in range(1, N+1):
            result[level] = i
            DFS(level + 1)

N, M = map(int, input().split())
result = [0]*N
cnt = 0 # 중복 순열의 개수 
DFS(0)
print(cnt)

순열 구하기(DFS)

# 서로 다른 숫자 N개 중 M개를 뽑아 중복없이 나열하는 코드

def DFS(level):
    global cnt, result
    if level == M:
        cnt += 1
        for i in range(1, M+1):
            print(result[i], end= ' ')
        print()
        return
    else:
        for i in range(1, N+1):
            if used[i] == 0:
                used[i] = 1
                result[level+1] = i
                DFS(level+1)
                used[i] = 0
                

N, M = map(int, input().split())
result = [0]*(M+1)
used = [0]*(N+1)
cnt = 0
DFS(0)
print(cnt)

조합

서로 다른 n개에서 순서와 상관없이 r개를 고르는 것을 조합이라고 한다.
순열과는 달리 조합에서는 순서가 중요하지 않다.

def DFS(level, index):
    if level == r:
        for i in range(r):
            print(result[i], end= ' ')
        print()
        return
    else:
        for i in range(index, n+1):
            result[level] = i
            DFS(level+1, i+1)

n, r = map(int, input().split()) # 서로 다른 n개, r개를 고른다
result = [0]*r
DFS(0,1)

itertools를 이용한 순열과 조합

import itertools

chars = ['A','B','C']

p = itertools.permutations(chars, 2) # 순열
c = itertools.combinations(chars, 2) # 조합

# p에는 itertools.permutations 객체가,
# c에는 itertools.combinations 객체가 반환된다.
# 두 번째 인자로 받는 숫자는 주어진 컨테이너 타입 변수에서 몇 개의 아이템을 봅을 지 결정하는 인자
# permutations는 두 번째 인자를 받지 않으면 default값으로 컨테이너의 전체 길이가 들어간다
# combinations는 두 번째 인자를 받지 않으면 error

print(list(p))
print(list(c))

# [출력]
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
[('A', 'B'), ('A', 'C'), ('B', 'C')]

profile
persistently

0개의 댓글