[java] 백준 11066 (파일 합치기) Gold 3

Problem : https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net Approach DP를 이용한 문제로, DP[i][j] = i ~ j까지의 파일을 합치는 최소 비용 이라고 정의하고 문제에 접근한다. 주어진 파일의 개수가 1개라면, 그 파일의 크기를 return 한다. 주어진 파일의 개수가 2개라면, 두 개의 파일 크기를 합친 값을 return 한다. 주어진 파일의 개수가 3개 이상이라면, DP[i][j] = DP[i][k] + DP[..

→2020.12.27

Algorithm/Baekjoon Online Judge

[java] 백준 1655 (가운데를 말해요) Gold 2

Problem : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net Approach 최대 힙과 최소 힙 두개를 사용하여 문제를 풀 수 있다. 최대 힙은 최댓값이 우선으로 빠져나오는 큐이고, 최소 힙은 최솟값이 우선으로 빠져나오는 큐라고 할 때, 최대 힙과 최소 힙에 하나씩 숫자를 넣는다고 가정햇을 때, 최대 힙의 최댓값이 최소 힙의 최솟값보다 항상 작음을 유지한다면, 최대 힙의 최댓값이 항상 중간값을 가지게 된다. 그러기 위해선 ..

→2020.12.27

Algorithm/Programmers

[java] 프로그래머스 (삼각 달팽이) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr Approach 월간 코드 챌린지 시즌1 에 수록된 문제이다. 정삼각형의 위쪽 꼭짓점부터 반시계방향으로 외곽부터 순회하면서(토네이도 식으로) 번호를 매기고, 그것을 1차원 배열로 변환하여 리턴하는 문제이다. 정삼각형의 한 변의 길이가 n이고, 번호를 1부터 매긴다고 하면, 마지막 번호는 n + (n - 1) + (n - 2) + ... + 1 = n(..

→2020.12.25

Algorithm/Baekjoon Online Judge

[java] 백준 11286 (절댓값 힙) Silver 1

Problem : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Approach PriorityQueue를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. 절댓값이 가장 작은 값을 출력하려면 PriorityQue..

→2020.12.25

Algorithm/Baekjoon Online Judge

[java] 백준 11279 (최대 힙) Silver 2

Problem : https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net Approach PriorityQueue를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. 하지만 가장 큰 값이 나와야 하므로 별도의 설정이 필요하다..

→2020.12.25

Algorithm/Baekjoon Online Judge

[java] 백준 1927 (최소 힙) Silver 1

Problem : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Approach 우선순위 큐(PriorityQueue)를 이용하여 풀 수 있는 문제이다. JAVA에서 기본적으로 PriorityQueue는 default값으로 오름차순, 즉 Integer큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. Code import java.io.*; i..

→2020.12.25

Algorithm/Baekjoon Online Judge

[java] 백준 2749 (피보나치 수 3) Gold 2

Problem : https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net Approach 유명한 피보나치 수열의 n번째 수를 구하는 문제이다. 하지만 n이 1,000,000,000,000,000,000 이하의 숫자이므로 오랜시간이 걸릴 것이다. 따라서 아래와 같이 피보나치의 행렬적 규칙을 이용하여 계산하여야 한다. (long 자료형을 사용하여) 아래 규칙만 알고 있다면 O(log n)의 행렬제곱 문제와 똑같다. [ Fn ] = [ 1 1 ] * [ Fn-1 ] = [ 1 1 ] * [ 1 1 ] * [ Fn-2 ] [ Fn-1 ] ..

→2020.12.25

Algorithm/Programmers

[java] 프로그래머스 (다리를 지나는 트럭) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42583 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr Approach 다음은 길이가 2이고, 10kg 무게를 견디는 다리, 무게가 [7, 4, 5, 6]kg인 트럭일 때의 과정이다. 경과 시간 다리를 지난 트럭 다리를 건너는 트럭 대기 트럭 0 [] [] [7,4,5,6] 1~2 [] [7] [4,5,6] 3 [7] [4] [5,6] 4 [7] [4,5] [6] 5 [7,4] [5..

→2020.12.25

Algorithm/Programmers

[java] 프로그래머스 (주식가격) Level 2

Problem : https://programmers.co.kr/learn/courses/30/lessons/42584 코딩테스트 연습 - 주식가격 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00 programmers.co.kr Approach 아래는 문제의 입출력 예이다. prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 큐를 이용한 간단한 문제이다. Queue에 prices를 모두 넣은 후, 하나씩 빼내면서 Iterator를 이용한 순회를 한다. 큐 순회 중에 가격이 낮아진다면 바로 break..

→2020.12.25

Algorithm/Baekjoon Online Judge

[java] 백준 10830 (행렬 제곱) Gold 4

Problem : https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach 같은 행렬 요소를 여러번 곱하는 문제이므로, 분할 정복을 이용하여 풀 수 있다. 행렬 제곱은 다음과 같이 분할 할 수 있다. 행렬 A의 9제곱을 구한다고 가정했을 때, A^9 = (A^4 * A^4) * A = ((A^2 * A^2) * (A^2 * A^2)) * A 이 된다. 알고리즘 자체는 O(logN)이지만, 행렬 곱셈 자체는 O(N^3)이다. 구현부는 코드와 코드 주석을..

→2020.12.24

티스토리툴바