문제 링크 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 - 이진탐색 (매개변수 탐색) 으로 풀이하면 되는 문제 - 시간 복잡도는 O(NlogN) 범위 지정시 (L, R) L 의 경우 100,000개의 강의(N)를 100,000 개의 블루레이(M)에 담는다 할 때 (각 강의 길이 또한 최대 10,000분) 최소 10,000분이 되야함. 10,000분 이하는 담을 수가 없기 때문에, 최소 10,000분이 기준이 됨 L 은 고로 주어진 배열에서 가..

문제 링크https://www.acmicpc.net/problem/1300 1300번: K번째 수세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 Bwww.acmicpc.net2차원 배열을 1차원으로 이렇게 구할 수도 있다니 또 하나 배운다 :) 풀이 - N (최대 10만), K (10만 ~ 10억)- N * N 2차원 배열을, 1차원 배열로 변환 후 정렬했을 때 K번째 있는 임의 수를 구하는 문제 - N이 최대 10만이기 때문에 1차원 배열로 변환시 10^10 = 100억이 되어서 메모리 초과, 시간 초과 발생 가능 아래와 같은 연산..

문제 링크 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이진탐색 (매개변수 탐색) 풀이하면 되는 문제 문제 지문 K개 랜선이 있을때 필요한 랜선 N개를 만들기 위한 최대 랜선 길이 H를 구하시오. 뒤집은 지문 (매개변수 탐색*) 임의 길이 H로 랜선을 K개를 자를때, 필요한 랜선 N개를 만들 수 있는가? 이때 최대 랜선 길이 H는 얼마인가? 시간 복잡도 O(NlogN) 최대값 랜선의 길이 최대값이 2^31 ..

문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 매개변수 (paramatrix search) 탐색 문제 (그리디 포함) 문제 지문 C 개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리(Dmax) 를 구하시오. 뒤집은 지문 두 공유기 사이의 거리 (D)를 라 할때, C개의 공유기를 설치 가능한가(yes/no)? 이때 설치 가능한 최대 거리(Dm..

문제 링크 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 반복문을 통해 left = 1 ~ N 까지 조회할 때 - arr[left + 1 ... N] 사이에 값들 중 -arr[left] 이상이면서 가장 왼쪽에 있는 값을 찾아야 함 - N 이 최대 10만일때 O(N^2) = 10^10 시간초과 발생가능 - 이진탐색으로 풀이시 O(NlogN) 시간 복잡도 가짐 투 포인터로 풀 경우 좀 더 쉽게 풀이 가능 주..

문제 링크 https://www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들 www.acmicpc.net 풀이 - 첫째줄에 점 N개가 주어지고, 다음 라인 부터 N개만큼 "위치 색깔" 형태로 입력이 주어짐 - 같은 색깔에 p와 q점에 대해 직선 화살표로 연결하려 할 때, 가장 가까운 거리의 점이여야 함 (만약 가까운 점이 두 개 이상이면 둘중 아무거나 선택) - 모든 점에 대해 같은 색깔을 가진 다른 점이 항상 존재 ( 2

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 - 길이가 N인 계단 수를 구하는 문제 (45656 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라 부름) - '이때 0으로 시작하는 수는 계단수가 아니다' 는 조건이 있음 점화식 - 2차원 DP배열에서 i, j 에 의미 부여 후 점화식 세워 문제 풀이하는 방법을 따라함 - 직접 했을 때는 식을 못 찾고, 설명을 찾아보고 다시 그렸을 때야 이해가 되었음 DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1] - 이때 DP[i][j] 에서 i는 자릿수(길이), j는 끝 숫자..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 - bottom-up 방식으로 품 // SUCCESS const input = require('fs').readFileSync('/dev/stdin').toString().split('\n'); const n = Number(input[0]); const dp = new Array(n+1).fill(0); for(let i = 2; i

동적 프로그래밍 (DP, Dynamic Programming) - 통산적으로 메모리를 더 사용하여 시간 복잡도 개선할 때 많이 사용됨 - DP로 문제를 해결하기 위해 '점화식'을 찾는 것이 핵심 과정 동적 프로그래밍은 아래의 두 조건을 만족할 때 사용가능하다 1. 최적 부분 구조(optimal substructure) 큰 문제를 유사한 형태의 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결한다. 2. 반복되는 부분 문제(overlapping sub-problem) 동일한 작은 문제를 반복적으로 해결해야 한다. 점화식 - 인접한 항으로 현재 값을 결정하는 관계식을 의미함 - 점화식은 "재귀 함수"로 표현가능 예) 파보나치 수열 점화식 An = (An-1) + (An-2) (이때 초기값..