기록방

👉 문제링크 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔸 문제 분석 🔸 피보나치 수열을 구현하는데 n이 1,000,000,000,000,000,000 으로 매우 큰 수가 주어진다. 🔸 문제 풀이 🔸 피보나치 수열을 구현하는데 반복문, 재귀, 동적 계획법을 사용할 수 있지만, 매우 큰 n에 대해서는 분할 정복을 이용한 거듭제곱을 이용해야한다. 행렬 곱셈을 이용한다. n번째 피보나치수는 (n/2-1)번째 피보나치 수[k1]와 (n/2)번째 피보나치 수[k2], (n/2+1)번째 피보나치 수[k3], (n/2+2)번째 피보나치 수[k4]로 나타낼 수 있다. EX ) 0, 1, 1, 2,..

👉 문제링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 🔸 문제 분석 🔸 N개의 수로 이루어진 수열이 있다. 두 수를 묶어서 곱셈 연산을 할 수 있고, 나머지는 합연산으로 계산한다. 계산 결과의 최대값을 출력한다. 🔸 문제 풀이 🔸 곱셈 연산으로 최대값을 만들어야 하므로 그리디 알고리즘으로 풀이한다. 수열을 정렬 후, 1보다 큰 수 중에서 크기가 큰 수를 우선으로 짝을 지어 곱셈 연산을 진행한다. 수가 1 미만인 수들은 음수끼리 만나 양수가 되거나, 0과 합쳐져 음수가 지워지므로 짝을 짓는다. 🔸 코드..

👉 문제링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 🔸 문제 분석 🔸 카드 묶음들을 합칠때 최소 비교 횟수를 출력한다. 🔸 문제 풀이 🔸 작은 묶음부터 합쳐야 최소값이 나오는걸 문제에서 확인할 수 있으므로, 그리디 알고리즘으로 접근해 우선순위 큐를 이용하여 풀이한다. 두 최소값 원소를 뽑아 그 합을 정답에 누적하고, 다시 그 합을 우선순위 큐에 넣는다. 우선순위 큐의 원소가 1개가 남을 때 까지 반복한다. 합으로 만들어진 새 묶음이 기존 묶음보다 클 수 있음에 유의한다. 🔸 코드 🔸 i..

👉 문제링크 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 🔸 문제 분석 🔸 N x N 인 배열 A가 있고, A[i][j] = ixj 이다. 일차원 배열 B에 A를 넣고 오름차순 정렬했을 때, B[k]를 구한다. 배열 인덱스는 1부터 시작한다. 🔸 문제 풀이 🔸 배열 A의 원소들 중 중앙값 보다 작은 수들의 개수를 세며 이진 탐색을 통해 풀이한다. 중앙값 보다 작은 수들이 K보다 작다면, 시작 인덱스를 중앙값 +1 로 변경한다. 중앙값보다 작은 수들이 K이상이라면, 마지막 인덱..

👉 문제링크 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 🔸 문제 분석 🔸 N개의 영상을 M개의 블루레이에 나눠 저장하려고 한다. 하나의 블루레이 크기의 최소값을 구한다. 🔸 문제 풀이 🔸 블루레이 크기를 이진 탐색으로 찾는다. 최소 크기는 N개의 영상 중 최대값 최대 크기는 N개의 영상의 총합 중앙값을 시작으로 M개의 블루레이에 모두 저장할 수 있으면 크기를 줄여보고, 모두 저장할 수 없으면 저장 크기를 늘려보는 식으로 탐색한다. 🔸 코드 🔸 import java.io.*; import java.util.Str..