1. 배낭 문제 개요 n개의 물건이 존재하고, 각 물건 i의 무게는 $w_{i}$, 가치가 $v_{i}$로 주어진다. 배낭의 용량이 W라고 할때, 이러한 배낭에 담을 수 있는 물건의 최대 가치는? 단, 배낭에 담은 물건의 무게 합은 W를 초과할 수 없고 각각의 물건은 1개씩만 존재한다 그리고 물건을 쪼개서 담을 수 없다고 가정한다. 이러한 문제는 0-1 knapsack 문제라 부르고 물건을 쪼개서 담을 수 있는 경우도 물론 있는데 fractional knapsack 문제라고 부른다. 2. 해법 - 완전탐색 조금 생각해보면, 존재하는 물건들의 집합 S에서, 일부를 골라 가방에 담는 문제이므로, 집합 S에서 모든 부분집합을 구하고, 가치들의 합을 조사한다 이때, 가방의 용량을 넘지 않으면 가치의 합을 구하고..
1. 문제 1952. [모의 SW 역량테스트] 수영장 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1일 이용권, 1달 이용권, 3달 이용권, 1년 이용권을 사용하여 주어진 1월~12월까지 수영장 이용 계획을 최소 비용으로 이용하고 싶을때, 그러한 최소 비용을 찾는 문제 2. 풀이 다이나믹 프로그래밍을 연습할 수 있는 아주 좋은 문제다 dp[i]를 1~i번째 달까지 사용한 최소 요금으로 정의하자 각각의 i번째 달에 사용할 수 있는 경우의 수는 무엇일까? 1) 1일 이용권을 모두 사용하는 경우 예를 들어 3월에 2일 사용했는데, 2일을 1일 이용권 2번으로 사용할 수 있다 2) ..
1. 문제 1249. [S/W 문제해결 응용] 4일차 - 보급로 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2차원 배열에서 (0,0)에서 (n-1,n-1)로 가는데, 경로에 쓰이는 숫자들의 합이 최소가 되도록 갈때, 그 최솟값을 구하는 문제 2. 풀이 2차원 배열에서도 다익스트라 알고리즘을 사용할 수 있을까? 그대로 사용하면 된다 2차원 배열을 하나의 그래프로 바꿀려고 시도한 적이 있었는데 그럴 필요도 없다 다익스트라 알고리즘이 distance 배열을 무한으로 초기화하고, 출발 위치는 0으로 시작한 다음에 현재 위치에서 인접한 곳으로 이동을 해보고, 거리가 최소가 되면 di..
1. 문제 2382 [모의sw역량테스트] 미생물격리 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 조건에 맞게 이동하는 미생물들이 존재하는 배열에서 특정 시간 이후에 남아있는 미생물의 수를 구하는 문제 2. 풀이1 기본적으로 sw 역량테스트는 문제에서 제시하는 조건대로 성실하게 구현하면 답은 낼 수 있다 일단 문제에서 말하는대로 직관적인 시뮬레이션을 수행해보자 먼저 n*n 배열에 미생물을 그대로 배치하고 싶다 그리고 가장자리는 1로 채워줘야한다. n-2개의 0이 들어간 리스트 좌우 양쪽에 1을 붙인 n-2개의 행을 준비하고, 0행과 n-1행은 1이 n개 채워진 배열을 위 아래로..
1. 문제 4012. [모의 SW역량테스트] 요리사 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com N개의 식재료를 N/2개씩 나누어 2개의 요리를 하려고 한다. 각 요리의 맛은 음식을 구성하는 식재료들의 시너지의 합으로 구해진다. 음식의 맛의 차이가 최소가 되는 경우를 찾는다면? 2. 풀이1 순열과 조합을 이용하는 문제가 될텐데 실전 문제에까지 직접 구현해서 사용할 이유는 전혀 없고 from itertools import combinations, permutations를 이용하자 처음에 풀때는 2개의 재료에 대해서는 설명이 명확한데 3개의 재료에 대해서는 시너지를 어떻게 계산하..
1. 문제 1953. 모의 sw 역량테스트 탈주범 검거 SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 탈주범이 시작 위치에서 터널을 통해 이동할 때, 일정 시간 후에 탈주범이 존재할 수 있는 곳의 개수를 구하는 문제 2. 풀이 어쨌든 성실하게 하나하나 구현하면 되는 문제 전형적인 BFS이지만 이동할 수 있는 조건이 복잡하고 까다로워서 실수할 수도 있는 문제 1) map의 범위를 벗어나는 곳은 이동 불가능 2) map에서 0인 곳은 이동할 수 없다 3) 주어진 터널 방향으로만 이동 가능하다 map에서 1번은 4방향으로 이동 가능하고, 2번은 상,하, 3번은 좌,우,..... 7번..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
