밤이 블로그

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#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..

BOJ#1916 최소비용 구하기 * 문제https://www.acmicpc.net/problem/1916 * 풀이 다익스트라 알고리즘을 이용합니다. * 다익스트라 알고리즘 (Dijkstra algorithm) 1. 개요 : 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. : 다익스트라 알고리즘은 각각의 꼭짓점 v에 대해 s(시작점)에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 ..

BOJ#13422 도둑 * 문제https://www.acmicpc.net/problem/13422 * 풀이 푸는건 어렵지 않지만 시간 제한에 신경을 써서 구현해야 합니다. → O(nm)으로 구현 시 시간초과, 따라서 O(n)으로 해결을 해야 합니다. 시간 초과, 코드 길이, 푸는 속도 등에 초점을 맞춰 풀어보시면 좋을 것 같습니다. 풀이의 요점은 이전 Iteration에서 사용했던 sum에서 필요없는 값은 빼고, 더할 값만 더해서불필요한 연산을 하지 않는 것입니다. * 나의 코드https://github.com/stack07142/BOJ/tree/master/BOJ%2313422_Theif

BOJ#2156 포도주 시식 * 문제https://www.acmicpc.net/problem/2156 * 풀이동적계획법(Dynamic Programming)을 이용해봅시다. 일단 아래와 같이 배열을 선언합니다.dp[n] : n잔 째 마셨을 때, 최대로 마실 수 있는 포도주의 양p[n] : 포도주 n번 째 잔에 들어있는 포도주의 양 포도주는 3번 연속해서 마실 수 없으므로,n번 째 (마지막) 포도주는 3가지 경우로 나눌 수 있습니다.마시지 않는 경우, 1잔 째 마신 경우, 2잔 째 마신 경우 우리가 구하려는 dp[n]을 구해봅시다.1) 마지막 n번 째 포도주 잔 - 마시지 않는 경우 : n-1번 째 잔은 다시 1, 2, 3번의 경우로 나누어 질 수 있습니다. : dp[n] = dp[n-1] 2) 마지막 n..

BOJ#9465 스티커 * 문제 https://www.acmicpc.net/problem/9465 * 풀이 동적계획법(Dynamic Programming) 문제입니다. 최종적으로 점화식을 구해야 문제를 풀 수 있습니다. 0) 자료구조- 각 스티커의 점수를 저장하는 2차원 int 배열 : cost - 0열에서 출발하여 해당 위치까지의 점수의 합을 저장하는 2차원 int 배열 : dp 1) 시작점 생각하기0열에서 시작한다고 생각해봅시다. 시작점은 (0, 0), (0, 1)으로 2개가 됩니다. 2) 다음 스티커 선택하기(0, 0)에서 시작할 경우 (1, 1), (1, 2) 스티커를 선택할 수 있습니다. 그리고 (1, 1)과 (1, 2) 중에서 큰 값을 선택하면 됩니다. 한편, (0, 0)에서 (0, 2), (..

BOJ#10844 쉬운 계단 수 * 문제https://www.acmicpc.net/problem/10844 * 풀이동적계획법(Dynamic Programming)을 이용합니다.일단 점화식을 만들어야 하는데.. 저에게는 꽤 어려운 문제였습니다. dp[N] : 길이가 N인 계단 수의 개수 → 인접한 자리수의 차이가 1이라는 조건을 이용할 수 없으므로 아래와 같이 점화식을 구성합니다. dp[N][L] : 길이가 N이면서 마지막 수가 L인 계단 수의 개수 → 마지막 수가 L이므로 앞자리 수는 L-1, L+1이 될 수 있다. → dp[N][L] = dp[N-1][L-1] + dp[N-1][L+1] public class Main { // dp[N][L] : 길이가 L이고 마지막 수가 L인 계단 수 // dp[N]..

BOJ#11726 2xn 타일링 * 문제https://www.acmicpc.net/problem/11726 * 풀이동적계획법(Dynamic Programming)을 이용합니다. 2xN일 때, 아래와 같이 2개의 하위 문제로 나눌 수 있습니다. dp[N] = dp[N-1] + dp[N-2](dp[N] = 2xN 직사각형을 1x2, 2x1 타일로 채우는 방법의 수) static int go(int n) { if (n 0) { return dp[n]; } dp[n] = (go(n - 1) + go(n - 2)) % DIVISOR; return dp[n]; } * 나의 코드https://github.com/stack07142/BOJ/tree/master/B..

BOJ#1463 1로 만들기 * 문제 https://www.acmicpc.net/problem/1463 * 풀이 동적 계획법 (Dynamic Programming) 기초 문제입니다. * 동적 계획법 (Dynamic Programming) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. : 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종 목표를 구한다. : 하위 문제들의 해결책을 저장하여 이후 같은 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. * 메모이제이션 (Memoization) : 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 반복 계산을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. : 동적 계획법의 핵심이 되는..