본문 바로가기

PS/algorithm

 (7)
출발 노드에서 도착 노드까지 갈 수 있는 모든 경로 print하기 카카오 기출 등산코스 정하기(22 internship) 문제를 풀다가 출발 노드에서 도착 노드까지 갈 수 있는 모든 경로를 출력하는 방법을 알면 풀 수 있을 것이라는 생각이 들어서 알고리즘을 정리해보았습니다. 위와 같은 그래프가 있다고 할 때, 1에서 5까지 가는 경로인 1-2-3-4-5 1-2-4-5 1-2-5 를 모두 구하는 것이 목표입니다. 위의 그래프를 딕셔너리로 나타내면 다음과 같습니다. {1:[2], 2:[1,3,4,5], 3:[2,4], 4:[2,3,5], 5:[2,4]} 각 경로를 path라는 리스트에 저장을 해두고, dfs가 한 번 끝나는 시점마다 pop을 해주는 방식으로 (한 칸 뒤로 물러나서) 해결할 수 있습니다. n, m = map(int, input().split()) graph ..
최단 거리 알고리즘 비교 최단 거리를 구하는 알고리즘에는 크게 3가지 방법이 있다. 다익스트라, 플로이드 와셜, 그리고 벨만 포드 알고리즘이다. 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단 거리를 구할 때 사용하며, 매번 노드에 연결된 가장 짧은 가중치의 간선을 선택하면서 최단 거리를 갱신하는 방식으로 동작한다. 플로이드 와셜 알고리즘은 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 구할 때 사용하며, 거쳐가는 노드를 기준으로 거리를 갱신하는 방식으로 동작한다. 다익스트라 & 플로이드 와셜 비교 글은 다음을 참고 다익스트라 & 플로이드 와샬 최단 거리를 구하는 알고리즘 중 다익스트라와 플로이드 와샬에 대해 정리한다. 다익스트라는 특정 노드에서 다른 모든 노드로 가는 최단 거리를 구할 때 사용하며, 플로이..
다익스트라 & 플로이드 와샬 최단 거리를 구하는 알고리즘 중 다익스트라와 플로이드 와샬에 대해 정리한다. 다익스트라는 특정 노드에서 다른 모든 노드로 가는 최단 거리를 구할 때 사용하며, 플로이드 와샬은 모든 노드에서 다른 모든 노드로 가는 최단 거리를 구할 때 사용한다. 다익스트라 (Dijkstra) 특정 노드에서 다른 모든 노드로 가는 최단 거리를 구할 때 사용한다. heapq를 사용하여 각 노드로부터 거리가 가까운 우선 순위로 탐색한다. 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 5. 3과 4 반복 import heapq graph = { 1: [(2,1), (3,1)], ..
[알고리즘 팀 스터디] 3주차 알고리즘 팀 스터디 3주차 (22.03.06 - 22.03.12) 범위 1. 프로그래머스 힙 학습 내용 기본적으로 heapq를 사용하면 최소 힙을 만들 수 있고, 최대 힙을 만들기 위해서는 (-value, value) 값에 -를 붙인 것을 첫 번째 원소로 하여 쌍으로 묶어준 후에 힙을 만들면 됩니다. (이 때, 작은 값이 앞으로 오게 되므로 -8, -1, 3이 있다면 -8, -1, 3의 순으로 오게 됩니다.) 힙을 만들어 주면 오름차순으로 정렬되는 것은 아닙니다. 부모가 자식보다 작은 것은 자명하지만, 좌 우 숫자는 정렬되지 않기 때문입니다. 그래서 [1, 2, 4, 7, 3, 9, 5]를 힙으로 만들게 되면 [1, 2, 4, 7, 3, 9, 5]가 됩니다. heapq.heapify(힙으로 만들 리스트)..
[알고리즘 팀 스터디] 1주차 알고리즘 팀 스터디 1주차 (22.02.19 - 22.02.26) 범위 프로그래머스 해쉬 4문제 이것이 코딩테스트다 그리디 4문제 학습 내용 dict.keys() 딕셔너리의 키들만 나오는데, dict_keys()에 싸여서 나오므로 편하게 사용하기 위해 list로 변환 후 사용합니다. dict.values() 딕셔너리의 값들만 나오는데, dict_values()에 싸여서 나오므로 편하게 사용하기 위해 list로 변환 후 사용합니다. dict.fromkeys(key로 만들 대상, value로 지정해줄 값) 키 들을 딕셔너리에 세팅하고 싶을 때 사용합니다. key로 사용할 대상들이 리스트에 있으면, (keys = ["a", "b", "c", "d"]) result = dict.fromkeys(keys, 0)을..
약수 구하기 python n의 약수를 구하는 방법에 대해 알아보겠습니다. 방법1 첫 번째 방법은 1부터 n까지 반복문을 돌며 n을 나누었을 때 나머지가 0이면(나누어 떨어지면) 약수입니다. def getDivisors(n): res = list() for i in range(1, n+1): if (n % i) == 0: res.append(i) return res 방법2 두 번째 방법은 조금 더 효율적으로 계산하는 방법입니다. 1부터 루트n까지만 돌며 확인을 하는 방법입니다. 루트n보다 큰 수에서 n까지에는 1부터 루트n까지 돌며 구한 약수들의 짝이 되는 약수들만 남게 됩니다. 예를 들어서, 6의 약수를 구한다고 하면 루트6의 몫은 2이므로, 반복문을 두 번만 돌게됩니다. i가 1인 경우 6을 1로 나눈 나머지는 0이므로 1은 ..
[algorithm] 에라토스테네스의 체 python 에라토스테네스의 체는, 소수를 찾는 방법입니다. def getPrimeNumber(n): #n까지 숫자 중 소수를 찾는다 check = [True] * (n+1) #idx와 숫자를 일치시켜 사용하기 위해 n+1개 m = int(n**0.5) #sqrt(n)까지만 확인하면 된다. for i in range(2, m+1): if check: #소수면 for j in range(i+i, n+1, i): #해당 수의 배수만큼 씩 돌며 check[j] = False #지워줌 return [i for i in range(2, n+1) if check[i]] n이 소수인지 판별하는 방법 1. 2부터 n-1까지 나누어 보며 나머지가 모두 0이 아닌지(나누어 떨어지는 수가 없는지) 확인합니다. 2. 좀 더 발전시켜 2부..

티스토리툴바