제 6장: 그 외의 알고리즘들(3)

69. 그래프에서 최적 경로를 구하는 데이크스트라 알고리즘

• 최단 거리 및 최저 운임 이동경로 등의 최적경로를 구할 경우 그래프를 이용하는 데이크스트라 알고리즘이 유용
• 그래프로 아래 3 요소를 표현 한 뒤 최적 경로 구함
  • 꼭짓점: 출발점, 종착점 및 경유 지점
  • 변: 꼭짓점과 꼭짓점을 연결하는 경로
  • 변의 가중치: 경로를 통과하는 비용(시간 혹은 운임)
• 최적 경로 구하는 절차
  • 1단계: 출발점의 [검색된 플래그]를 켠다. 그 외 모든 꼭짓점의 [검색됨 플래그]를 끈다.
  • 2단계: [검색된 플래그]가 켜진 모든 꼭짓점과 변으로 연결된 [검색됨 플래그]가 켜진 꼭짓점 목록을 구한다.
  • 3단계: [검색된 플래그]가 켜져있는 꼭짓점으로 향하는 경로의 ‘가중치’합계와 2단계에서 구한 꼭짓점으로 향하는 ‘변의 가중치’합계가 가장 적은 꼭짓점을 새롭계 선택한다.
  • 4단계: 3단계에서 선택한 새 꼭짓점이 종착점일 경우 해당 꼭짓점까지의 경로를 최적경로로 삼는다.
    • 종착점이 아닐경우 그 꼭짓점의 검색됨 플래그를 켜고 2단계 절차를 다시 수행한다.

70. 자연수 n이 소수인지 여부를 거르는 에라토스테네스의 체

• 소수: 1과 자신만을 약수로 갖는 1보다 큰 자연수
• 에라토스테네스의 체: N까지의 자연수를 나열한 뒤 소수가 아닌 수(합성수)를 걸러냈을 때 마지막까지 남은 자연수가 소수이다.
• 자연수 2~N사이의 소수 수열 PRIME을 에라토스테네스의 체로 구하는 방법
  • 1단계: 2~N까지의 자연수 수열 DATA를 생성
  • 2단계: 수열 DATA의 1번째 요소 P를 소수 열 PRIME으로 이동
  • 3단계: 2단계에서 구한 소수의 배수를 수열 data에서 걸러낸다.
  • 4단계: 수열 DATA의 최대 값이 수열 PRIME의 최대 값의 제곱 이상이라면, 2~3단계를 반복한다.
  • 5단계: 수열 DATA에 남은 숫자를 소수 열 PRIME의 끝으로 이동시킨다.