GRAY | 추천 알고리즘의 과학 저자

문제설명 문제분석 각각의 송전탑을 노드라고 생각하면, 각 노드와 간선의 관계를 이루고 있는 기존 n개의 송전탑이 주어집니다. 이때 간선을 하나씩 제거해가면서 분리된 두 개의 그룹에 포함된 노드의 차를 구하고, 구해진 결과 중 최솟값을 리턴하는 문제입니다. 문제가 어려우니 조금 나눠서 적어보겠습니다. 모든 노드는 간선으로 이어져 있다. 각 노드는 최소 1개 이상의 간선이 존재한다. 노드와 노드를 이어주는 간선을 하나 제거하고, 이때 분리된 그룹의 노드 수를 비교한다. 결과값은 비교한 값 중에서 가장 작은 값이어야 한다. 문제를 단순화 했으니 이해하기 쉽게 코드를 짜보겠습니다. 이해하기 쉽게 코드작성하기 이 문제는 여러 방법으로 접근할 수 있습니다. 기본적으로 그래프의 모든 노드를 탐색해야하는 문제인 만큼 ..

DFS ( Depth-first search ) 의 꽃인 N queens 를 구현하였다. 물론 자의로 주어진 스켈레톤에 구현하였고, 타의로 내 레포지토리에 하나가 쌓이게 되었다. 우선 N queens를 구현하기에 앞서, BFS 와 DFS를 모른다면 이 링크를 통해 개념 정도는 숙지를 해두자. [Algorithm] BFS, DFS - 너비우선탐색, 깊이우선탐색 BFS와 DFS는 탐색에서 대조적으로 설명하는 대표적인 두가지 방법이다. BFS와 DFS의 중간 그 어딘가에는 Heuristic ( 휴리스틱 ) 함수를 사용한 A* search ( 에이스타 서치 ) 등이 존재한다. 오늘은 BFS와 DFS dev-gp.tistory.com Backtracking ( 백트래킹, 퇴각검색 ) 백트래킹은 한정 조건을 가지는..

BFS와 DFS는 탐색에서 대조적으로 설명하는 대표적인 두가지 방법이다. BFS와 DFS의 중간 그 어딘가에는 Heuristic ( 휴리스틱 ) 함수를 사용한 A* search ( 에이스타 서치 ) 등이 존재한다. 오늘은 BFS와 DFS에 대한 간략한 설명과, 트리구조에서 어떤 방식으로 접근하여 사용하는 지 이야기해보자. BFS ( Breadth-First Search, 너비 우선 탐색 ) BFS는 시작점에서 출발하여 종점에 도착할 때 까지 시작점으로부터 같은 거리에 있는 좌표 혹은 노드를 가장 먼저 탐색한다. 위 그림에서 왼쪽의 grid는 start로부터 end까지 도달하기 위해 BFS가 동작하는 모습을 단편적으로 보여준다. 마찬가지로 오른쪽의 트리에서 루트로부터 end에 도달할 때까지 거리가 가까운 ..