전체 글

전체 글

    [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] 프로그래머스 (다리를 지나는 트럭) Level 2
    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..

    [java] 프로그래머스 (주식가격) Level 2
    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..

    [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] 프로그래머스 (124 나라의 숫자) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (124 나라의 숫자) Level 2

    Problem : https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr Approach ​ 1. 124 나라에는 자연수만 존재합니다. ​ 2. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. ​ 3. n은 500,000,000이하의 자연수이다. 10진법 124 나라 10진법 124 나라 1 1 6 14 2 2 7 21 3 4 8 22 4 11 9 24 5 12 10 41 그럼 3으로 나눴을 때, 나머지가 1이면 1의 자리수가 1, 2이면 2, 0이면 4인 것이 보일 것이다.위의 표를 보아 예상하기를 11:42, 12:44, 13:111, 14:112,..

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

    [java] 백준 11054 (가장 긴 바이토닉 부분 수열) Gold 3
    Algorithm/Baekjoon Online Judge

    [java] 백준 11054 (가장 긴 바이토닉 부분 수열) Gold 3

    문제 원문 링크 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net Approach 바이토닉 수열 : 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족하는 수열이다. LIS(Longest Increasing Subsequence)를 응용한 문제이다. 앞에서부터 LIS의 길이를 구하여 저장하고, 뒤에서부터 LIS의 길이를 구하여 저장한 후, 같은 위치에 있는 두 저장한 값을 더하여 가장 큰..

    [java] 백준 2156 (포도주 시식) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 2156 (포도주 시식) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net Approach DP로 풀 수 있는 문제이다. ​ 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. ​ 2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. ​ 3. 최대로 많이 마시게끔 포도주를 마셔야 한다. 놓여있는 마지막 잔을 마실 경우, ​ 1. ~ X O O 로 마시는 경우가 있다...

티스토리툴바