Algorithm

    [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 로 마시는 경우가 있다...

    [java] 백준 10844 (쉬운 계단 수) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 10844 (쉬운 계단 수) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach DP로 풀 수 있는 문제이다. 문제 풀이에 앞서, 밑의 조건을 알고 가면 편하다. ​ 1. 0으로 시작하는 N자리 수는 없다. ​ 2. 1자리 수는 모두 계단수이다. ​ 3. DP에 저장할 때에 1,000,000,000으로 나눈 나머지를 저장해야 한다. N자리 수를 봤을 때, 10의 자리 수가 0이면 1의 자리 수가 1이어야 한다. 10의 자리 수가 1~8이면 1의 자리 수는 10의 자리 수의 +1한 수 이거나 -1한 수 여야만 한다. 10의 자리수가 9이면 1의 자리 수는 ..

    [java] 백준 1932 (정수 삼각형) Silver 1
    Algorithm/Baekjoon Online Judge

    [java] 백준 1932 (정수 삼각형) Silver 1

    문제 원문 링크 : https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net Approach DP 문제이다. 문제에서는 이등변 삼각형처럼 보이지만, 실제로는 정사각형 배열의 반만 쓰면 된다. 크기가 N인 정수 삼각형이고, i는 위에서부터 층의 높이, j는 삼각형의 열일 때, ​ DP[i][j] = DP[i - 1][0] (j == 0) ​ DP[i][j] = DP[i - 1][j - 1] (j == N) ​ DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] (j == 1...N-1) 위의 식을 도출..

    [java] 프로그래머스 (기능개발) Level 2
    Algorithm/Programmers

    [java] 프로그래머스 (기능개발) Level 2

    문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr Approach 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. progresses speeds return [93, 30, ..

    [java] 백준 2580 (스도쿠) Gold 4
    Algorithm/Baekjoon Online Judge

    [java] 백준 2580 (스도쿠) Gold 4

    문제 원문 링크 : https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net Approach 이 문제 또한 대표적인 BruteForce, Backtracking 문제이다. N-Queens 문제와 접근법은 동일하다. 놓을 수 있는지 없는지 검사 후, 다음 단계로 넘어가며, 놓을 수 없다면 다시 뒤로 돌아가 똑같이 다음 수를 검사하는 것이다. 나는 1차원 배열을 사용하였으며, 배열에서 i번째 요소는 N x N 행렬에서 (i / N)행 (i % N)열이다. ..

티스토리툴바