백준 9466번 링크Cycle을 찾는다는 점에서 그래프 문제처럼 생겼지만, 그래프 형태가 워낙 단순해서 스택 문제라고 생각해도 될 것 같다. 사실 DFS나 스택이나 뭐... 같은 방식이니 다른 분들과 다 비슷하게 푼 것 같다.각 vertex는 directed edge를

백준 9328번 링크조건이 많아서 BFS 문제처럼 생기긴 했는데 어떻게 풀어야 하나... 고민하다가 main queue, sub queue를 만드는 방식을 생각해냈다.Main queue는 일반적인 BFS에서 사용하는 queue다. Sub queue는 아직 열쇠가 없어서

백준 9252번 링크Longest common subsequence를 찾는 전형적인 DP 문제다. 점화식은 다음과 같다.$$DPi = \\begin{cases}DPi - 1 + 1 &\\text{if } stri == strj \\max(DPi - 1, DPi) &\\

백준 7579번 링크NP hard 문제이다. Optimization version의 정의는 다음과 같다.Input: Positive integers $$W, w{1}, ... , w{n}$$ and $$v{1}, ... , v{n}$$Output: A subset S

백준 2623번 음악프로그램순서를 정하는 문제에서 바로 topological sort라는 느낌이 왔다.Directed graph의 component 중 각 node로부터 다른 모든 node로 이동하는 경로가 있는 component를 SCC라 한다. Cycle이 있는 경

링크텍스트 값이 오름차순으로 들어오므로, 정렬은 필요가 없다. 정답이 가능한 경우를 생각해보자. 음수와 양수 값이 하나씩 있는 경우, 음수나 양수만 둘 있는 경우가 있다.입력에 음수나 양수 값만 있는 경우절대값이 가장 작은 두 값이 답이 된다.입력에 음수, 양수가

링크텍스트풀이 방법Topological sort를 이용한다. 각 학생을 vertex로 보고, 각 규칙을 directed edge로 볼 수 있다. 결과는 규칙을 만족하는 결과를 요구하므로, 모든 edge의 방향성을 만족하는 topological sort가 적절하다.Top

링크텍스트스도쿠가 주어지면 정답을 출력하는 프로그램을 작성해야 한다.정답이 여러가지라면 사전식으로 가장 앞서는 것을 출력한다.풀이 방법Brute force, backtracking 방식으로 푼다. 우선 값이 0인, 즉 채워야 하는 칸들의 좌표를 vector인 zeroC

링크텍스트외적을 이용하여 풀 수 있는 문제다. 점이 순서대로 주어지므로, 연속되는 두 점에 대한 외적값의 절반을 모두 더하면 된다.

https://www.acmicpc.net/problem/2098NP-hard로 알려진 문제다. 정의는 다음과 같다.Input: An nxn size matrixOutput: A cyclic permutation that minimizes $c(π) = \\s