코딩못하는사람

벨만-포드 알고리즘 다익스트라와 마찬가지로 SSP알고리즘인 벨만-포드 알고리즘은 음의 가중치를 다룰 수 있다. 그런데 다음과 같이 음의 가중치로 인해 순환 구조를 가진다면 최단경로를 구할 수 없다. 따라서 벨만-포드 알고리즘은 최단경로를 구하는 것과 이 그래프에서 최단경로를 구할 수 있는지 없는지를 판별하는 과정 두 과정으로 나눠진다. 벨만 포드 알고리즘은 V-1번 모든 간선을 Relax하는 작업을 수행한다. 최단경로구하기 동작과정은 각 정점들을 돌아 가면서 모든 간선들을 탐색한다, 단 맨 처음은 시작점부터 탐색한다( 처음 이후에는 순서 상관없음) D(s,v)=D(s,u)+w(u,v) 이 과정을 V-1번 탐색하는 이유는 s에서 v까지 가는 경우에서 v를 뺀 모든 경로가 각각 최단거리일 수 있기 때문이다(..

비트 마스크란? 비트는 컴퓨터에서 다루는 최소 단위이다. 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크 라고 한다 프로그래밍을 하며 비트마스크가 왜 필요한지 알아봤다. 비트연산을 통한 삽입, 삭제, 조회 등이 간단해짐 더 간결한 코드 작성이 가능 더 빠른 연산이 가능 비트마스크를 이용한 정수 표현으로 다이나믹 프로그래밍이 가능함 사실 4번 DP를 활용하기 위해 파이썬을 이용해서 비트마스크를 쓰는 방법을 연습했다. DFS를 할때 내가 방문했던 곳들의 상태를 저장하기 까다로울텐데 비트마스크를 쓰면 간단하게 쓸 수 있다.(n이 작다면) 파이썬에는 bin함수가 내장되있어서 쉽게 2진수로 출력이 가능하다 기본 계산 AND연산 bin(0b1010011010 & 0b110110110..