본문 바로가기

자료구조3

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.
11401번 - 이항 계수 3 출처: 백준 알고리즘 주소: www.acmicpc.net/problem/11401 문제요약: -> 이항계수 (N, K)을 1,000,000,007으로 나눈 나머지에 대해 출력 해결방법: 1) 이항계수 (N, K)을 구해서 1,000,000,007으로 나눈다. => 제일 간단한 방법이지만, N값이 크면 이항계수 (N, K)의 값을 저장할 방법이 없다. 2) "페르마의 소정리"을 이용해서 값을 구한다. => ap-1 ≡ 1 (mod p) {단, p: 소수, a: 정수} 소스코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 .. 2021. 3. 1.

티스토리툴바