Suzzang's DevLab Suzzang's DevLab

다익스트라 알고리즘은 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단 경로(shortest path)를 찾아주는 알고리즘이다.완전 탐색을 이용하면 많은 비용이 소모된다.이를 효율적으로 해결하기 위해 다익스트라 알고리즘을 사용한다.방문 가능한 노드들 중에서 가장 비용이 작은 노드를 선택하여 방문한다.즉, 우선순위가 높은 곳을 먼저 방문한다.우선순위 큐와의 관계우선순위 큐를 사용하면 원하는 조건에 따라 (min 또는 max) 자동 정렬이 이루어진다.이를 통해 다익스트라 알고리즘의 구현이 훨씬 간편해진다.중요한 점: 우선순위가 높은 데이터가 항상 큐의 맨 앞에 위치한다. # 간단한 수도 코드1. 우선순위 큐에 시작노드 추가 2. 우선순위가 가장 높은 노드 추출 3. 방문여부 확인 ..

우선순위 큐는 리스트와 완전 이진 트리를 활용하여 구현하는 두 가지 방법이 있다.예를 들어, 가장 작은 값을 먼저 빼내야 하는 경우를 생각해보면, 다음과 같은 시간 복잡도가 발생한다.리스트를 이용하는 경우정렬되지 않은 리스트에서는 삽입이 O(1)이지만 최소값을 찾는 데 O(N)의 시간 복잡도가 발생한다.정렬된 리스트를 사용할 경우, 삽입에 O(NlogN)의 시간이 걸리지만 최소값을 찾는 작업은 O(1)로 수행된다.완전 이진 트리를 이용하는 경우삽입과 삭제 모두 O(logN)의 시간 복잡도를 가지므로 더 효율적인 방법이다. 완전 이진 트리를 활용하려면 어떻게 구현해야 할까?완전 이진 트리를 효과적으로 구현하려면 힙(Heap) 자료구조를 사용하는 것이 적합하다.힙은 완전 이진 트리의 성질을 가지며 우선순위 ..

pow 함수는 python에서 제공하는 내장 함수로, 거듭제곱을 계산할 때 사용된다. 알고리즘 공부를 하다가 발견한 함수로, 거듭제곱 계산시 ** 연산자를 사용해도 되지만값이 매우 커지면 오버플로우가 발생한다. 이때, pow함수를 사용할 수 있다. 1. pow(base, exp)- base를 exp 만큼 거듭제곱한 결과를 반환한다. 2. pow(base, exp, mod)- base를 exp 만큼 거듭제곱한 다음, 그 값을 mod로 나눈 값의 나머지를 반환한다.     Ref. ChatGPT, Softeer

a = 0def func(): global a # 함수 바깥에 선언된 변수를 바로 참조 , 이걸 안해주면 지역 변수 a를 만들어 줘야한다. 그렇지 않으면 할당되기 전에 참조되었다고 에러 뜸 a += 1 for i in range(10): func() print(a)# 10a = 10def func(): print(a+20) # 그러나 단순히 이러한 값 참조는 허용된다. func()# 30array = [1,2,3,4,5]def fun(): array = [3,4,5] array.append(6) # 지역변수 array에 우선 참조 print(array) func()print(array) # 전역변수 array에 우선 참조# [3,4,5,6]# [1,2..

알고리즘 공부 하면서 발생한 에러다. chat GPT와 인터넷 검색 결과를 종합해보니 list라는 이름을 잘못 사용했을 때 발생합니다. 이 문제는 보통 사용자 정의 변수 이름과 파이썬 내장 함수의 이름이 충돌해서 생깁니다. 라고 한다. 변수명과 함수명이 같을 때 발생하는 에러였다.   그러나 변수명을 변경하고 나서도 똑같은 에러가 발생했다. 해결 방법은 맨 윗줄에 아래처럼 del을 붙이면 된다.del list    바로 해결완료!:)