코딩못하는사람

단일 출발지 최단 경로( Single Source Shortest Path ) 하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것에는 두가지 다익스트라 알고리즘과 벨만-포드 알고리즘이 있다. 다익스트라와 벨만-포드의 차이는 음의 가중치를 다룰수 있냐 없냐의 차이이다.(벨만-포드가 가능) 다익스트라 알고리즘은 최소힙을 이용하여 구현할 수 있다. 우리가 알아볼 시작지점으로부터 다른 도착지점까지의 가중치 배열을 INF로 초기화한다.ans=[INF]*(v+1) 시작지점의 값을 0으로 초기화하고 heap에 (가중치,위치)을 넣어준다 while문을 사용하여 heappop을 통하여 최소값을 뽑아주고 뽑힌 (가중치+위치에 연결된 곳들의 가중치)로 연결된 곳들을 relax(경로가 더 효율적이면..

https://www.acmicpc.net/problem/13913 1.접근 bfs역추적을 방문했던곳인지 확인하는 check배열을 만들어 바로 전 값을 저장하도록 해서 추적하게 했다. 2.풀이 출발지점에서 도착지점까지 가는 +1,-1,*2의 3가지 뿌리로 bfs를 만들어준다. 여기서 방문했던 곳인지 확인하는 check 배열을 -1로 초기화 시킨다.bfs를 통하여 방문할때마다 cnt대신에 자신의 바로 전 위치를 집어 넣어주면 -1도 아니게 되고 어떤 경로로 현재 지점에 와있는지 알 수 있게된다. 따라서 큐에서 도착지점 값이 나올 때 cnt값을 반환하고 도착지점에서부터 시작지점까지 check배열을 순서대로 거꾸로 따라가보면 어느 경로로 왔는지 나온다.(마지막 while 문) 3.코드 4.배운점 처음에 che..

유니온 파인드 말 그대로 집합,공동체를 찾는다는 것이다. 집합으로 묶어서 풀면 좋은 문제를 풀 때 효율적으로 풀기좋다. 특히 집합끼리 묶는것을 쉽게 만들어 준다. 모든 원소들을 자기 자신을 부모노드로 초기화 한다. 집합을 합치는 것은 부모노드를 같게 만들어줌으로써 집합을 만들 수 있다. 같은집합에 속해있는것은 find를 통해 부모노드를 찾는 함수를 활용하여 같은 부모노드를 가르키면 같은 집합,아니면 다른 집합에 포함되있는 것이다. 유니온 파인드에는 3가지 과정이 있다. 1.각자 자신으로 부모노드를 초기화한다. 2.find(부모노드 찾기) def find(v): if parent[v]==v: return v else: parent[v]=find(parent[v]) return parent[v] 사실 els..

두개의 문제는 전위,중위,후위순회을 활용해서 문제를 풀어봐야한다. 2263 트리의 순회 https://www.acmicpc.net/problem/2263 1.접근 생각하기 어려웠지만 직접 트리를 그려서 중위탐색과 후위 탐색을 해보면 전위 탐색을 어떤식으로 해야할지 보였다. 2.풀이 중위순회과 후위순회을 그려보면 규칙을 찾을 수 있다. 후위 탐색된 리스트에서 맨 마지막 값은 중위 순회의 루트노드일 것이다.따라서 중위 탐색에서 그 루트노드의 인덱스를 구해서 왼쪽 오른쪽 나눠서 재귀적인 문제로 만들어 풀면 된다. 여기서 후위순회에서 구한 루트값의 인덱스를 구할 때 일일이 탐색하게 되면 시간초과가 날게 분명하므로 for i in range(n): num[in_order[i]-1]=i 루트값이 어디있는지 인덱스를..