밤이 블로그

BOJ#1699 제곱수의 합 * 문제https://www.acmicpc.net/problem/1699 * 풀이Dynamic Programming 문제입니다. 주의할 점으로,Greedy 하게 풀면 안됩니다. 반례로 12의 경우를 생각해보시면 되겠습니다.ex) 12 = 3^2 + 1^2 + 1^2 + 1^2 (4) = 2^2 + 2^2 + 2^2 (3) 따라서 동적계획법을 이용하면서 완전 탐색을 해주시면 됩니다. - 비슷한 문제 https://www.acmicpc.net/problem/1463 * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%231699_SumOfSquares

BOJ#11055 가장 큰 증가 부분 수열 * 문제https://www.acmicpc.net/problem/11055 * 풀이 BOJ#11053 문제와는 조금 다른 문제입니다.11053 문제는 '증가하는 부분 수열' 중 가장 긴 수열의 길이를 구하는 것이었고,11055 문제는 '증가하는 부분 수열' 중 수열의 합이 가장 큰 것을 구하는 것입니다. 즉, 가장 긴 수열이 항상 가장 큰 합을 보장하지 않으므로dp를 11053 문제와는 다르게 설계하셔야 합니다. 11053의 dp[i]가 'A[i]를 포함하는 수열 중에, 길이가 가장 긴 수열의 길이' 였다면,11055의 dp[i]는 'A[i]를 포함하는 수열 중에, 수열의 합이 가장 큰 수열의 합' * 나의 코드https://github.com/stack0714..

BOJ#11053 가장 긴 증가하는 부분 수열(LIS) * 문제https://www.acmicpc.net/problem/11053 * 풀이 유명한 문제인 Longest Increasing Subsequence (LIS)입니다.O(N^2) 방법과 O(N logN) 방법으로 풀어보았습니다. 기존에 워낙 설명이 잘 되어있어서 따로 포스팅 하지는 않겠습니다만,제가 공부할 때 참고했던 사이트 남겨드립니다. 1. LIS 이해 및 O(N^2) 풀이https://www.youtube.com/watch?v=CE2b_-XfVDk 위 동영상을 보시고 아래 저의 코드를 보시면 되겠습니다. * 나의 코드 // O(N^2) for (int i = 1; i < N; i++) { for (int j = 0; j < i; j++) {..

BOJ#13418 학교 탐방하기 * 문제https://www.acmicpc.net/problem/13418 * 풀이앞서 살펴봤던 최소 스패닝 트리 문제입니다. 1197번과 같은 기본 문제이고,(http://stack07142.tistory.com/53)크루스칼 알고리즘을 이용했습니다. 어려운 문제는 아닙니다만, 최소/최대 둘 다 구해야 하므로애초에 우선순위 큐를 2개 만들어서, 오름차순/내림차순으로 정렬할 수 있도록 했습니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%2313418_SchoolTour

최소 스패닝 트리Prim(프림), Kruskal(크루스칼) 알고리즘+ Union-Find 자료구조 * 개요 - 신장 트리(스패닝 트리, Spanning Tree)란?1. 그래프의 모든 정점이 간선으로 연결되어 있다.2. 그래프 안에 사이클이 포함되어 있지 않다. - 최소 신장 트리(최소 스패닝 트리, Minimum Spanning Tree)란?말그대로 최소 비용으로 만들어진 신장 트리. 가중치의 합이 가장 작은 신장 트리 - 프림과 크루스칼 알고리즘은 최소 스패닝 트리를 구하는 방법 중 하나이다.- 둘 다 Greedy Method을 기초로 하고 있다. (당장 눈앞의 최소 비용의 선택을 해서 결과적으로 최적의 Solution을 찾는다.) - 프림은 정점 위주의 알고리즘, 크루스칼은 간선 위주의 알고리즘이다..

BOJ#1197 최소 스패닝 트리 * 문제https://www.acmicpc.net/problem/1197 * 풀이 - MST(최소 스패닝 트리), 프림, 크루스칼 알고리즘, Union-Find 자료구조 설명http://stack07142.tistory.com/54 - MST (Minimum Spanning Tree)를 구하는 방법으로 아래 2가지 알고리즘이 있습니다.1) Prim's Algorithm, 프림2) Kruskal Algorithm, 크루스칼 1197번 문제를 위 2가지 알고리즘으로 풀어보았습니다. 1. Prim's Algorithm, 프림메모리 : 18848 KB, 시간 : 1244 MS import java.io.BufferedReader; import java.io.BufferedWri..

http://stack07142.tistory.com/39 * 동적 계획법 (Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. : 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목표를 구한다. : 하위 문제들의 해결책을 저장하여 이후 같은 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. * 메모이제이션 (Memoization) : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 계산을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. : 동적 계획법의 핵심이 되는 기술이다. (예제) 피보나치 수열 보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.function fib(n) i..

Dijkstra 다익스트라 알고리즘 (우선순위 큐를 사용하지 않는) http://stack07142.tistory.com/47 * 다익스트라 알고리즘 (Dijkstra algorithm) 1. 개요 : 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. : 다익스트라 알고리즘은 각각의 꼭짓점 v에 대해 s(시작점)에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존..

BOJ#13415 정렬 게임 * 문제https://www.acmicpc.net/problem/13415 * 풀이시간 제한 때문에 생각할게 많은 문제입니다.주어진 정렬 Order를 모두 수행하는 경우 시간 초과가 발생하기 때문입니다. 알고리즘 #1. 필요 없는 정렬 Order는 무시한다.ex)104 1 5 2 3 10 8 11 15 663 24 55 43 22 13 1 오름차순을 (+), 내림차순을 (-)라고 했을 때,+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 에서+3 → -2 → +4 → -5 → +5 → -4 → +3 → -2 → +2 → -1 → +3 → -1 회색 음영은 수행하지 않아도 되므로결국 +5 → -4 → +3 → -1 으로 줄일..

BOJ#13414 수강신청 * 문제https://www.acmicpc.net/problem/13414 * 풀이시간초과에 유의하여 풀어야 합니다. 1. 자료구조 선택입력되는 값의 순서를 유지해야 한다. → Linked중간 중간 중복되는 값을 검사해야 하므로 검색이 빨라야 한다. 규모가 커질 수록 검색에 유리한 → Hash 따라서 LinkedHashSet을 이용한다. 2. 입출력 시간 최소화입력 : Scanner 대신 BufferedReader를 이용출력 : System.out.println 대신 BufferedWriter를 이용하자. 또는 Stringbuilder에 내용을 담았다가 System.out.println에 한번에 출력 3. Collections에 접근할 때는 Iterator를 이용하며,Itera..