JAVA - 백준 [BAEK JOON]/동적 계획법 1
[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]
[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]
2021.01.05www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 문제가 어려운 편은 아니다. 주어진 조건에 따라 함수를 그대로 옮겨적고 메모이제이션만 추가하면 된다. 알고리즘 [접근 방법] 문제를 설명하기는 모호한데.. 일단 동적계획법의 특징은 대체로 재귀 + Memoization(메모이제이션) 이라는 것을 생각하면 된다. 위에서 설명한 조건에 따른 함수(재귀)호출은 코드로 보면 이렇다. static int w(int a, int b, int c) { if(a 20) { ..
[백준] 12865번 : 평범한 배낭 - JAVA [자바]
[백준] 12865번 : 평범한 배낭 - JAVA [자바]
2020.09.17www.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 문제 알고리즘 [접근 방법] 이 문제는 배낭 문제(knapsack)로 매우 유명한 문제다. 문제 설명처럼 배낭에 넣을 수 있는 최댓값이 정해지고 해당 한도 물건을 넣어 가치의 합이 최대가 되도록 고르는 방법을 찾는 것이다. 즉, 조합 최적화 문제다. 배낭문제, 일명 냅색 알고리즘은 크게 두 가지 문제로 분류 될 수 있는데, 짐을 쪼갤 수 있는 경..
[백준] 1912번 : 연속합 - JAVA [자바]
[백준] 1912번 : 연속합 - JAVA [자바]
2020.09.10www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 이 문제는 너무 쉬운 문제라.. 메모이제이션하면서 구간만 잘 찾아내면 끝인 문제다. 알고리즘 [접근 방법] 꽤나 쉬운 문제임에도 정답 비율이 꽤나 낮은 문제다. 아마 '연속 되는 수를 선택'해야 한다는 조건을 놓치거나 음수를 빼버리는 경우? 이렇게 접근해서 틀린 분들이 많지 않을까 싶다. 문제 예제들을 그대로 적용해보면 이렇다. 첫 번째 예제는 아래와 같다. (배열로 표현함) 여기서 연속된 수를 선택하여 뽑아내면 다..
[백준] 9251번 : LCS - JAVA [자바]
[백준] 9251번 : LCS - JAVA [자바]
2020.09.08www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS의 대표적인 문제다. 알고리즘 [접근 방법] 우리가 그동안 LIS, LDS, 바이토닉 부분수열까지 풀어봤다. 이 번에는 LCS인데, LCS의 정의 자체는 매우 간단하다. 위키피디아에서 보면 매우 잘 정리되어있으니 읽어보시는 것도 좋을 것 같다. ko.wikipedia.org/wiki/최장_공통_부분_수열 최장 공통 부분 수열 - 위키백과, 우리 모두의 백과..
[백준] 2565번 : 전깃줄 - JAVA [자바]
[백준] 2565번 : 전깃줄 - JAVA [자바]
2020.09.04www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 역발상을 하면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 문제 접근 방식부터 알아보자. 먼저 문제에서는 서로 교차되지 않도록 하기 위해 철거되어야 할 전선의 최소 개수를 구하는 것이다. 하지만 그렇게 구하기에는 교차 여부를 확인해야 하기에 불편하다. 그렇다면 역으로 생각해보자. 철거되어야 할 전선의 최소 개수라 하면, 거꾸로 전체 전선의 개수에서 최대한 겹치지 않게 설치 가능한 개수를 구하여 빼면, 즉 (..
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]
2020.09.04www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 이전 문제인 가장 긴 증가하는 부분 수열을 풀어보셨다면 매우 쉽게 풀 수 있는 문제다. 이 문제를 풀기 전에 앞서 아래 포스팅을 보고 오는 걸 추천드린다. st-lab.tistory.com/137 [백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바] www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하..
[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]
[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]
2020.09.02www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net (제목이 꽤 길다...) 문제 이전 포도주 시식 또는 계단오르기 문제를 해결했다면 오히려 쉽게 접근 할 수 있는 문제다. 알고리즘 [접근 방법] 앞서 말했듯 포도주 시식, 계단오르기 같은 문제랑 같은 계열의 문제다. 보통 이런 문제를 최장 증가 부분 수열(LIS)라고 한다. 말 그대로 주어진 수열에서 오름차순으로 구성 가능한 원소들을..
[백준] 2156번 : 포도주 시식 - JAVA [자바]
[백준] 2156번 : 포도주 시식 - JAVA [자바]
2020.08.31www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 만약 백준 카테고리에서 동적계획법을 차례대로 풀어왔다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 아마 동적계획법1 카테고리 문제를 차례대로 풀어왔다면 2579번 문제인 '계단 오르기'랑 매우 유사하다는 것을 느끼셨을 것이다. 이 문제를 풀기에 앞서 혹여 기억이 안나거나 아직 풀어보지 못한 분은 계단 오르기 문제를 보고 오시는 것을 추천드린다. 필자도 이에 대해 포스팅 했으니 아래 포스팅을 참고하시면..
[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]
[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]
2020.08.29www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 저번 문제인 1로 만들기보다 쉬운 편이다. 몇가지 규칙만 알면 되니 한 번 같이 알아보도록 하자. 알고리즘 [접근 방법] 문제를 설명하기 전에 자릿수 개념에 대해 헷갈려 하는 분들이 있어 먼저 한 번 정리하려고 한다. 그래야 필자가 설명하기도 편할 듯 하다. N번째 자릿수라 하면 보통 길이가 N인 자연수에서 가장 왼쪽에 있는 수가 N번째 자리가 N번째가 된다. 만약 123456이라는 수가 있다고 하면 6번째 자릿수 자릿값은 1, 5번째 자릿수의 자릿값은 2, ⋯ , 첫번째 자릿수의 자릿값은 6이 된다. 소수의 경우 왼쪽..
[백준] 1463번 : 1로 만들기 - JAVA [자바]
[백준] 1463번 : 1로 만들기 - JAVA [자바]
2020.08.28www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 알고리즘 [접근 방법] 생각보다 어렵지 않게 풀 수 있는 문제다. 이번 문제는 재귀로 풀이해볼 것이다. 크게 세 가지 경우의 수로 나눌 수 있는데, 3으로 나누는 경우, 2로 나누는 경우, 1을 빼는 경우가 있다. 여기서 1로 만들기 위한 최소 연산 횟수를 찾아내야 한다. 여기서 함정이 하나 있다. "무조건 큰 수로 나눈다고 해결되진 않는다." 위 이미지의 힌트에서 볼 수 있듯이 10을 큰 수부터 나눠보기 시작하면 10 -> 5 -> 4 -> 2 -> 1 이렇게 4번의 연산이 필요하다. 하지만 정답은 10 -> 9 ->..