방구석 개발자의 실험실

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

[백준] 17266 어두운 굴다리 자바 풀이 이진탐색 (제출시 7%에서 틀린다면)    얼마전 소프티어에서 풀었던 녀석과 해결방법이 거의 동일하니아래의 문제도 풀어보시면 좋을 것 같습니다. 2024.08.28 - [알고리즘 단련장/소프티어] - [소프티어] 슈퍼컴퓨터 클러스터 자바 풀이 이진탐색 시간초과 해결 (HSAT 4회 정기 코딩 인증평가 기출)       문제링크https://www.acmicpc.net/problem/17266      문제인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙빙 돌아서 집으로 간다. 안타깝게 여긴 인식이는 굴다리 모든 길 0~N을 밝히..

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점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 ..

[소프티어] 슈퍼컴퓨터 클러스터 자바 풀이 이진탐색 시간초과 해결 (HSAT 4회 정기 코딩 인증평가 기출)https://softeer.ai/practice/6252 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai        언어별 시간/메모리언어시간메모리JavaScript5초1024MBC3초1024MBC++3초1024MBJava5초1024MBPython5초1024MB대규모 머신 러닝에서는 여러 컴퓨터를 하나의 클러스터로 묶어 계산을 수행하는 경우가 많다. 병렬 컴퓨팅 파워가 늘어나면 훨씬 더 거대한 데이터도 실용적으로 사용할 수 있게 된다. 클라우드 컴퓨팅을 이용하는 기업도 많지만, 개인정보와 보안, 네트워킹, 비용 등의 문제로 직접 클러스터를 구축하는 경우도 많다.현지도 이러한..

https://softeer.ai/practice/6251 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 언어별 시간/메모리언어시간메모리JavaScript1초256MBC1초256MBC++1초256MBJava1초256MBPython1초256MB어떤 부서의 업무 조직은 완전이진트리 모양이다. 즉, 부서장이 루트이고 부서장 포함 각 직원은 왼쪽과 오른쪽의 부하 직원을 가진다. 부하 직원이 없는 직원을 말단 직원이라고 부른다. 모든 말단 직원은 부서장까지 올라가는 거리가 동일하다. 조직도 트리의 높이는 H이다. 아래는 높이가 1이고 업무가 3개인 조직도를 보여준다.  업무는 R일 동안 진행된다. 처음에 말단 직원들만 각각 K개의 순서가 정해진 업무를 가지고 있다. 각 업무는 업무 번호가 ..