다익스트라 알고리즘

다익스트라 알고리즘다익스트라 알고리즘은 최단거리를 구하는 알고리즘입니다.다익스트라 알고리즘을 사용하면, 하나의 노드로부터 최단 거리에 있는 다른 노드를 탐색할 수 있습니다.목적지와 가중치를 저장하여 가장 적은 가중치의 경로를 탐색할 수 있으며, 지하철 노선 탐색을 예로 들 수 있습니다.최단 거리를 구할 노드로부터 거리가 입력된 노드를 돌아가면서 더 거리가 짧은 값이 나오면 값을 새로 갱신합니다. 알고리즘 구성 각 노드까지의 거리를 최대값으로 초기화하고, 해당 노드로 이동할 수 있는 더 작은 값일 나올 때 값을 갱신합니다.INF = 1e8distance = [INF] * (n+1) INF는 정수의 최대값이며, 1~n까지의 거리값을 저장하기 위해서 n+1로 초기화합니다. 다음으로는 도착 노드와 가중치 값을 ..

• format_list_bulleted Algorithm
• · 2024. 1. 7.
• textsms

[Python] 파이썬의 순열과 조합 알고리즘

파이썬 라이브러리 순열과 조합의 경우 파이썬 내부의 라이브러리를 사용하면 직접 구현하는것 보다 훨씬 빠른 속도로 구현할 수 있다. 알고리즘 문제의 경우 빠른 속도를 요구하므로, 순열과 조합의 라이브러리를 꼭 숙지해야 한다. 순열과 조합은 매우 비슷해서 구분이 어렵고 헷갈리기 때문에 차이를 알고 구별할 수 있도록 학습한다. 파이썬에서는 itertools를 사용해서 순열과 조합을 구현할 수있다. from itertools import permutations https://docs.python.org/ko/3/library/itertools.html itertools — Functions creating iterators for efficient looping This module implements a nu..

• format_list_bulleted Algorithm
• · 2023. 9. 17.
• textsms

[알고리즘] 에라토스테네스의 체

에라토스테네스의 체 소수를 찾을 때 가장 적은 시간 복잡도를 소요하는 알고리즘이다. 여러 개의 수가 소수인지 아닌지를 판별하며, N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스보다 시간 복잡도가 높은 알고리즘과 비교하여 해당 알고리즘의 이점을 파악한다. 일반적인 소수 찾기 알고리즘 소수의 판별법을 사용한다. 소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 6의 경우 1,2,3,5을 약수를 가지므로 소수가 아니고, 7의 경우 1,7만을 약수로 가지므로 소수라고 할 수 있다. 가장 간단한 소수 판별법은 아래와 같으며, 어떤 수의 소수를 찾을 때 시간 복잡도가 O(n)이 된다. # 가장 간단한 소수 판별법 # 모든 수를 나누어서 소..

• format_list_bulleted Algorithm
• · 2023. 5. 17.
• textsms

[알고리즘] 백 트래킹 기법 이해하기

[백 트래킹 기법 이해 (BackTracking)] - 백트래킹 혹은 퇴각 검색으로 부르며, 제약 조건 만족 문제에서 해를 찾기 위한 전략이다. * 제약조건 만족 : 해를 찾기 위해 후보군에 제약 조건을 점진적 체크, 해당 후보군이 제약 조건을 만족할 수없다고 판단되면 즉시 backtrack으로 넘어가서 이 후보군을 탐색 후보군에서 완전 제외 시킴* 즉 가능성이 없는 후보군을 삭제한 후, 해당 후보군을 다시는 체크하지 않으며, 이를 통해 최적의 해를 찾는 방법이다. 행렬에서 각 행이 0,1,2,3... 과 같이 점진적 증가인 경우를 카운트해서 반환한다면,그 행의 맨 뒤까지 탐색할 때 점진적인 증가가 발생되지 않은 시점에서 해당 후보군을 제외시키고, 다른 탐색 후보군을 탐색하는 방법 또 퇴각 검색 기법 중..

• format_list_bulleted Algorithm
• · 2022. 12. 6.
• textsms

[자료구조] python으로 linked list 구현하기

[링크드 리스트] 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 python으로 알고리즘 문제를 풀던 중에 링크드 리스트의 구현이 필요해져서 공부한 기록 일반적인 링크드 리스트의 노드는 아래와 같이 구현한다. class Node: def __init__(self, data): self.data = data self.next = None data는 현재 데이터, next는 다음 데이터를 가지고 있다. 이제 LinkedList를 구성해야 한다. class LinkedList: def __init__(self, data): self.head = Node(data) # 헤더부터 탐색하기 def append(self, data): current = self.head..

• format_list_bulleted Algorithm
• · 2022. 11. 28.
• textsms

DRF의 동작 방식 알기 model, serializer, view, url

DRF를 사용하기 위해서는 DRF의 동작 방식을 알아야 했다. DRF에서는 model - serializer - view - url 순으로 구현해야 한다. 개인 프로젝트를 진행하면서 작성한 코드로 해당 방식에 대한 동작을 살펴보겠다. user App 내에서 구현하였다. [model 구현] 모델은 데이터이다. class searchLog(models.Model): username = models.ForeignKey(Profile,on_delete=models.CASCADE,related_name='searchLogPost',to_field='username_id') log = models.CharField(max_length=50,db_column='log') model에서 serchLog라는 class를..

• format_list_bulleted Python,Django,DRF
• · 2022. 11. 5.
• textsms