Partially Committed

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 브루트포스로 문제를 해결하기에는 N 이 너무 큰 경우에 시간 초과가 발생할 수 있다. 이때 다양한 방법으로 최적화를 시도할 수 있겠지만, 분할정복처럼 N 을 절반씩 나눠서 연산한 다음에 결과를 합쳐서 문제를 푸는 것을 meet in the middle 알고리즘이라고 한다. 다만, 재귀적으로 반복해서 N/2, N/4 ... 1 처럼 계속 쪼개는 게 아니고 맨 처음에 1회만 반으로 쪼개는 것이다. 예..

(title: [백준 13549/1956/1620/2629] 자바) A. 숨바꼭질3 BOJ 13549 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도 Gold 5 풀이 시간 20 분 분류 다익스트라 / 0-1 BFS 시간복잡도 다익스트라 : O(nlogn) 0-1 BFS : O(V+E) = O(N+N) ~= O(N) 공간복잡도 일차원 그래프에서 다익스트라 알고리즘을 수행하여 쉽게 해결할 수 있다. 다익스..

(title: [백준 9251/1520/9370] 자바) A. LCS BOJ 9251 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 난이도 Gold 5 풀이 시간 10분 분류 DP 시간복잡도 O(NM) 공간복잡도 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws I..

(title: [백준 5568/2559/1504/11066] 자바) A. 카드놓기 BOJ 5568 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 난이도 Silver 4 풀이 시간 10 분 분류 백트래킹 시간복잡도 O(n^k * k * log n) 공간복잡도 import java.io.*; import java.util.*; public class Main { static int n; static int k; static TreeSet treeSet = new TreeSet(); static boolean [] visited; static..