그냥 개발블로그에요

알아보기 Greedy는 탐욕스러운 이라는 뜻이다. 선택의 순간마다 당장 제일 좋아보이는 경우를 선택한다. 여러 경우 중에 하나를 선택해야할 때, 그 순간 최적이라고 생각하는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 그 순간 선택한 결정은 지역적으로는 최적이지만, 전역적인(최종적인) 해답이 최적이라는 보장은 없다. 따라서 그리디 알고리즘을 적용하려면, 지역적으로 최적이면서 전역적으로 최적이어야 한다. 조건 Greedy choice property - 탐욕적 선택 속성 - 앞의 선택이 이후의 선택에 영향을 주지 않는다. optimal substructure - 최적 부분 구조 - 문제에 대한 최종 해결법은 부분 문제에 대한 최적해이다. 이러한 조건이 성립하지 않을때에도, 근사 알고리즘..

알아보기 다익스트라 알고리즘은 가중치 그래프에서 가중치의 값이 모두 양수일 때 한 노드에서 각 노드까지의 최소거리를 구할때 사용한다. 기본적으로 그리디과 다이나믹을 사용한다. 방문한 노드들을 체크하여, 체크하지 않은 노드들 중 가장 비용이 적은 노드를 선택(그리디)하고, 그 비용과 기존의 비용을 비교하여 값을 갱신(프로그래밍)하는 방식이다. 적용해보기 위의 그래프를 이용하여 1번 노드에서 각 노드까지의 최소비용 구해보도록 하자. 각 노드로 가는 최소 비용을 담는 배열 dis을 생성한다. 그 값들은 최대값으로 일단 해놓고, 1번정점을 0으로 한 뒤 시작한다. 배열 값 중 0의 값이 최소이므로 체크해 놓고, 1번노드에서 바로 갈 수 있는 노드에 대한 비용을 각 노드가 가진 현재 값과 비교하여 더 작다면 바꾼..