그냥 개발블로그에요

  • 홈
  • 태그

다이나믹 1

Daijkstra 다익스트라: 과정 이해하고 적용해보기

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

코딩테스트/알고리즘 2023.11.03
이전
1
다음
더보기
프로필사진

그냥 개발블로그에요

  • 분류 전체보기 (34)
    • C++ (2)
    • PROJECT (1)
      • 라이브 스트리밍 플랫폼 (1)
    • MAC (1)
    • SPRING (12)
    • DB (2)
    • JAVA (0)
    • AWS (1)
    • CS (1)
      • 컴퓨터 구조 (0)
      • 운영체제 (1)
    • 코딩테스트 (7)
      • 프로그래머스 (0)
      • 알고리즘 (6)
    • Obsidian (1)
    • 리뷰 (4)
      • 전자제품 (4)
      • 스피커 (0)
      • 모자 (0)

Tag

BFS, M1, cpu, mac, 인증, 프로세스, SpringBoot, 인가, swagger, redis, 운영체제, 알고리즘, 스레드, spring, 시간복잡도, 그리디, C++, JWT, Authentication, dfs,

최근글과 인기글

  • 최근글
  • 인기글

최근댓글

공지사항

Copyright © Kakao Corp. All rights reserved.

티스토리툴바