1. 그래프 최소 비용 문제 : 최소 신장 트리 문제 vs 최단 경로 문제 최소 신장 트리 문제 가중치 그래프에서 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제 최단 경로 문제 시작 정점에서 목표 정점까지 가는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제 2. 신장 트리(Spanning Tree) 정점인 n개인 undirected graph에서 n개의 정점과 n-1개의 간선으로 구성된 트리 즉, 모든 vertex set을 포함해야한다. 신장 트리의 수는 정점의 개수와 간선의 수의 비례한다. 3. 최소 신장 트리(Minimum Spanning Tree) 가중치 그래프의 신장 트리 중 간선들의 가중치의 합이 최소인 신장 트리 프림 알고리즘과 크루스칼 알고리즘이 존재한다.

1. 서로소 또는 상호배타 집합(Disjoint set) 교집합이 없는 집합 집합에 속한 특정 원소로 각 집합을 구분 대표자(representative) 상호배타 집합 표현 연결 리스트, 트리 2. 상호배타 집합 연산 Make-Set(x) : 원소 x만 속한 집합을 생성 Find-Set9x) : 원소 x가 속한 집합을 알아내는 연산, 해당 집합의 대표자를 반환 Union(x, y) : 원소 x가 속한 집합과 원소 y가 속한 집합을 합치는 연산, 대표자는 본인이 설정 3. 연결 리스트 표현 같은 집합의 원소들을 하나의 연결 리스트로 관리 연결리스트의 첫번째 원소가 집합의 대표원소 각 원소는 대표원소를 가리키는 링크를 갖는다. 4. 트리 표현 집합(disjoint set)을 하나의 트리로 표현 자식 노드가 ..

1. 그래프 탐색 그래프의 모든 정점을 빠짐없이 탐색 2. 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 시작 정점에서 한 방향을 선택해서 다음 정점으로 이동 선택된 정점에서 (1)을 반복 수행하면서 계속 깊이 탐색 이미 방문한 정점은 재방문 안한다. 더 이상 갈곳이 없으면 부모노드로 되돌아가 다시 깊이 탐색 스택을 사용한다 DFS 재귀 호출 # G : 그래프 # v : 시작 정점 # visited : 정점의 방문 여부, False로 초기화 # G[v] : 그래프 G에서 v의 인접리스트 def dfs(G, v): visited[v] = True # v를 방문 표시 visi..

1. 친구관계 A와 B는 친구를 (A - B)로 표현 2. 그래프 객체들 사이의 연결 관계 표현 정점(vertex)집합과 정점을 연결하는 간선(edge)집합으로 구성 G = (V, E) |V| : 정점 수, |E| : 간선 수 |V| = n개의 정점은 최대 C(n, 2) = n*(n-1)/2 개의 간선이 가능 3. Directed Graph vs Undirected Graph Undirected Graph 서로 대칭적이지 않은 관계 기업간의 공급관계, 작업의 선후 관계 등을 표현 4. 가중치 그래프(Weighted Graph) 간선에 비용이 추가된 그래프 5. 용어 인접(adjacency) : 두 정점 사이에 간선이 존재할 경우 인접하다고 한다. 완전 그래프 : 모든 정점이 인접한 그래프 부분 그래프 :..

1. 동전 거스름돈 총금액 800, 동전 종류 : 10, 50, 100, 400, 500 그리디 : 500, 100, 100, 100 -> 최적해가 아니다 소스코드 # coin[] : 동전의 금액을 젖아 # choice[] : 선택한 동전 집합 # best : 거스름돈에 대한 최소 동전 개수 def coinChange(choice, N, money): global best if best N best = N else: for i in range(len(coin): if money - coin[i] >= 0: choice[N] = coin[i] coinChange(choice, N+1, money-coin[i])

1. 순열 예시) 원소 개수 n = 4 -> 집합 = {A, B, C, D}, 4!인 24가지의 경우가 존재 따라서 상태 공간 트리에서의 단말노드의 수는 24개이다. 24개의 후보해가 존재한다는 것이고 이것은 단말노드의 수와 같다. 노드 방문 시마다 원소를 가리키는 인덱스 값을 저장 같은 원소 수를 갖는 부분집합과 순열의 상태 공간 트리의 높이는 같다. 순열의 경우 높이가 다른 노드는 선택지 수가 동일하지 않다. 선택할 때마다 다음 선택의 선택지 수가 하나씩 줄어든다. 소스코드 # order[] : 순열의 순서를 저장하는 리스트 def permutation(order, k, n): if k == n: # 다 선택하면 print_order_array(order, n): # 출력 else: check = [..

1. Power set 집합의 모든 부분집합 (공집합, 자기자신 포함) 집합의 원소개수가 n => 부분집합의 개수는 2^n 1 또는 0 값을 가지는 비트열 리스트로 부분집합 표현 소스코드 # a[0, ... , n-1] : 집합에 대한 비트표현 저장, 크기는 원소의 수 # k : 선택한 횟수(현재 노드의 높이) # n : 모든 선택 수(트리의 높이) def subset(a, k, n): if k == n: # 모든 선택이 끝난 상태 (단말노드 도착) process_solution(a, n) # else: a[k] = 0 # k번째 원소 포함 안하는 경우 subset(a, k+1, n) a[k] = 1 # k원소 포함하는 경우 subset(a, k+1, n) 백트래킹 구현은 상태공간트리와 동일한 함수호출트..

1. n-Queens 문제 n x n 체스판에서 n개의 퀸들을 서로 위협하지 않도록 배치하는 문제 2. 백트래킹 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는 기법 최적화(optimize)문제와 결정(decision)문제를 해결할 수 있다. 최적화 문제 미로 찾기, Subset sum 등 결정 문제 n-Queen, Map coloring 등 루트까지 되돌아갔는데 더이상 선택지가 없다면 답이 없는 것이다. 백트래킹의 핵심은 상태 공간 트리를 탐색하는 것! 해를 찾기 위한 선택의 과정을 트리로 표현 트리의 내부 노드는 해로 가는 중간 상태 트리의 단말 노드는 하나의 후보해에 대한 최종 상태 상태 공간 트리를 깊이 우선 탐색(DFS)하는 방법이 백..

i != 1, V = {v1, v2, v3, v4}, A는 v1을 포함하지않는 V의 부분집합, {v2, v3, v4} = 111 1. vi 가 A에 포함되는가? A & (1 011 v2가 A에 포함되는가? v2 -> i = 2 1

2주차 스터디 계획 https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 주에 공부할 내용은 백트래킹과 그래프입니다! 1. 백트래킹 1) 학습 목표 1. 백트래킹 개념을 학습하고 최적화 문제와 결정 문제에 적용할 수 있음을 이해한다. 2. 백트래킹으로 상태 공간 트리를 탐색하는 방법에 대해 이해한다. 3. 모든 부분 집합과 모든 순열을 백트래킹으로 생성할 수 있다. 2) 학습 구성 (5강 + 2문제) 1강 : 백트래킹 개념 2강 : 부분 집합 3강 : 순열 ..