1. 문제 끝말잇기 참가자 = 원으로 앉아있음 시계방향으로 단어를 말함 단어의 첫글자 = 이전사람이 말한 글자의 끝 단어의 종류가 정해짐 한단어 두번X 단어들을 전부 사용가능한지 판단하고 어떤 순서로 단어를 사용해야하는지를 계산하는 문제 2. 오일러 트레일 이 문제는 각 단어의 첫부분과 끝부분으로 만들어진 간선을 가지는 그래프를 만들고 오일러 트레일과 오일러 경로 구하는 문제인것 같다. 하지만 책에서 구현한 오일러 경로를 아직 이해하지 못하겠다. 간선이 아닌 정점을 벡터에 집어넣는것, 아직 생각을 더해야 겠다. 또한 그래프를 생성하고 홀수점이 2개일때 오일러 트레일을 찾을려면 홀수점 두개중에서 시작점과 끝점을 찾아야하는게 문제이다. (책의 풀이를 보고, 방향그래프인점을 생각하지 못한 것을 알게되었다.) ..

1. 오일러 서킷 (Eulerian circuit) - 한붓 그리기 그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제 이와 같은 경로를 그래프 이론에서 오일러 서킷이라고 부른다. 오일러 서킷이 어느 경우에 존재할 수 있는지를 판단하는 단서는 반대로 오일러 서킷이 존재할 수 없는 경우를 생각하는것이다. 가장 생각하기 쉬운 경우는 그래프의 간선들이 두 개 이상의 컴포넌트에 나뉘어 있는 경우이다. (간선을 가지지 않은 컴포넌트는 예외) 정점의 차수(degree) 시작점이 u이고 끝점이 v인 특정 경로 u->v 가 모든 간선을 지나지 못하고 끝났다고 해보자. 이는 v에서 연결된 간선은 전부 한번 씩 지나갔다는 것을 의미한다. (갈곳이 없다) u != v: 항상 v는 홀수 개의 간..

1. 문제 고대어 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있지만, 사전에 포함된 단어의 순서들이 영어와 서로 다르다. 사전선이 다른 순서인지 알파벳 순서가 영어와 서로 다른 것인지 알기 위해 사전에 포함된 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산하는 프로그램을 작성하여라 2. DFS, 위상정렬, DAG - 사이클이 없는 방향그래프일때 해당 순서를 계산할 수 있을 것이다. - DAG를 다루는 문제로 각 알파벳을 정점으로하고 다음문자와의 비교를 통해 알파벳끼리의 간선을 생성할 수 있을 것이다. 이 문제는 사이클만 찾는 코드를 구현하면 쉽게 풀 수 있다. 사이클이 생기는 경우는 한가지만 체크하면된다. 위상정렬을 구하기 위해 dfs를 실행하는 중 함수가 종료될..

1. 그래프 탐색 (search) 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색이라고 한다 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다. 2. 깊이 우선 탐색 (Depth-first search, DFS) 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것 이다. 따라갈 간선이 없으면 마지막에 따라왔던 간선을 따라 뒤 돌아간다. 위 그림들은 정점의 번호가 작은것을 먼저 탐색하는 dfs의 예시이다. 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 ..

알고리즘 문제해결전략2 그래프파트 1. 그래프 그래프는 객체들의 상호 관계를 표현하기 위해 고안된 자료 구조이다. 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 트리와는 다르게 부모 자식 관계에 관한 제약이 없기 때문에 그래프는 트리보다 훨씬 다양한 구조를 표현할 수 있다. 2. 그래프의 정의 그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조이다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다. 3. 그래프의 종류 간선에 추가적인 속성을 부여 존재할 수 있는 간선이나 정점의 형태에 제약 가능 여러 속성을 함께 가지는 그..

1. 문제 이 문제는 여러 집합들을 세 집합으로 나누는 문제이다 - 아무것도 속해있지 않은 집합 - b집합과 대치되는 a집합 - a집합과 대치되는 b집합 m개의 댓글에서 두명의 정보가 주어진다. 두명의 정보는 ack -> 같은 편, dis -> 다른편 으로 주어지고 이를 통해 a와 b 집합으로 나누는 것이다. 그 후 a와 b의 모순이 생기면 모순이 생기는 댓글의 인덱스를 모순이 생기지 않으면 아무것도 속해있지 않은 집합의 크기와 a,b중 더 큰 집합의 크기를 더한 값을 반환하면 문제를 해결할 수 있다. 2. 상호 배타적 집합: 유니온-파인드 자료구조 ack a b 가 주어지면 a 와 b를 합친다. 이때 a와 b가 대치되는 사람 r[a] r[b] 가 있다고 하자 그러면 ack r[a] r[b] 또한 참이 ..