GaeunLee blog

무게 제한이 걸려있는 가방에 가치를 최대로 하게끔 물건을 넣는 방법을 알아보자! 대표 문제: 12865 평범한 배낭 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 가치를 최대로 하는 문제이니, dp에 가치를 저장해서 해결한다. Value(i,w)란 i번째 물건까지, w무게만큼 골랐을 때 최대가치를 말한다고 가정한다. (단, i는 물건의 index, w는 현재 가방에 담겨있는 무..

가중치 그래프의 두 정점 사이의 거리 중 가장 최단거리는 어떻게 찾을 수 있을까? 이 문제를 해결하기 위해서는 모든 시작점으로부터의 최단 경로 정보가 필요하다. 그렇다면 다익스트라 알고리즘을 v번 호출하면 풀 수 있다. https://0923ulee.tistory.com/entry/%EB%8B%A8%EC%9D%BC-%EC%8B%9C%EC%9E%91%EC%A0%90-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C 단일 시작점 최단 경로 알고리즘 (다익스트라, 벨만 포드) 가..

가중치 그래프에서 시작 정점 s에서 다른 정점들 사이의 최단 경로를 구해보자! 일단, 시작 정점 s에서 어떤 정점 v사이의 거리를 배열(distance[v])로 나타내 보자. 그러면 distance[s] = 0이라고 표현할 수 있다. *최단 경로를 구하기 위한 완화 작업(Relax)이란?* 시작 정점 s에서 v로 가는 경로에서, 간선 u->v를 사용하는 것이 이득인지 판단하는 검사이다. 즉, 시작 정점 s에서 v로 가는 기존 경로와 시작 정점 s에서 정점 u를 지나 v로 가는 경로 중 더 짧은 거리를 선택한다는 의미이다. (더 짧아지는 경우 갱신한다.) distance[v] = min(distance[v], distance[u] + weight(u->v)) //u를 거치는 방법으로 갱신이 일어난 경우 "..

백준 17626 www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 1. 주어진 수와 같거나 작은 가장 큰 제곱수를 우선으로 그리디하게 풀면 틀린다. 더 작은 경우가 존재 ex) 11339 = 106^2 + 10^2 + 1^2 + 1^2 + 1^2 (5 : 오답) 11339 = 105^2 + 17^2 + 5^2 (3 : 정답) 2. dp를 이용해 min을 갱신하면서 찾는다. dp[n] = 합이 n이 되는 제곱수의 개수라고 하자..

백준 20047 www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 손가락으로 짚은 두 동전을 편의상 Fcoin이라고 하자. 1. 문자열 S(Fcoin을 제외), T의 인덱스를 증가시키면서 비교하고, 달라지는 경우에 T와 Fcoin을 비교했다. 그럴 경우 반례가 생긴다. -> 문자열 S(Fcoin을 제외)에서 비교할 문자와 와 Fcoin이 같은 경우 어떤 경우로 체크해줘야 하는지 고려하지 않았다. 3 xxo xox 0 2 ans : ..