devInfo

[백준 / Java] 1504번 : 특정한 최단 경로

문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지..

[백준 / Java] 17626번 Four Squares

문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 12으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 1252 + 62 + 12 + 12라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 1052 + 152 + 82 + 52. 자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오. 입력 입력은 ..

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍를 활용한 최단 경로(Shortest path) 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다익스트라 알고리즘이 다이나믹 프로그래밍을 활용하는 이유는 '최단 거리는 다양한 루트가 존재하기 때문'이다. 그렇기에 기존에 하나의 최단 거리를 구할 때 까지 모든 루트를 그대로 사용한다. 아래의 그래프에서 1에서 다른 정점으로 가는 최단 거리를 구한다고 해보자. 1에서 각 정점으로 한 번에 가는 최단 거리는 각 3, 6, 7이다. 이 때 한 번에 가는 것이 아닌 2를 거쳐 정점 3과 정점 4로 간다면 3 > 1과 3 > 1 >..

플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 문제들이 있다. 이 경우 플로이드 와샬 알고리즘을 사용하면 쉽게 모든 정점의 최단 거리를 구할 수 있다. 플로이드 와샬을 기본적으로 DP를 기반으로 진행된다. 플로이드 와샬 알고리즘의 주요 아이디어는 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 위 와 같은 그래프가 존재한다고 가정하자.이 때 각 정점에서 다른 정점으로 가는 비용을 이차원 배열로 정리하면 아래와 같다. 해당 테이블이 의미하는 바는 '현재까지의 최단 거리'이다. 해당 테이블을 통해 지나치는 정점으로 다른 정점으로 가는 테이블을 그릴 것이다. 1. 노드 1을 거쳐가는 경우 노드 1을 거쳐가는 경우는 노드 2와 노드 3이다. 이를 테이블로 나타내면 아래와 같다..

[Java] 자바 TreeMap 사용법 & 예제

1. TreeMap이란? TreeMap은 이진트리를 기반으로 한 Map 컬렉션입니다. 같은 Tree구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장한다면 TreeMap은 키와 값이 저장된 Map, Etnry를 저장한다는 점입니다. TreeMap에 객체를 저장하면 자동으로 정렬되는데, 키는 저장과 동시에 자동 오름차순으로 정렬되고 숫자 타입일 경우에는 값으로, 문자열 타입일 경우에는 유니코드로 정렬합니다. 정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키값이 높은 것은 오른쪽 자식 노드에 Map.Etnry 객체를 저장합니다. TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어집니다. TreeMap은 데이터를 저장할 때 즉시 정..

[Java] Queue를 ArrayList가 아닌 LinkedList로 구현해야 하는 이유

ArrayList와 LinkedList 의 차이점 1. ArrayList ArrayList는 중복을 허용하고 순서를 유지하며 인덱스로 원소들을 관리한다는 점에서 배열과 상당히 유사합니다. 배열은 크기가 지정되면 고정되지만 ArrayList는 클래스이기 때문에 배열을 추가, 삭제 할 수 있는 메소드들도 존재합니다. 하지만 추가했을 때 배열이 동적으로 늘어나는 것이 아니라 용량이 꽉 찼을 경우 더 큰 용량의 배열을 만들어 옮기는 작업을 하게 됩니다. 2. LinkedList LinkedList는 내부적으로 양방향의 연결 리스트로 구성되어 있어서 참조하려는 원소에 따라 처음부터 순방향으로 또는 역순으로 순회할 수 있습니다. (배열의 단점을 보완하기 위해서 링크드 리스트(Linked list)라는 자료구조가 고..