그냥 개발블로그에요

  • 홈
  • 태그

다이나믹 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

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

최근글과 인기글

  • 최근글
  • 인기글

최근댓글

공지사항

Copyright © Kakao Corp. All rights reserved.

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.