스터디-공부/알고리즘13 [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. 스택 두 개로 큐 만들기 스택으로 큐: 스택 두 개로 큐 하나를 구현한 MyQueue 클래스를 구현하라 스택 두 개를 이용해서 엘리먼트들을 옮기면서 마지막 엘리먼트를 넘겨주나? 기본적인 Queue는 FIFO 이기 때문에 Queue 에서 필요한 기능은 push() : 뒤에 넣음 pop() : 앞에서 꺼내감 일 것 같다. 이 때 stack 이라고 자료구조를 명시해주었기 때문에 array에 직접 접근 하는 것이 아닌 stack의 함수만 이용해야 한다고 가정하고 문제를 풀어나가 보았다. class Stack: def __init__(self): self.stack = [] def push(self, value): return self.stack.append(value) def pop(self): if not self.stack: ret.. 2023. 8. 30. [스택, 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. 연결리스트 - 노드의 교집합 찾기 교집합: 단방향 연결리스트 두 개가 주어졌을 때 이 두 리스트의 교집합 노트를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 천 번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다. 단방향 알고리즘의 특성상 같은 노드를 바라보게 되면 그 이후로는 데이터가 같다. 따라서 뒤에서부터 길이를 일치시키면 되겠다. 예를 들어 a : 1 - 2 - 3 - 4 - 7 - 8 - 9 b : 5 - 6 - 7 - 8 - 9 라는 두 단방향 연결리스트가 있다면 둘이 같은 노드를 바라보는 7 부터는 동일하게 된다. 따라서 뒤에서 부터 a 1 2 3 4 7 8 9 b 5 6 7.. 2023. 8. 27. 리스트의 합 리스트의 합: 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 첫 번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라. 입력 : (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. 이전 1 2 3 다음
