지금까지 BFS, Dijksta 와 같이 써먹어왔던 알고리즘은 '모든' 길을 탐색해야 한다는 사실이 있다.. 따라서, 모든 지점이 탐색된다는 불편함이 존재한다. 길찾기를 할 때는 목적지만 보는게 더 좋기 때문! 그래서 이를 개선한 알고리즘이 바로 A* 알고리즘이다. A* 알고리즘에서 새로운 개념이 등장하는데 그것은 휴리스틱이다. 휴리스틱은 길을 어림잡아 매긴 수치이다.파란색이 길이고, 빨간색이 벽이고 녹색이 도착지점이다. 여기서 휴리스틱은 3이다.. 내가 갈 수 있는 길인지 판단하지 않고 그냥 나와 목적지까지의 거리를 가중치로 부여하는것. 그래서 현재 거리와 (G) 휴리스틱(H)가 더해진 값 F로 계산을 진행한다. (F = G + H) 이렇게 아무 의미 없이 탐색을 하는 다익스트라와 달리 이 휴리스틱이 ..

지금까지는 우선순위 큐에서 최대값이 먼저 나오는 구조였다.. 하지만 최소값이 먼저 나오고 싶게 할 때가 있을것이다. (최단경로 등) Enqueue와 Dequeue를 할 때 이 조건을 반대로 하면 될것이다.. 하지만 이러한 구조를 건들지 않고 할 수 있는 하나의 방법이 더 있었는데 Enqueue를 할 때, 음수를 넣어주는 방법도 있었다..... 와..ㅋㅋ 음수는 수(절댓값)가 클수록 작다는 성질이 있기 때문에 -10이 제일 큰 수가 될것 근데 음수가 나오니까 이런 구조에서는 Dequeue를 할 때 -1을 곱해줌! 자 이런 방법이 있었고 이제 이 우선순위 큐에 int형 말고 다른 자료형이 들어오려면 어떻게 해야할까.. 먼저, Generic 형태로 모든 자료형을 받는다 하지만 '비교' 에서 문제가 생긴..

이전에 힙 트리라는 자료구조에 대해 알아보았다. 우선순위 큐는 이 힙 트리를 이용한 자료구조인데... 간단하게 우선순위가 있는 애가 맨 첫번째로 나가는 자료구조이다! 힙 트리는 최상위(root)에 가장 큰 놈이 있으니까 root를 빼는 방식 이제 '우선순위 큐' 를 구현해보자. List (힙 트리의 제약조건으로 List를 Tree로 사용할 수 있다) List로 데이터를 받고 힙트리의 제약조건중 부모가 커야하니까 들어온 데이터를 내 부모와 비교한다. (현재 - 1) / 2가 부모가 된다는 사실은 전에 보았으니 생략. 그리고 내가 더 크다면 부모와 나를 교체하는 방식으로 끝까지 올라가도록 반복! Dequeue 도 구현해보면 결국 힙의 제약조건으로 인해 0번째 인덱스가 제일 큰 수라는것을 알 수 있기에 과감히..

이진 트리는 부모가 최대 2개의 자식을 가지는 트리이다. 이런식의 구조를 가지고 있음! 이진 트리 중에 이진 검색 트리가 있는데 왼쪽에는 부모보다 작은것, 오른쪽에는 부모보다 큰 것이 존재함! 이러한 구조를 지니고 있어 검색에 용이하다! 32라는 값을 찾는다면? 크니까 오른쪽 작으니까 왼쪽 이렇게 빠르게 찾을 수 있다. (이진탐색 알고리즘과 비슷한 것 같음) 하지만 하나의 문제점이 있는데, 이렇게 한줄로 할 경우에는 결국 이진 검색 트리의 이점을 잃고 리스트와 동일한 구조가 되어버리니까 삽입, 삭제가 일어날 때 트리를 재 배치한다고 한다! 이진 검색 트리와 비슷한 힙 트리라는 개념도 있는데 힙 트리는 이진 트리의 구조를 하고있으나 몇가지의 제약조건이 추가된 형태다. 제약조건중 첫 번째는 부모가 자식보다 ..

트리를 구현한다면 이렇게 자신의 데이터와 자식들을 List로 가지고 있게 할수 있다. 그리고 어제 그렸던 그림과 같은 구조를 표현한다면? 이런식으로 Children을 추가하는 방식으로 Tree를 구현함! 이제 Tree를 순회하는 방법에 대해서 알아보자면 트리의 구조상 재귀함수로 순회하는것이 합리적 (트리를 자르면 트리..를 자르면 트리) 이렇게 자식을 돌면서 재귀함수로 트리의 구조같이 쭉 뻗어나가면서 출력을 진행한다. 굿

BFS를 이용하여 길찾기 알고리즘을 시도해보았다. 하지만, 길을 가는 비용이 모두 동일하다 라는 조건이 성립해야만 이 BFS 알고리즘을 사용할 수 있다. 그렇다면, 이제 길에 각기 다른 비용이 들어간다고 해 보자. 어떤게 비용이 적게들까?? 바로 1, 2, 3, 4, 5 이렇게 가는 방법이다. 왜냐면 5의 비용을 적기 때문! 이렇게 가중치가 있을 경우 최단경로를 구할 수 있는 알고리즘이 다익스트라 알고리즘이다. 이제 다익스트라 알고리즘을 코드로 구현 해 보자. 우리가 눈으로 볼 때는 당연한 말이지만 알고리즘을 이해하려면 항상 컴퓨터적인 사고를 해야한다. 나머지 비용은 모른다. 오로지 내 앞에 연결된 Vertex까지의 비용을 알아내야 한다! 즉, 내가 연결된 Vertex의 모든 비용을 비교해서 최소 비용을..