백준10 1753번 - 최단경로 출처: 백준 알고리즘 주소: https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제 요약: (1) 방향 그래프와 시작 정점이 주어진다. (2) 시작 정점에서 모든 정점에 대한 최단경로를 계산하고 출력한다. 문제 해결(파이썬): A. 입력 B. 다익스트라 알고리즘 구현 C. 출력 - 시작 지점 = 0 - 시작 정점에서 갈 수 있는 정점 = 최소 거리 - 시작 정점에서 갈 수 없는 정점 = INF 미리 공부할 내용: 1. .. 2021. 7. 1. 1260번 - DFS와 BFS 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 요약: (1) 입력으로 정점의 개수(N), 간선의 개수(M), 탐색을 시작할 정점의 번호(V)를 제공 => (각 입력의 범위는 N: 1 ~ 1000, M: 1 ~ 10000, V: 1 ~ N 이다.) (2) 이후 M개의 간선을 입력으로 제공한다. (3) 입력으로 제공된 정보를 이용하여 DFS을 수행한 결과 출력 (4) 또한, BFS를 수행한.. 2021. 4. 9. 1655번 - 가운데를 말해요 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 요약: (1) N개의 숫자가 차례대로 입력 (2) 1 ~ N개 들어온 숫자들의 중간값 출력 문제 해결: A. 중간값 설정 B. 중간값보다 작은 경우, MaxHeap에 저장 C. 중간값보다 크거나 같은 경우, MinHeap에 저장 D. MaxHeap과 MinHeap의 크기의 차이를 1이하로 유지 미리 공부할 내용: => heap에 대해 공부하기 위해 아래 블로그 .. 2021. 4. 8. 11286번 - 절댓값 힙 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 요약: (1) 절댓값이 작은 힙 클래스 생성 => 힙의 최대 크기(N): 100000, 힙에 저장되는 정수 범위: -231 ~ 231 (2) 0이 아닌 정수를 입력 받으면 힙에 입력 (3) 0을 입력으로 받으면 절댓값이 가장 작은 값 출력하고 그 값을 힙에서 제거 => 만일 절댓값이 가장 작은 값이 여러 개인 경우, 그 중에 제일 작은 값 하나만 출력하고 .. 2021. 4. 6. 1927번 - 최소 힙 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 요약: (1) 최소 힙 클래스 생성 => 힙의 최대 크기(N): 100000, 힙에 저장되는 자연수의 범위: 1 ~ 231 - 1 (2) x값이 0이면 힙에서 가장 작은 값을 출력하고, 그 값을 힙에서 제거 (3) x값이 자연수이면 힙에 삽입 문제 해결: A. 최소 힙 클래스 정의 B. 최소 힙 클래스 내의 삽입 함수 생성 C. 최소 힙 클래스 내의 최소 값.. 2021. 4. 5. 이전 1 2 다음
