Python3 [백준] 7578번 : 공장 (Python) 문제https://www.acmicpc.net/problem/7578문제 요약 A 열에 위치한 기계, B 열에 위치한 기계의 식별번호가 주어진다.각 기계는 유일한 식별번호를 가지며, A 열의 특정 식별번호를 가진 기계는 B 열에 반드시 존재한다. (짝을 이룬다)A열, B열의 기계들에 대해, 식별번호가 같은 기계끼리 모두 연결했을 때 발생하는 교차하는 선 쌍의 개수를 찾는 문제이다.(중요) 교차점 을 구하는 문제가 아니다! (선 N개가 한 점에서 교차하는 경우를 생각하지 않아도 된다.)문제에서 체크할 것들입력값의 특성 기계의 개수 $N$ : $1 \leq N \leq 500,000$→ $O(NlogN)$ 알고리즘으로 해결해야 하구나! ($O( N^{2} )$ 알고리즘으로는 불가)기계의 식별번호 $K$ .. 2026. 1. 17. [백준] 7579번 : 앱 (Python) https://www.acmicpc.net/problem/7579 7579번: 앱입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활www.acmicpc.net문제입력 / 출력풀이 과정이 문제가 왜 배낭 문제인지 전혀 알지 못해서 해답을 봤습니다.항상 이런 해답은 보고 나서야 깨닫는 것 같네요. 해답을 보지 않았다면 평생 못풀었을 수도...이 문제를 배낭 문제 풀이 형식으로 바꾸면 쉽게 해결됩니다.생각의 방향을 고친다면 풀이는 자연스럽게 이해됩니다.풀이 이해가 되지 않는다면 평범한 배낭 문제부터 이해하셔야 합니다!2023.05.01 - [분류 전체보기] - [Pyt.. 2023. 5. 2. [백준] 12865번 : 평범한 배낭 (Python) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net문제입력 / 출력전통적인 0-1 Knapsack 문제입니다.오늘은 이 배낭문제를 완벽하게 파헤치겠습니다. 풀이 과정DP 문제가 늘 그렇듯 DP값을 정의하는 것이 가장 중요합니다.DP[N][K] = N번째 물건까지 담았을 때 용량이 K인 가방의 최대 가치N번째 status는, N-1번째 status만 보고 도출할 수 있다는 것입니다. 그렇.. 2023. 5. 1. 이전 1 다음
