그래프(36)
-
[그래프] Graph 3: Eulerian circuit 오일러 서킷, 오일러 트레일
1. 오일러 서킷 (Eulerian circuit) - 한붓 그리기 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제 이와 같은 경로를 그래프 이론에서 오일러 서킷이라고 부른다. 오일러 서킷이 어느 경우에 존재할 수 있는지를 판단하는 단서는 반대로 오일러 서킷이 존재할 수 없는 경우를 생각하는것이다. 가장 생각하기 쉬운 경우는 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우이다. (간선을 가지지 않은 컴포넌트는 예외) 정점의 차수(degree) 시작점이 u이고 끝점이 v인 특정 경로 u->v 가 모든 간선을 지나지 못하고 끝났다고 해보자. 이는 v에서 연결된 간선은 전부 한번 씩 지나갔다는 것을 의미한다. (갈곳이 없다) u != v: 항상 v는 홀수 개의 간..
2021.02.13 -
[그래프] DICTIONARY 고대어 사전
1. 문제 고대어 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있지만, 사전에 포함된 단어의 순서들이 영어와 서로 다르다. 사전선이 다른 순서인지 알파벳 순서가 영어와 서로 다른 것인지 알기 위해 사전에 포함된 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하여라 2. DFS, 위상정렬, DAG - 사이클이 없는 방향그래프일때 해당 순서를 계산할 수 있을 것이다. - DAG를 다루는 문제로 각 알파벳을 정점으로하고 다음문자와의 비교를 통해 알파벳끼리의 간선을 생성할 수 있을 것이다. 이 문제는 사이클만 찾는 코드를 구현하면 쉽게 풀 수 있다. 사이클이 생기는 경우는 한가지만 체크하면된다. 위상정렬을 구하기 위해 dfs를 실행하는 중 함수가 종료될..
2021.02.12 -
[그래프] Graph 2: DFS 그래프의 깊이 우선 탐색, 위상 정렬
1. 그래프 탐색 (search) 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색이라고 한다 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다. 2. 깊이 우선 탐색 (Depth-first search, DFS) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것 이다. 따라갈 간선이 없으면 마지막에 따라왔던 간선을 따라 뒤 돌아간다. 위 그림들은 정점의 번호가 작은것을 먼저 탐색하는 dfs의 예시이다. 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 ..
2021.02.11 -
[그래프] Graph 1: 그래프의 표현과 정의
알고리즘 문제해결전략2 그래프파트 1. 그래프 그래프는 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조이다. 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 트리와는 다르게 부모 자식 관계에 관한 제약이 없기 때문에 그래프는 트리보다 훨씬 다양한 구조를 표현할 수 있다. 2. 그래프의 정의 그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조이다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다. 3. 그래프의 종류 간선에 추가적인 속성을 부여 존재할 수 있는 간선이나 정점의 형태에 제약 가능 여러 속성을 함께 가지는 그..
2021.02.11 -
[결정 문제][그래프] ARCTIC 북극 기지
1. 최적화 문제 이 문제는 각 기지를 모두 연결할 수 있는 거리 중에서 최대 거리를 최소화 하는 문제로 모든 경우의 수를 만들어서 최대거리가 최소인 경우를 찾으면 된다. 하지만 이 최적화 문제는 경우의 수가 너무 많다. 2. 결정 문제 결정 문제로 문제를 변형해보자 모든 기지를 통신반경 D인 무전기로 연결할 수 있는지? 이 문제를 이진탐색으로 여러번 수행하면 최적해에 아주 가까운 근사값을 얻을 수 있을 것이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 ..
2021.01.21 -
[동적 계획법, 그래프] JUMPGAME 외발 뛰기
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #include #include #define UNTRAVELED -1 #define NO 0 #define YES 1 int cache[100][100]; int board[100][100]; int dy[2]{1,0}; int dx[2]{0,1}; bool inRange(int y, int x, int n) { return ((y n; memset(cache, -1, sizeof cache); for(int j{0}..
2021.01.06