코딩못하는사람

단일 출발지 최단 경로( Single Source Shortest Path ) 하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것에는 두가지 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다. 다익스트라와 벨만-포드의 차이는 음의 가중치를 다룰수 있냐 없냐의 차이이다.(벨만-포드가 가능) 다익스트라 알고리즘은 최소힙을 이용하여 구현할 수 있다. 우리가 알아볼 시작지점으로부터 다른 도착지점까지의 가중치 배열을 INF로 초기화한다.ans=[INF]*(v+1) 시작지점의 값을 0으로 초기화하고 heap에 (가중치,위치)을 넣어준다 while문을 사용하여 heappop을 통하여 최소값을 뽑아주고 뽑힌 (가중치+위치에 연결된 곳들의 가중치)로 연결된 곳들을 relax(경로가 더 효율적이면..

유니온 파인드 말 그대로 집합,공동체를 찾는다는 것이다. 집합으로 묶어서 풀면 좋은 문제를 풀 때 효율적으로 풀기좋다. 특히 집합끼리 묶는것을 쉽게 만들어 준다. 모든 원소들을 자기 자신을 부모노드로 초기화 한다. 집합을 합치는 것은 부모노드를 같게 만들어줌으로써 집합을 만들 수 있다. 같은집합에 속해있는것은 find를 통해 부모노드를 찾는 함수를 활용하여 같은 부모노드를 가르키면 같은 집합,아니면 다른 집합에 포함되있는 것이다. 유니온 파인드에는 3가지 과정이 있다. 1.각자 자신으로 부모노드를 초기화한다. 2.find(부모노드 찾기) def find(v): if parent[v]==v: return v else: parent[v]=find(parent[v]) return parent[v] 사실 els..

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