방구석 개발자의 실험실

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

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

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

[소프티어] 우물 안 개구리 자바 풀이 레벨3 단순구현  https://softeer.ai/practice/6289 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai   전체 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); ..

[소프티어] 출퇴근길 자바 풀이 레벨3 (HSAT 6회 정기 코딩 인증평가 기출)https://softeer.ai/practice/6248 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai     이 녀석은 새벽까지 날 못자게 한 녀석이다.설명도 찰떡같이 해둔분이 안계신거 같아서, 내가 각잡고 예쁘게 적어보고 싶었다. 문제 스펙        핵심 요약- 출근길과 퇴근길에 모두 포함되는 정점 구해야 함.- DFS와 역방향 간선 그래프를 이용해야 함.- 정방향 a출발 DFS 결과들 && 역방향 b출발 DFS 결과들 = "a-> b" 도달 가능한 경로를 의미함.  - 출근길 경로 a->b를 구하기 위해         정방향 a출발 DFS   (단, b도착시 움직이지 못하게 visit tru..