SW 문제 해결 - 탐욕 알고리즘

About this offer

조합적 문제 부분집합 어떤 집합의 공집합과 자기 자신을 포함한 모든 부분 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 수 = 2^n개 집합에서 부분집합을 찾아내는 구현 방법 1. 완전 탐색 재귀호출을 이용한 완전탐색으로 부분집합을 구할 수 있음 실전 보다는 안전 탐색 학습용으로 추천하는 방법 2. Binary Counting 2진수와 비트연산을 이용해 부분집합을 구할 수 있음 모든 부분집합이 필요할 때 사용 하는 추천 방법 완전 탐색으로 부분집합 구하기 # 민철이에게는 세명의 친구가 있습니다. {MIN, CO, TIM} # 함께 영화관에 갈 수 있는 멤버를 구성하고자 합니다. # 모든 경우의 수를 출력해봅시다. 완전 탐색을 이용해 구현 O, X로 집합에 포함시킬지 말지 결정 코드 구현 Branch : 2개 Level : 3개 arr = ['O', 'X'] path = [] name = ['MIN', 'CO', 'TIM'] def run(lev): if lev == 3: print(path) return for i in range(2): path.append(arr[i]) run(lev + 1) path.pop() run(0) 실행 결과 ['O', 'O', 'O'] ['O', 'O', 'X'] ['O', 'X', 'O'] ['O', 'X', 'X'] ['X', 'O', 'O'] ['X', 'O', 'X'] ['X', 'X', 'O'] ['X', 'X', 'X'] #### 완성된 소스 코드 * 이름 출력 코드 추가 ```python arr = ['O', 'X'] path = [] name = ['MIN', 'CO', 'TIM'] def run(lev): if lev == 3: print_name() return for i in range(2): path.append(arr[i]) run(lev + 1) path.pop() run(0) # 이름 출력 함수 def print_name(): print('{', end=' ') for i in range(3): if path[i] == 'O': print(name[i], end=' ') print('}') # 출력 결과 { MIN CO TIM } { MIN CO } { MIN TIM } { MIN } { CO TIM } { CO } { TIM } { } 바이너리 카운팅 (Binary Counting) 원소 수에 해당하는 N개의 비트열을 이용해 부분집합을 표시 001 이면 부분집합 {A}를 나타냄 0번 비트가 1이므로 첫 원소인 A만 포함된 부분집합을 나타냄 110이면 부분집합 {B, C}를 나타냄 1번, 2번 비트가 1이므로, 두번째와 세 번째 원소인 B, C 가 포함된 부분집합을 나타냄 10진수 이진수 {A, B. C} 0 000 {} 1 001 {A} 2 010 {B} 3 011 {A, B} 4 100 {C} 5 101 {A, C} 6 110 {B, C} 7 111 {A, B, C} 부분닙합의 총 개수 만들 수 있는 집합의 총 개수는 2^n 이며, n=3 이기기에 총 8개의 부분집합 존재 2^n은 1<<n 공식을 이용해 빠르게 구할 수 있음 print(pow(2, 3)) print(1 << 3) # 출력 결과 8 8 부분집합 {B, C} 만드는 rhkwjd 6(0b110)에서 비트 연산을 이용해 마지막 한 자리가 1인지 0인지 검사 arr = ['A', 'B', 'C'] n = len(arr) def get_sub(tar): for i in range(n): if tar & 0x1: print(arr[i], end= '') tar >>= 1 # 검사한 한 자리를 제거 get_sub(6) #### 완성된 부분집합 코드 * get_sub(0) ~ get_sub(7) 까지 호출하여 모든 부분집합 출력 ```python arr = ['A', 'B', 'C'] n = len(arr) def get_sub(tar): for i in range(n): if tar & 0x1: print(arr[i], end=' ') tar >>= 1 # 검사한 한 자리를 제거 for tar in range(1 << n): # range(0, 8) print('{', end= ' ') get_sub(tar) print('}') # 출력 결과 {} { A } { B } { A B } { C } { A C } { B C } { A B C } 조합 (Combination) 서로 다른 n개의 원소 중 r 개를 순서 없이 골라낸 것 순열과 조합 차이 탐욕 알고리즘 Greedy (탐욕 알고리즘) 결정이 필요할 때, 현재 기준으로 가장 좋아 보이는 선택지로 결정해 답을 도출하는 알고리즘 대표적인 문제해결 기법 완전 탐색(Brute-Force) 답이 될 수 있는 모든 경우를 시도해보는 알고리즘 Greedy 결정이 필요할 때 가장 좋아보이는 선택지로 결정하는 알고리즘 DP 현재에서 가장 좋아보이는 것을 선택하는 것이 아닌, 과거의 데이터를 이용해 현재의 데이터를 만들어내는 문제해결 기법 분할 정복 큰 문제를 작은 문제로 나누어 해결하는 문제해결 기법 Knapsack 문제 활동 선택 문제

Offer details

Provider

velog

Source

velog-rss