이숭간 공부기록

www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제유형 : 그래프, DFS/BFS 문제풀이 : 그래프에서 연결된 리스트 (덩어리)의 개수를 찾는문제이므로 DFS/BFS를 통해 그래프를 탐색한다. dfs함수는 시작노드에서부터 연결된 노드들로 재귀적으로 호출되며 더이상 방문할 노드가 없을때 리턴된다. 따라서 전체 노드를 순회하며 아직 방문 전일때, 해당 노드를 시작노드로 하여 DFS함수를 실행하면 ..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제유형 : BFS 문제풀이 주어진 2차원배열을 graph에 저장한다. 초기상태에서 1인 위치를 큐에넣고, BFS를 통해 인접노드들을 확인하며 0인경우(익지않은 토마토)일때만 1로 바꿔준다. 인접노드는 상하좌우로 움직인 4가지 노드이며, 조건을 통해 그래프 범위를 벗어나지 않도록 체크한다. 여기서는 -1일때는 어차피 아무것도 할수없으므로 신경쓰지 않아도 되고, 0인경우에는 1로 바꿈과 동시에 방..

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제유형 : 우선순위큐, 자료구조 문제 풀이 neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj7662/ [백준/파이썬] 7662번 이중 우선순위 큐 풀이 파이썬을 이용한 백준 온라인저지 문제풀이 neomindstd.github.io 처음에 우선순위 큐 하나를 두고(최소힙), 최소값삭제는 최소힙그대로 빼고, 최대값 삭제일때는 최소힙의 모든 원소에 접..

출처 : gmlwjd9405.github.io/2018/05/10/data-structure-heap.html를 참고하여 작성하였습니다. " 우선순위 큐를 위해 만들어진 자료구조 " (우선순위 큐가 뭔데요? 우선순위의 개념을 큐에 도입한 자료구조로서, 우선순위가 높은 데이터가 큐에서 먼저 나가게 된다.) 1. 힙이란? 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조 여러개의 값중 최댓값이나 최솟값을 빠르게 찾아내도록 고안됨 부모노드의 키값이 자식노드의 키값보다 항상 크거나(혹은 작은) 이진트리이다. 힙 트리에서는 중복된 값을 허용한다. 2. 힙의 종류 최대힙 (Max Heap) key(부모) >= key(자식) 숫자로 생각하면 큐에서 나가는 순서가 내림차순이 되는것이다. 최소힙 (Min H..

모든노드에서 다른 모든노드까지의 최단경로를 계산한다. 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드중 최단거리를 갖는 노드를 찾는 과정이 필요없다. 2차원 테이블에 최단거리 정보를 저장한다. DP유형에 속한다. 플로이드 워셜 알고리즘 노드의 개수가 많은경우에는 플로이드워셜보다 다익스트라를 사용하는것이 좋다. 시간복잡도는 O(n^3)임 행은 출발노드, 열은 도착노드를 의미함. k값만 바꿔가면서 모든a,b를 반복하며 전부 확인해주면 된다. k = 1일때(1번노드를 거치는) 모든 a,b에 대해서 확인하고 갱신한다. 소스코드 import sys input = sys.stdin.readline INF = int(1e9) n = int(input..