백준

[python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 )

위상정렬 어떤 일을 하는 순서를 찾는 알고리즘, 즉 순서가 정해져 있는 일을 차례대로 수행하는 것이다. 답이 여러개 가능 DAG(Directed Acyclic Graph)에만 적용 가능 큐나 스택을 사용 DAG(Directed Acyclic Graph) 방향성 비순환 그래프는 개별요소들이 특정한 방향을 향하고, 순환하지 않는것. ( o -> o -> o 요런 형태) 사실 그냥 봐서는 잘 이해가 가기 어렵다. 그러므로 고수님의 링크(https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html) 대강 어떤 알고리즘인지 알았다면 문제를 보자 문제를 쓰윽 보면 키 순서대로 학생을 정렬하려고 하는데 모든 학생의 비교 결과가 아닌 일부의 비교 결과..

[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

우선 이 문제를 풀기위해서는 벨만-포드 알고리즘을 이해해야한다. 벨만-포드 단일시작점 알고리즘 (출발 노드가 고정) 최단 경로 알고리즘 음수 간선 가능 음수 사이클 확인 가능 쓱 보면 다익스트라와 비슷해보인다.(https://guccin.tistory.com/112?category=977502) 그러나 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선에 대해서 최단거리를 알아낼수 있다. 또한 다익스트라는 우선순위 큐를 활용하여 최단 경로를 구하는데에 반해 벨만-포드는 매번 모든 간선을 전부 확인하며 최단거리를 알아내기 때문에 다익스트라보다 시간복잡도가 크다. 다익스트라 O(|E||log|V|), 벨만-포드 O(|E||V|) [c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 ) ..

[python3] 백준 10844 풀이 ( 쉬운 계단 수, 다이나믹 프로그래밍, 이차 배열)

이번 문제 너무 어려웠다. 이것저것 해보다가 결국 해설을 봐버렸지만 그냥 외워서 체득시켜 놓아야 겠다. 솔직히 이거 못풀었다. 그래서 해설을 보고 이해하고 풀게 되었다. 처음에는 노가다로 갯수를 구해보았다. 9, 17, 32, 61까지 구했고 먼가 규칙이 있는듯 했지만 결과만으로는 규칙을 찾을 수 없었다. 그래서 끝자리를 배열에 넣어 개수를 확인하는 방식을 사용해보았다. 그러나 이렇게 풀면 시간초과가 났다. 알고보니 배열을 2차원 배열을 만들어 각 숫자별 개수를 저장하여 푸는 방법이 존재했다. 예를 들어 끝자리가 가능한 숫자는 0~9까지 이다. 따라서 이에 대한 배열을 만든다. 그리고 N=1일때 가능한경우에 1을 채워준다. 0은 시작부분에 나올수 없기 때문에 0이 되고 나머지는 가능하므로 1을 채울 수 ..

[c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 )

다익스트라 다익스트라는 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 단일 시작점 알고리즘에 속하여 시작점을 기준으로 각 노드까지의 최단 거리를 알 수 있다. 이때 시간 복잡도를 줄이기 위해 우선순위 큐를 활용하면 좋다. 음수 간선이 없을때 사용 (음수가 있으면 벨만-포드나 플로이드를 사용하는게 좋다) 우선순위 큐를 활용 단일 시작점 알고리즘 다익스트라 알고리즘은 BFS처럼 동작한다. 시작점에서부터 BFS탐색을 진행한다. 단, 우선순위 큐에서 노드를 뽑을때는 간선의 가중치가 가장 낮은 노드를 뽑는다.(우선순위 큐에 {-가중치,노드} 형태로 넣으면 된다.) 해당 노드와 접한 노드를 뽑아서 dp에 최단경로를 메모이제이션한다. 이후 최단경로 가중치를 노드와 함께 큐에 넣고 루프를 돌며 반복한다. 문..

[c++] 백준 1197 풀이 (MST, 최소 신장 트리, 그래프, 유니온 파인드)

이번에는 MST를 풀어보자. MST는 Minimum Spanning Tree의 약자로 span이란 기간을 의미해서 직역하면 최소화된 기간 트리이다. 좀 더 풀어 말하면 트리가 낮은 가중치로 연결되어 있다고 볼 수 있다. 다르게는 그래프의 최소 연결 부분 그래프 라고 할 수 있다. 이번 문제를 풀기 위해서는 MST를 알기 이전에 Spanning Tree에 대해서 이해해야한다. Spanning Tree 간선 수가 가장 작게 연결된다. 만약 정점이 V개라면 V-1개로 연결된 트리 사이클이 존재하지 않는다.(트리의 형태) Minimum Spanning Tree 값이 가장 작은 간선을 이용하여 만든 Spanning Tree 간선 가중치 합이 최소여야 한다. 사이클이 존재하지 않는다. 크루스칼 알고리즘과 프림알고리..

[c++] 백준 1717 풀이 (집합의 표현, 그래프, 서로소 집합, 유니온파인드)

서로서 집합은 상호 배타적 집합(Disjoint-set) 이라고 한다. 교집합이 공집합인 집합(서로소 집합) 들의 정보를 확인하고 조작할 수 있는 자료구조이다. - union : 두 노드를 한 그래프로 합친다. - find : 어떤 노드가 속한 집합을 반환 이 문제는 유니온 파인드를 이용하여 두 노드가 해당하는 집합을 합치거나 한 노드가 다른 노드의 집합에 속하는지 판별하는 문제이다. 따라서 union함수를 구현하고, find함수를 구현하여 풀이를 진행한다. 우선 find함수를 구현한다. find함수의 역할은 해당 노드의 부모로 탐색을 진행한다. 따라서 루트 노드를 만나는 경우 반환을 진행하며, 루트 노드가 아닌 경우에는 해당 노드의 부모에 루트 노드 값을 입력해준다. (즉 find과정을 통해 tree를..

[python3] 백준 1967 풀이 (트리의 지름, DFS)

이 문제는 그림을 보면 이해가 빨라진다. 우리는 각 노드를 쫙 잡아당겼을때 길이가 가장 길어지도록 하는 길이를 찾아야 한다. 만약 오른쪽 그림이 가장 길게 잡아당겨진 형태라고 가정한다. 그럼 오른쪽에 회색 노드들 중에서 아무거나 잡고 DFS를 통해 가장 먼 노드를 찾으면 그건 무조건 파란색 노드가 된다. 신기하게도 어떤 노드를 택하던 가장 먼 노드를 찾으면 그건 파란색 노드가 되는것이다. 진짜 신기하다. 그렇게 파란색 노드를 하나 찾고, 이번에 찾은 파란색 노드로부터 가장 먼 길이를 찾으면 우리가 찾고자하는 트리의 길이가 된다...... 그럼 DFS를 단 2번만 하면 해결되는 문제이다. 그럼 DFS할 때 각 길이만 저장하면서 확인하면 되는 것이다. 1. DFS(1)로 파란색 노드하나 찾기 2. DFS(B..

[python3] 백준 1937 풀이 (욕심쟁이 판다, DFS, DP)

어떤 문제이던 DP가 들어가면 난이가 확 올라가는것 같다. 이 문제는 처음에는 DFS로만 풀었다. 각 좌표별로 DFS를 실행했고 DFS에 시간복잡도에 N*N만큼 곱해져서 상당히 시간복잡도가 컸다. 그래서 시간초과가 났고 새로운 풀이를 찾아야 했다. 우선 고수들의 예시를 보자 위와 같이 대나무가 있다고 가정한다. 우리는 (0,0)부터 탐색을 시작한다. 그렇다면 자신보다 큰 값으로 최대한 이동할때의 DFS를 생각해본다. 그렇다면 DP배열은 아래와 같이 설정된다. 그러면 결국 DFS한번 만으로 각 좌표에서의 최대 일 수를 구할 수 있다. 그렇다면 DP가 계산되지 않은 (1,0)을 살펴본다. 그러면 이미 DP(0,0)은 최댓값을 가지고 있으므로 2의 값을 가져와서 1을 추가한다면 DFS없이 최대 일 수를 구할 ..