방구석 개발자의 실험실

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

[소프티어] 택배 마스터 광우 자바 풀이 dfs 쉽게 접근하기   https://softeer.ai/practice/6273 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai    언어별 시간/메모리언어시간메모리JavaScript2초256MBC2초256MBC++2초256MBJava2초256MBPython2초256MB여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원 했다. 광우는 평소에 운동을 하지않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.레일은 N개이며, 각각의 레일은 Ni 무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순..

https://softeer.ai/practice/7727 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 생각이 한번 꼬여서 은근 애먹었는데,이해하고나면 아? 생각보다 쉽네? 였다.       핵심 설명변수 네이밍 규칙이 Worker와 Work로 하다보니 헷갈려서 바꿨다Worker와 Gold로 바꾸고 일꾼이 골드를 수확한다고 생각하니 편했다. 각설하고,맵 저장해주고~여느때와 다름없이 dfs를 구현해준다. for(int i=0; i= map.length || ny >= map[0].length ){ continue; // 맵 벗어난 경우 } if(v[nx][ny] != 0){ ..

[소프티어] 순서대로 방문하기 자바 풀이 DFS 백트래킹 (HSAT 7회 정기 코딩 인증평가 기출) 잊을만 하면 찾아오는 소프티어.이젠 일상인 것 같다. 문제보자.https://softeer.ai/practice/6246 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai  백트래킹(Backtracking) 개념백트래킹은 문제 해결을 위한 알고리즘적 기법 중 하나로, 모든 가능한 경우의 수를 탐색하여 정답을 찾는 방법입니다. 백트래킹은 재귀적으로 탐색을 진행하면서, 해당 경로가 유효하지 않다면 이전 단계로 돌아가 다른 경로를 시도하는 방식입니다. 쉽게 말해, 탐색 중에 조건을 만족하지 않는 경로가 발견되면 그 즉시 탐색을 중단하고, 다른 가능한 경로를 찾는 전략입니다.   핵심 설명첫번..

[소프티어] 출퇴근길 자바 풀이 레벨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..

[소프티어] 장애물 인식 프로그램 dfs 자바 풀이    반타작..?    dfs의 전형적인 문제전체 코드에 주석부분을 참고하자.import java.io.*;import java.util.*;public class Main { public static int wallCnt = 0; public static List wallSum = new ArrayList(); public static int m[][]; public static int curSum; public static Integer n; public static void main(String[] args) throws IOException { BufferedReader br = new Buff..