[파이썬 코테 대비 동아리]_개념을 공부하자”완전탐색”편

완전 탐색 알고리즘?

: 가능한 경우의 수를 모두 조사해서 정답을 찾는 방법. Brute Force라고도 부른 다. 직관적이고 이해하기 쉬운 기초적인 방법이다.

4자리의 비밀번호를 찾겠다 하면 모두풀려고 시도하는 거!

완전 탐색 알고리즘의 동작 과정은 다음과 같다.

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
2. 가능한 모든 방법을 모두 동원
3. 실제값을 구함

간단하다!

완전 탐색의 종류는 다음과 같다.

1. Brute Force
2. 백트래킹( Backtracking )
3. 순열 ( Permutation )
4. 비트 마스크 ( Bit Mask )
5. 재귀 함수
6. DFS /BFS

먼저 Brute Force 기법은 이름에서 알 수 있듯이 조건문을 통해 가능한 모든 경우의 수를 시도하는 방법이다. 위에서 설명한 방법과 같다. 이 방법을 사용하는 문제는 거의 나오지 않으므로 코드도 보지 않을 것이다!!

Backtracking 방법은 가능한 후보군을 가지로 치며 탐색한다. 분할 정복을 이용한 기법으로 해를 찾다가 도저히 답이 아닐 것 같으면 되돌아가서 다른 가지로 간다.

순열은 임의의 수열이 주어졌을 때 그것을 다른 순서로 연산한다. 타 블로그에서 정리한 순열 알고리즘을 가져와봤다.

※ 순열을 구현하는 방법

현재 순열을 구성하는 배열을 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}

내가 안 하고 가져 온 이유가 시간복잡도가 O(N!) 이 되기 때문에…. 이딴 시간복잡도로는 N이 크면 사용할 수 없기때문에! 그냥 한번 보기만 하자…~ 잘 쓰이긴 하나? 싶다. 찾아보니 N이 한자리 수 일 때만 쓴단다. 파이썬에서는 순열 관련 라이브러리가 있기 때문에 그거 쓰면 됨다.

비트 마스크는 2진수로 연산되는 컴퓨터 연산을 이용한다. 비트마스크 문제는 각각의 원소가 포함되거나 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용된다. 예를 들어 원소 5개인 부분집합을 구할 때 각 원소가 포함되거나 포함되지 않는 경우만 존재하므로 적합하다.

and연산 → 둘다 1이면 출력1

Or 연산 → 둘 중 하나라도 1이면 1

Not 연산 → 1이면 출력0 0이면 출력1

Xor연산 → 둘 관계가 다르면 출력1 같으면 출력0

Shift 연산 (<<,>>) → A<<B이면 A를 좌측으로 B비트만큼 미는 것.

O(1)에 구현되는 것이 많기 때문에 다른자료구조를 사용하는것 보다 훨씬 빨리 동작한다. 비트마스크 코드를 알아보자.

#공집합 = '0b0'
zero = bin(0)

#꽉 찬 집합 (20bit ) 
full = (1 << 20) - 1
print(bin(full))
>>>0b111111111111111111

#원소추가
#s에 num을 추가하면 num번 비트만 1을 만들어주면 된다.
S |= (1 << num)

#원소 삭제
#num만큼의 비트만 0으로 만들고 나머지를 1로 만들어준다
S &= ~(1 << num)

#원소 토글
# s에 num이 없다면 추가 있다면 삭제. xor연산의 개념
S ^= (1 << num)

#원소 체크
#s에 num이 있으면 1반환 없으면 0반롼.
print(1 if S & (1 << int(op[1])) != 0 else 0))

#원소 비우기 및 채우기 
#비우려면 모든 비트를 0 채우려면 1로 맘들더준다.
S = 0              #비우기
S = (1 << 21) - 1  #채우기

#집합끼리의 연산
A | B   # 합집합
A & B   # 교집합
A & ~B  # 차집합 (A - B)
A ^ B   # A와 B 중 하나에만 포함된 원소들의 집합

#집합 크기 구하기 == 재귀함수로 구현
def bitCount(x):
	if x == 0: return 0
	return x % 2 + bitCount(x//2)

물론 이 코드도 다른 블로그 참고했슴니다^!^

재귀는 이미 알아서 간단하게만 하자면 답이 아니면 나온 값을 다시 넣고 계속 돌리는 방식! 재귀를 사용하고 샆으면 탈출 조건과 함수 상태를 저장하는 parameter가 꼭 필요하다는 걸 잊지말자.

시간복잡도는 O(N)이 된다.

dfs bfs는 나중에 다시 다룰 것이다.

이제 알고리즘에서 주로 쓰는 조합형 완전 탐색 함수 4가지를 알아보자

1. product
2. permutation
3. combinations
4. combinations_with_replace,ent

보아하니 전부 itertools 를 import 해줘야함(반복 데이터 처리 함수)

얘네 모두 generator 이기 때문에 list()로 캐스팅 해줘야함 안 그러면 한 번 돌고 사라짐

product ( 곱집합 )

: 보통 데카르트의 곱이라고 한대요 ㅋㅋ

for문 두 개를 섞어놨다고 생각하면 된다.

product(p,q,…[repeat =1])

예제

itertools.product('1234', repeat = 2)
>>>[('1', '1'), ('1', '2'), ('1', '3'), ('1', '4'), 
 ('2', '1'), ('2', '2'), ('2', '3'), ('2', '4'), 
 ('3', '1'), ('3', '2'), ('3', '3'), ('3', '4'), 
 ('4', '1'), ('4', '2'), ('4', '3'), ('4', '4')]

permutations (순열)

: 반복 가능한 요소의 연속된 길이가 r인 순열을 반환한다. r이 지정되지 않았거나 none 이면 기본값으로 적용되며 가능한 모든 길이의 최대 길이 순열이 생성된다.

가능한 모든 순서를 반환하며 반복되는 요소가 없다는 게 특징이다.

permutations(p[,r])의 형태로 사용 가능하다.

예시

itertools.permutations('1234',2)
>>>[('1', '2'), ('1', '3'), ('1', '4'),
 ('2', '1'), ('2', '3'), ('2', '4'),
 ('3', '1'), ('3', '2'), ('3', '4'), 
 ('4', '1'), ('4', '2'), ('4', '3')]

combinations (조합)

: 반복되는 요소가 없는 정렬된 순서들을 반환한다.

combinations(p,r)의 형태로 사용한다.

예시

combinations('1234',2)
>>>[('1', '2'), ('1', '3'), ('1', '4'),
 ('2', '3'), ('2', '4'), 
 ('3', '4')]

combinations_with_replacement (중복 가능 조합)

: 조합에서 개별 요소마다 두 번 이상 반복할 수 있다

예시

combinations_with_replacement('1234',2)
>>>[('1', '1'), ('1', '2'), ('1', '3'), ('1', '4'),
 ('2', '2'), ('2', '3'), ('2', '4'), 
 ('3', '3'), ('3', '4'), 
 ('4', '4')]

문제를 풀어보자!

[카펫]

문제설명

Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.-> 세로 <= 가로

입출력 예

brown yellow return

10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

나중에….나중에….풀이생각해서 수정학겟다……..