반응형 알고리즘120 [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. [Python/Java] 백준 17626번 - Four Squares https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 혼자 힘으로 풀었는가? : X 구글에 검색해봄(문제가 이해되지 않았음) 알고리즘 유형 - 다이나믹 프로그래밍 - 브루트포스 알고리즘 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할.. 2022. 11. 16. [Python][이코테] 최단경로 / 다익스트라 알고리즘(2) 2022.11.09 - [Algorithm/이것이 코딩테스트다] - [Python][이코테] 최단경로 / 다익스트라 알고리즘(1) 개선된 다익스트라 알고리즘 기존의 간단한 다익스트라 알고리즘은 시간 복잡도가 \(O(V^2)\) 이다. 이번에 공부할 개선된 다익스트라 알고리즘은 \(O(ElogV)\)를 보장한다. (E = 간선의 개수, V = 노드의 개수) 간단한 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해 매번 최단 거리 테이블을 선형적으로 탐색했다. 이 과정에서만 \(O(V)\)의 시간이 걸렸다. 하지만 개선된 알고리즘은 힙(Heap) 자료구조를 사용한다. 힙 자료구조를 사용하면 특정노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 가장 짧은 노드를 더욱 빠르게 찾을 수 .. 2022. 11. 15. 이전 1 ··· 22 23 24 25 26 27 28 ··· 30 다음 반응형
