방구석 개발자의 실험실

[알고리즘] Knapsack(배낭) 알고리즘 (그리디 및 dp) FKP KP 총정리 # Knapsack# 냅색 알고리즘# FKP# KP# 배낭문제# 분할가능 배낭문제# 0-1 배낭문제# 다중 배낭문제 워낙 유명하디 유명해서리 컴공이라면 한번쯤은 들어봤을 녀석입니다. 바로 채득해보겠습니다.      1.   Knapsack 알고리즘이란?배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정한 가치의 무게가 정해진 짐들을 배낭에 담을 때, 가치의 합이 최대가 되는 조합을 찾는 알고리즘입니다.대충 배낭에 비싼거 마구마구 담으라는 의미가 되겠습니다  대표적인 문제 유형에는 3가지가 있습니다.FKP : Fractional Knapsack Problem (분할가능 배낭 문제)말 그대로 물건을 쪼갤 수 있는 배낭 ..

https://www.acmicpc.net/problem/2193      문제0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력첫째 줄에 N자리 이친수의 개수를 ..

[백준] 11659 구간 합 구하기 4 자바 풀이 DP https://www.acmicpc.net/problem/11659  문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.출력총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.제한1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N예제 입력 1 복사5 35 4 3 2 11 32 45 5예제 출력 1 복사1291출처문제를 만든 사람: baekjoo..

[백준] 11722 가장 긴 감소하는 부분 수열 자바 풀이 DP  본 문제에선 숫자가 감소하지만 반대로 생각하면 증가이기 때문에 LIS문제입니다최장 증가 부분수열 (LIS, Longest Increasing Subsequence).  저번에 풀었던 LCS도 참고하시면 좋을 것 같습니다2024.08.22 - [알고리즘 단련장/백준] - [백준] 9251 LCS 최장 공통 부분수열 자바 풀이 DP [백준] 9251 LCS 최장 공통 부분수열 자바 풀이 DPhttps://www.acmicpc.net/problem/9251  왜 그때 당시에는 생각이 나지 않았을까. 싶은DP의 기본중의 기본 문제.안해보면 낯설지만, 한번 만나면 익숙한 녀석. 시작해보자.  스펙은 이렇다.       문snapcode.tistor..

[백준] 9095 1,2,3 더하기 자바 풀이 DP 런타임 에러 해결 https://www.acmicpc.net/problem/9095  문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.출력각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.예제 입력 1 복사34710예제 출력 1 복사744274출처I..

https://www.acmicpc.net/problem/1463  문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.예제 입력 1 복사2예제 출력 1 복사1예제 입력 2 복사10예제 출력 2 복사3힌트10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.출처문제를 번역한 사람: baekjoon문제의 오타를 찾은 사람: c..

https://www.acmicpc.net/problem/2579     계단 오르기 성공 문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 ..

[소프티어] 통근버스 출발 순서 검증하기 자바 풀이 dp DP (HSAT 4회 정기 코딩 인증평가 기출)  https://softeer.ai/practice/6257 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai  언어별 시간/메모리언어시간메모리JavaScript2초1024MBC1초1024MBC++1초1024MBJava2초1024MBPython2초1024MB현대자동차그룹 연구소에서는 임직원들의 편의를 위해 출퇴근 통근 버스를 제공하고 있다.퇴근 시간이 되면 연구소 주차장에는 수 많은 버스들이 일렬로 주차되어 있다. 퇴근 버스는 번호순서 대로 출발해야 하는데, 주차장은 폭이 좁아 앞의 버스가 모두 나가야 뒤의 버스가 나갈 수 있는 구조로 되어 있다. 버스를 순서에 맞게 출발시키기 위..

https://www.acmicpc.net/problem/9251  왜 그때 당시에는 생각이 나지 않았을까. 싶은DP의 기본중의 기본 문제.안해보면 낯설지만, 한번 만나면 익숙한 녀석. 시작해보자.  스펙은 이렇다.       문제LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.입력첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.출력첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.예제 입력 1 복사ACAYKPCAPCAK예제 출..

DP란?- 동적 프로그래밍(DP)은 알고리즘 문제 해결에 매우 중요한 기법 중 하나     추천 DP 문제들 1003번: 피보나치 함수문제 설명: 피보나치 함수의 호출 횟수를 계산하는 문제로, 기본적인 DP를 이해하고 연습하기 좋음 1463번: 1로 만들기문제 설명: 주어진 정수를 1로 만드는 최소 연산 횟수를 찾는 문제로, DP를 통해 최적의 방법을 찾는 연습을 할 수 있음 2098번: 외판원 순회문제 설명: 외판원 문제로, 모든 도시를 방문하여 처음 도시에 돌아오는 최단 경로를 찾는 문제임. 비트마스크 DP를 활용하는 문제로 도전해볼 만함.11053번: 가장 긴 증가하는 부분 수열문제 설명: 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 문제임. DP를 활용하여 최적의 부분 수열을 찾는 ..