전체 글

그래프의 탐색그래프를 탐색한다는 것은 그래프의 정점들을 탐색한다는 의미이다.이때 정점을 탐색하는 순서가 중요한데 크게 두 가지로 나눌 수 있다. 바로 깊이 우선 탐색과 너비 우선 탐색이다. 깊이 우선 탐색(DFS: Depth First Search)말 그대로 깊이를 우선적으로 탐색한다.한 정점을 기준으로 더 이상 탐색할 정점이 없을 때까지 가보고 없으면 최근에 방문했던 노드로 되돌아가 다음 가지 않은 노드를 방문한다. 너비 우선 탐색(BFS: Breadth First Search)말 그대로 너비를 우선적으로 탐색한다.한 정점을 기준으로 가장 가까운 정점을 모두 방문하고 다음 정점으로 넘어간다.그 정점에서 가장 가까운 정점부터 모두 방문한다. 지금부터 각각에 대해 자세히 알아보도록 하자. 깊이 우선 탐색(..

그래프(Graph)란?그래프(Graph)란 노드와 간선을 이용한 비선형 데이터 구조로 데이터 간의 관계를 표현하는데 사용된다.데이터를 노드로 데이터 간의 관계는 간선으로 표현한다. 또한 데이터 간의 관계에서 정도를 표현할 필요가 있다면 가중치를 사용해 표현한다.그림으로 표현하면 다음과 같다.참고로 노드, 간선, 가중치는 다음과 같은 용어로 혼용된다.노드(Node)정점버텍스(vertex)간선엣지(Edge)가중치(Weight)비용(cost) 그래프의 종류방향성간선은 그래프에서 두 정점간의 관계를 나타낸다.그래프에서 간선은 방향을 가질 수도 있고 없을 수도 있다.그래프가 방향이 있는 간선을 포함하면 방향 그래프그래프가 방향이 없는 간선을 포함하면 무방향 그래프라고 한다.가중치그래프에선 가중치를 통해 관계의 정..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr2. 풀이 과정이 문제는 최소신장트리를 구현하는 문제이다.최소신장트리란 가중치가 부여된 연결 그래프에서 모든 정점을 포함하면서, 모든 간선의 가중치 합이 최소가 되는 트리를 말한다. 최소신장트리를 구현하는 방법은 두 가지가 있다. 1. 크루스칼 알고리즘 1) 간선들을 비용을 기준으로 오름차순으로 정렬한다. 2) 적은 비용의 간선부터 시작해 해당 간선이 잇는 두 노드를 연결시킨다. 이때 사이클이 발생하지 않도록 주의해야한다. 3) 모든 노드를 방문할 때까지 반복해 가중치의 합을 구한다.  2. 프림 알고리..

1. 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr2. 풀이 과정끝맛일기에서 탈락자가 나오는 경우는 두 가지이다. 1. 이전 단어의 마지막 글자로 시작하지 않은 경우2. 이미 나온 단어를 다시 말한 경우 이 두 가지 조건에 해당하면 그 순간의 유저 번호와 몇번째 사이클이었는지를 반환하면 된다.1. 이전 단어의 마지막 글자로 시작하지 않은 경우를 체크하기 위해 HashSet을 사용하고2. 이미 나온 단어를 다시 말한 경우를 체크하기 위해 이전 단어의 마지막 단어와 현재 단어의 첫번째 단어를 비교했다. 이게 끝이다. 이제 코드를 보자 3. 내 코드impor..