BOJ

    [java] 백준 11066 (파일 합치기) Gold 3
    Algorithm/Baekjoon Online Judge

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

    [java] 백준 1655 (가운데를 말해요) Gold 2
    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 최대 힙과 최소 힙 두개를 사용하여 문제를 풀 수 있다. 최대 힙은 최댓값이 우선으로 빠져나오는 큐이고, 최소 힙은 최솟값이 우선으로 빠져나오는 큐라고 할 때, 최대 힙과 최소 힙에 하나씩 숫자를 넣는다고 가정햇을 때, 최대 힙의 최댓값이 최소 힙의 최솟값보다 항상 작음을 유지한다면, 최대 힙의 최댓값이 항상 중간값을 가지게 된다. 그러기 위해선 ..

    [java] 백준 11286 (절댓값 힙) Silver 1
    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..

    [java] 백준 11279 (최대 힙) Silver 2
    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큐일 경우 숫자가 작을수록 우선순위가 높다. 따라서 별다른 설정없이 우선순위 큐에 넣었다 뺀다면 자동적으로 가장 작은 값이 나온다. 하지만 가장 큰 값이 나와야 하므로 별도의 설정이 필요하다..

    [java] 백준 1927 (최소 힙) Silver 1
    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..

    [java] 백준 2749 (피보나치 수 3) Gold 2
    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 ] ..

    [java] 백준 10830 (행렬 제곱) Gold 4
    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)이다. 구현부는 코드와 코드 주석을..

    [java] 백준 12865 (평범한 배낭) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 12865 (평범한 배낭) Gold 5

    Problem : https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net Approach 대표적인 DP 문제인 KnapSack Problem이다. DP[i][j] 는 j만큼의 무게를 견딜 수 있는 가방에 처음 i개의 물건들로 담을 수 있는 최대 가치를 말한다. - i번째 물건의 무게 weight 가 현재 넣을 수 있는 무게 j보다 크다면 DP[i][j] = DP[i - 1][j]이다. ..

    [java] 백준 9251 (LCS) Gold 5
    Algorithm/Baekjoon Online Judge

    [java] 백준 9251 (LCS) Gold 5

    Problem : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net Approach LCS(Longest Common Subsequence) 문제로 DP로 풀이가 가능한 문제이다. 배열은 DP[s1.length + 1][s2.length + 1] 으로 선언하여 두 문자열을 각각 한 문자씩 비교해 나간다. DP[i][j] 는 s1.charAt(i)와 s2.charAt(j)를 비교한 후, 그 때까지의 LC..

    [java] 백준 2565 (전깃줄) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2565 (전깃줄) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net Approach 언뜻 보기에 어려워 보이는 문제이지만, LIS로 간단히 풀리는 문제이다. 일단 왼쪽 기둥을 기준으로 입력을 정렬시킨다. 그런 후, LIS의 길이를 DP배열에 저장한다. 그림에서의 DP배열의 요소는 {1, 1, 0, 2, 0, 3, 4, 1, 2, 5} 이다. 이 문제에서 LIS는 줄이 겹치지 않고 오른쪽기둥 기준 오름차순으로 연결돼 있는 줄의 개수이다. Code imp..

티스토리툴바