python5 [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. 연결리스트 - 노드의 교집합 찾기 교집합: 단방향 연결리스트 두 개가 주어졌을 때 이 두 리스트의 교집합 노트를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 천 번째 리스트에 있는 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. 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메소드를 작성하라. URL화: 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메소드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다 (자바로 구현한다면 배열 안에서 작업할 수 있도록 문자 배열(character array)을 이용하길 바란다). URL 인코딩에 대해 궁금하다면 https://en.wikipedia.org/wiki/URL_encoding 을 참고하자. 한국어 위키에는 퍼센트 인코딩 이라고 되어있다. 이 문제를 해결하는 가장 쉬운 방법은 replace를 하는것 이겠지만, 그 것을 묻는 것은 아닐 것이다. 이 문제는 문자로 구성된 배열(character array)을 이용해 문제를 풀기를 원했고 최종적으로.. 2023. 8. 18. 이전 1 다음
