sori's Tstory

https://www.acmicpc.net/problem/15681알고리즘 재활을 하는 중이므로, BFS,DFS 등을 제외한 다른 알고리즘은 기억이 잘 나지 않았다. 그래도 빡구현으로 호기롭게 풀어보려다, 반례를 찾아버려서 다시 풀어야 하는 암울한 상황이다. 그래도 반성문이라도 적어보고자 오답 노트를 써본다.문제에 대한 간단 한 설명은 아래와 같다.트리의 정보가 주어지고, 서브 트리의 루트 노드 번호가 주어지면, 해당 서브 트리의 총 노드 갯수를 구하는 비교적 간단한 문제이다.따라서 우선 나는 벡터로 트리의 정보를 저장하고, 루트 노드에서 부터 탐색을 하다가, 해당 서브트리의 루트 노드 번호를 만나면, 거기서부터 그래프 탐색으로 갯수를 세려고 했다.#include#include#include#includ..

https://www.acmicpc.net/problem/14430 map이 주어지면 오른쪽 또는 아래쪽으로만 이동하여 주울 수 있는 자원의 최대치를 구하는 문제이다. 개인적으로 이동할수 있는 경우가 정해져있다는 점에서 숨바꼭질 문제와 비슷하다고 느꼈다.이 문제에서는 오른쪽 또는 아래쪽으로만 탐색을 해야하므로, 그래프 전체를 돌아다닐수 없고, 여러가지 경우의 수를 탐색 해 최적의 경로를 구해야 한다는 점에서 DP 문제 일것이다. 라고 느꼈다.우선 여느 DP 와 다를 것 없이 기존의 map 을 보존해야하므로  최대 자원 수를 구하는 이차원 DP와 원래 주어진 map, 2가지 이차원 배열을 선언 해야한다.처음에는 탐색 조건을 아래와 같이 설정했다. for (int i = 0; i 그러나 위와 같이 탐색을 하..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬까진 어떻게 했지만 작업의 최솟값을 찾지 못했다. 처음에는 루트노드(가장 마지막 작업)을 시작으로 time배열에 더해 나가려고 했지만, 자식 노드의 형제 노드들까지 time을 더해 버리는 바람에 총 시간 이 나와버렸다. 문제에서 주어진 "서로 선행 관계가 없는 작업들은 동시에 수행 가능하다."라는 말은 사실 형제 노드들중 최댓값을 고르라는 말과 같다. (최솟값이 아닌 최댓값인 이유..

오늘은 배낭 문제 알고리즘에 대해 알아보도록 하자 배낭 문제는 각 물건에는 가치와 무게가 존재하고, 내가 들 수 있는 정해져있을 때 최대한 많은 가치의 합을 찾는 문제이다. 쉽게 말해, 도둑 알고리즘이라고 기억하면 편하다. 이 배낭 알고리즘은 대표적인 다이나믹 프로그래밍 문제 중 하나로, 1. 배낭 문제는 배낭 내 물건을 쪼갤 수 있는(일부만 선택하는) Fraction Knaspack Problem 과 2. 물건을 쪼갤 수 없는 (가져가거나 안 가져가거나)0-1 knapSack Problem으로 나눌 수있다. 이 때, 결국 모든 경우의 수를 확인해야 하므로 현재 배낭 내 물건의 최대가치와, 현재 무게 합을 고려해야하므로 2차원 배열에 담아야 한다 우선은 더 쉬운 0-1 knapSack Problem을 먼..