개발하고싶은 블로그

순환하지 않는 유향 그래프를 방향성에 거스르지 않도록 순서대로 배열하는 방법 말 그대로 순환하지 않는 유향 그래프에서 순서가 정해져 있을 때 그 순서대로 방문을 하고 싶을 때 사용할 수 있는 알고리즘이다. 그림을 통해서 예시를 하나 들어보겠다. 만약 아래와 같은 그래프가 있다고 가정해 보자 처음으로 진입점이 존재하지 않는 1부터 시작해 보자. (1을 큐에 넣는다) 현재 큐에는 1만 있으므로 큐에서 1을 꺼내면 1이 가리키고 있는 2, 3이 후보가 된다. 2, 3 모두 앞의 순서가 1밖에 없다. 그러므로 2, 3 모두 방문이 가능하므로 큐에 2, 3을 넣는다. 다시 큐에서 2를 꺼내 2가 가리키고 있는 4, 5에 대해서 확인해 보면 5는 2 이외에도 3이 앞 순서로 있기 때문에 현재 작업할 수 없는 상태이..

플러드 필(flood fill) 혹은 시드 필(seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. - 위키백과 위와 같은 다차원 배열이 있다고 가정했을 때, 검은색으로 칠해진 부분은 연결되지 않은 영역이라고 하자. 그러면 위의 다차원 배열에 대해서 특정 칸과 연결된 영역을 찾고 싶을 때 플러드 필 알고리즘을 이용해서 찾을 수 있다. (연결된 영역은 상하좌우로 접근 가능한 경우이다) 만약 0.0과 연결된 영역을 찾는다면 아래와 같은 영역이 찾아진다. 또한 0.3과 연결된 영역을 찾으면 아래와 같은 영역이다.이렇게 연결된 영역을 찾고 싶을 때 사용할 수 있는 알고리즘이 플러드 필 알고리즘이다. 스택 기반이나 큐 기반으로 구현할 수 있다. 자세한 사항은 아래 위키백과를 참조하자. ..

idea-sketch.tistory.com/29 [알고리즘] 되추적(Backtracking)을 알아보자. 오늘의 주제는 되추적(Backtracking) 이다. 저번 포스팅인 깊이우선탐색(Depth-First Search)과 넓이우선탐색(Breath-First Search)의 몸풀기를 거치고 최단경로(Shortest Path) 알고리즘에 들어가는 첫 걸음이라.. idea-sketch.tistory.com 여기에 설명이 잘 되어 있다. 요지는 dfs를 스택을 이용하여 구현한다면 "스택을 사용하고 스택에 넣기 전에 유망성 검사를 한다. 유망성 검사 조건을 어떻게 할 것인가" 인 것 같다