문제 링크 Gold 4 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net https://mag1c.tistory.com/452 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, mag1c.tistory.com 풀이 방향..
다익스트라(Dijkstra) 알고리즘 그래프의 최단 경로를 구하는 알고리즘으로 하나의 정점에서 출발하여 최단 거리를 구하는 알고리즘이다. 탐욕법(Greedy)과 동적 계획법을 사용하는 알고리즘으로, 음의 가중치(음의 값)가 없어야한다. 음의 가중치가 존재하게 되면, 최소 비용의 음의 무한대값이 생성될 수 있으며 그리디 알고리즘을 적용할 수 없다. 인접 행렬로 표현된 그래프의 경우 O(n^2)의 복잡도를 가지며, 우선순위 큐를 사용하여 시간복잡도를 O(m logn)까지 낮출 수 있다. 매커니즘 (1) 방문하지 않은 노드 중 가장 비용이 적은 노드를 선택한다 (그리디) (2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다 (DP) 예시 https://mag1c.tistory.com/451 [백준 19..
문제 링크 Gold 5 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 첫 풀이 단순 BFS로 구해보려했던 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { private static int N; private st..
문제 링크 Silver 1 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 문제의 조건은 선택한 스티커의 상하좌우 스티커는 선택할 수 없다. 라고 하였다. 아래 문제 예시를 보자. 50 10 100 20 40 30 50 70 10 60 위의 예시에서, dp를 사용하여 최대값을 어떻게 구할 수 있을까 왼쪽부터 시작해서, 하나씩 선택해보았다. 50 10 30 50 50 10 30 50 첫 번째 idx의 값을 선택할 수 있다. 두 번..
문제 링크 Silver 1 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 문제에서 N은 N-1과 N+1과 색상을 중복해서는 안된다. 라고 하는 부분에서 조금 헷갈렸는데 결론은 크게 신경쓰지 않아도 된다. N일 때 N-1에서 중복만 체크한다면 어떤 상황에서도 중복이 될 일은 없다. for (int i = 0; i < N; i ++) { st = new StringTokenizer(br.readLine(), " "); ..
문제 링크 Silver 3 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 풀이 문제 티어는 낮지만 DP문제라서 냉큼 공부 처음에는 아래처럼 해당 idx의 제곱값을 구하여 greedy처럼 풀어내려고 했으나 int[] arr = new int[(int) Math.sqrt(n) + 1]; for (int i = 0; i < arr.length; i ++) { arr[i] = i * i; } 모든 상황에 만족하지 ..
문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 자기 전에 문제 하나 풀고 자야지~~ 하면서 풀었던 문제 실버 3 문제라 DP로의 접근은 쉬웠으나, 뜻하지 않게 ArrayIndexOutOfBounds Exception으로 고생했음.. 반 졸린 상태에서 풀어서~~ 라고 핑계를 대보지만. 실수를 줄이기 위해 항상 신경써야겠다고 다짐한 문제로. 상기시키기 위해 포스팅.... import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; publi..
Count Ways To Build Good Strings - LeetCode Can you solve this real interview question? Count Ways To Build Good Strings - Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following: * Append the char leetcode.com 풀이 DP배열을 생성해, Bottom Up방식으로 풀이. dp[0]=1이 왜 1인가에 대해 고민을 좀 많이 했던 문제였다. 문자열의 길이가 0인게 없지..