알고리즘10 [Python, 파이썬] 다익스트라 알고리즘 직접 구현해보기 파이썬으로 다익스트라 알고리즘을 직접 구현해보았다. 다익스트라 알고리즘은 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 위키피디아 나무위키 DirectedGraph (방향 그래프) 다익스트라 알고리즘을 적용할 그래프를 만들 기 위해 먼저 DirectedGraph (방향 그래프) 를 구현하였다. 다익스트라 알고리즘 (Dijkstra algorithm ) 구현 나무 위키에 단계별로 이미지와 함께 설명이 잘 되어있어 그대로 옮겼더니 정상적으로 동작하였다. python에서 static method 구현하기 관련해서 찾아보니 classmethod 와 staticmethod 에 대한 이야기가 나왔다. 나는 classmethod 를 이용해서 Dijkstra.find_shortest_path(graph, "A.. 2023. 9. 5. [큐, Queue] 동물 보호소 동물 보호소: 먼저 들어온 동물이 먼저 나가는 동물 보호소(animal shelter)가 있다고 하자. 이 보호소는 개와 고양이만 수용한다. 사람들은 보호소에서 가장 오래된 동물부터 입양할 수 있는데, 개와 고양이 중 어떤 동물을 데려갈지 선택할 수 있다. 하지만 특정한 동물을 지정해 데려갈 수는 없다. 이 시스템을 자료구조로 구현하라. 이 자료구조는 enqueue, dequeueAny, dequeueDog, dequeueCat의 연산을 제공해야 한다. 기본적으로 탑재되어 있는 LinkedList 자료구조를 사용해도 좋다. 일단 기능 요구사항을 정리해보자. enqueue : queue에 저장 dequeueAny : "먼저 들어온 동물이 먼저 나가는" 이라고 명시되어 있기 때문에, 개나 고양이 상관없이 오.. 2023. 8. 31. [스택, Stack] 현재 시점의 최소값 스택 Min: 기본적인 push와 pop 기능이 구현된 스택에서 최솟값을 반환하는 min 함수를 추가하려고 한다. 어떻게 설계할 수 있겠는가? push, pop, min 연산은 모두 O(1) 시간에 동작해야 한다. 문제를 처음 봤을 때는 "최소값을 저장하는 변수를 만들어 push, pop 시에 업데이트 해주면 되는거 아닌가?" 라고 생각했는데 그렇게 할 경우 O(1) 로 처리해야한다는 조건에서 pop시에 O(n)이 되어버릴 것 같았고, 그렇다고 별도의 array를 만들어 관리하자니 마찬가지로 O(n)이 되어버릴 것 같았다. 우선 기본 stack을 구현해보자. stack은 배열을 이용해서 구현할 수 있다. class Stack: def __init__(self): self.stack = [] def pus.. 2023. 8. 29. 리스트의 합 리스트의 합: 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 첫 번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라. 입력 : (7→1→6) + (5→9→2), 즉 617 + 295 출력 : 2→1→9, 즉 912 class Node: def __init__(self, val=0, next=None): self.val = val self.next = next def sum_of_two_linked_list(a, b): number_a = linked_list_to_number(a) number_b.. 2023. 8. 25. 단방향 연결리스트의 중간 노드 삭제 중간 노드 삭제: 단방향 연결리스트가 주어졌을 떄 중간(정확히는 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다. 삭제할 노드(A) 접근 → 다음 노드(B = A.next) 접근 → A.next = B.next, A.value = B.value 하면 A 노드가 사라지게 된다. 코드 class Node: def __init__(self, val=0, next=None): self.val = val self.next = next def delete_node_in_middle(node_to_delete): # 첫 번째 노드나 마지막 노드는 삭제할 수 없다고 명시되어 있기 때문에 고려하지 않음. # 다음 노드의 값.. 2023. 8. 24. 문자열 회전 문자열 회전: 한 단어가 다른 문자열에 포함되어 있는 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌고, s2가 s1을 회전시킨 결과인지 판별하고자 한다(가령 'waterbottle'은 'erbottlewat'을 회전시켜 얻을 수 있는 문자열이다). isSubstring 메서드를 한 번만 호출해서 판별할 수 있는 코드를 작성하라. 그냥 문자열 length 만큼 한칸씩 돌려가면서 일치하는 경우가 있는지 확인하면 되는거 아닌가 생각이 들었다. def is_substring(a, b): char_array = list(b) for i in range(len(char_array)): char = char_array.pop(0) char_array.append(char.. 2023. 8. 22. 이전 1 2 다음
