알고리즘 문제를 풀다가 막힌 부분이 있어 정리하려고 한다!1. 정수를 리스트에 담기118372라는 정수를 배열에 한자리씩 담으려고 한다.이때 list()와 map()를 사용한다.중요한 것은 str() 문자열로 변경한 뒤에 map으로 감싸줘야한다!이유는 map함수가 반복 가능한(iterable) 객체를 두 번째 인자에 필요로 하는데, n은 정수이기 때문에 str문자열로 변경해줘야한다. list(map(int, str(n))n = 118372n_list = list(map(int, str(n)) # [1, 1, 8, 3, 7, 2] 2. 정수가 담긴 리스트를 하나의 정수로 표현하기정수가 담긴 리스트 [1, 1, 8, 3, 7, 2]를 118372로 표현하는 방법처음에는 하나씩 빼서 str()로 바꿔서 합치..
Algorithms
위상정렬 (Topopogical sort)위상 정렬은 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것이다.방향 그래프에서 간선 가 있다면, 정점 u는 정점 v를 선행하여 정렬한다.방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열해야한다.활용 예로는 선수 과목은 과목들의 선행 관계를 표현한다.🌟 구현정점에 들어오는 간선수를 저장하는 진입차수(in_degree)를 사용한다.동작방식모든 정점의 in_degree 설정순서에 맞도록 리스트 설정 예) graph[2] = [1,3] : 정점 2는 정점 1과 정점 3보다 선행함.in_degree가 0인 정점은 큐에 추가큐가 빌 때까지 반복3.1 큐의 앞 요소를 popleft()로 가져와 그에 맞는 리스트를 꺼냄3.2 리스트에서 나온 정점의 i..
유튜브로 "이것이 코딩이다" DFS&BFS 문제를 풀어보다 "미로 탈출" 문제에서 오류가 발생했다.👾 문제 📍 풀이입력3 31100100115 6101010111111000001111111111111인접한 노드에 자신의 노드 값을 +1 함 ⚒️ 코드from collections import dequen, m = map(int, input().split())graph = [] * n # 잘못된 부분 ㅠfor _ in range(n): graph.append(list(map(int, input().split())))result = 0dx = [1, -1, 0, 0]dy = [0, 0, 1, -1]def bfs(x, y): myqueue = deque() myqueue.append((x, ..
다익스트라 알고리즘에 대해 [이전글]에서 어떻게 풀어야하는지 정리해뒀다.요약하자면![이전글] 에서는 인접 노드의 distance > 현재 노드의 distance + 인접 노드까지의 distance 를 비교해야 했다.이를 위해서 우선순위 큐(PriorityQueue)와, 노드 방문 여부, disatnce를 고려해야 한다.하지만 이번 문제에선 heapq를 사용한다.파이썬 내장 heapq도 [이전글]에서 정리했다.👾 K번째 최단 경로 찾기 - 백준 1854번https://www.acmicpc.net/problem/1854예제 입력15 10 21 2 21 3 71 4 51 5 62 4 22 3 43 4 63 5 85 2 45 4 1예제 출력1-1107514 📍 풀이이전과는 다르게 k번째 거리를 구해야한다. ..
🌟 우선순위 큐란?우선순위를 가진 항목들을 저장하는 큐 FIFO 순서가 아니라 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐는 2가지로 구분된다.최소 우선순위 큐 : 가장 우선순위가 **낮은** 요소부터 삭제최대 우선순위큐 : 가장 우선순위가 **높은** 요소부터 삭제우선순위 큐 구현 방법배열을 이용한 우선순위 큐연결리스트를 이용한 우선순위 큐힙(heap)을 이용한 우선순위 큐여기에선 힙을 이용한 우선순위 큐를 설명한다.힙을 이용한 우선순위 큐 시간 복잡도는 O(logn)이다. 🌟 힙(heap) 이란?key(부모노드) >= key(자식노드) 또는 key(부모노드) 힙 종류최대 힙 : key(부모노드) >= key(자식노드) 완전 이진트리최소 힙 : key(부모노드) ✔️ Heapqpyt..
🌟 다익스트라 알고리즘이란?하나의 시작 정점에서 다르정점까지의 최단 경로를 계산하는 것이다. 최단 경로 알고리즘이라고도 불린다! ⚒️ Dijkstra의 최단 경로 알고리즘다음과 같은 그림에서 최단경로를 계산하려고 한다. 각 단계에서 S안에 있지 않은 정점 중에서 가장 distance값이 작은 정점을 S에 추가한다.정점 W를 거쳐서 정점 u로 가는 가상적인 더 짧은 경로가 있다고 가정해보자! 그러면 정점 v에서 정점 u까지의 거리는 v->w->u (경로2 + 경로3) 거리가 된다.그러나 경로 2는 경로 1보다 항상 길 수 밖에 없다. 현재 distance 값이 가장 작은 정점은 u이기 때문이다. => 거리1 이 알고리즘을 해결하기 위해선 3가지를 고려해야한다. directionvisitedqueued..
