반응형 자바34 [Java] 힙(Heap) https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 위 문제를 풀면서 대학교 2학년 때 배웠던 힙이 기억이 안 나서 공부하게 되었다. 우선 힙(Heap)에 대해서 알아보자. 힙(Heap)이란? 힙은 '최소값 혹은 최댓값을 빠르게 찾기 위한 완전 이진트리 형태로 만들어진 자료구조'라고 정의할 수 있다. 우선 '이진 트리' 구조로는 힙을 구현할 수 없다. 힙의 중요한 모토는 최소 힙 - 부모 노드가 반드시 자식 노드보다 작아야 한다.. 2022. 11. 22. [Java/Python] 백준 1260번 - DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 혼자 힘으로 풀었는가? : X (내가 쓴 글 봤음) 알고리즘 유형 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종.. 2022. 11. 21. [Java/Python] 백준 1012 - 유기농 배추 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 혼자 힘으로 풀었는가? : O 알고리즘 유형 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 깊이 우선 탐색 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보.. 2022. 11. 19. [Python][이코테] 최단경로/ 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용 다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다. 노드의 개수가 N개일 때 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 \(O(N^2)\)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 총시간 복잡도는 \(O(N^3)\)이다. 다익스트라 알.. 2022. 11. 17. 이전 1 ··· 5 6 7 8 9 다음 반응형
