백준
1.백준 2098번 외판원 순회
https://www.acmicpc.net/problem/2098NP-hard로 알려진 문제다. 정의는 다음과 같다.Input: An nxn size matrixOutput: A cyclic permutation that minimizes $c(π) = \\s
2.백준 2166번 다각형의 면적
링크텍스트외적을 이용하여 풀 수 있는 문제다. 점이 순서대로 주어지므로, 연속되는 두 점에 대한 외적값의 절반을 모두 더하면 된다.
3.백준 2252번 줄 세우기
링크텍스트풀이 방법Topological sort를 이용한다. 각 학생을 vertex로 보고, 각 규칙을 directed edge로 볼 수 있다. 결과는 규칙을 만족하는 결과를 요구하므로, 모든 edge의 방향성을 만족하는 topological sort가 적절하다.Top
4.백준 2239번 스도쿠
링크텍스트스도쿠가 주어지면 정답을 출력하는 프로그램을 작성해야 한다.정답이 여러가지라면 사전식으로 가장 앞서는 것을 출력한다.풀이 방법Brute force, backtracking 방식으로 푼다. 우선 값이 0인, 즉 채워야 하는 칸들의 좌표를 vector인 zeroC
5.백준 2623번 음악프로그램
백준 2623번 음악프로그램순서를 정하는 문제에서 바로 topological sort라는 느낌이 왔다.Directed graph의 component 중 각 node로부터 다른 모든 node로 이동하는 경로가 있는 component를 SCC라 한다. Cycle이 있는 경
6.백준 7579번 앱
백준 7579번 링크NP hard 문제이다. Optimization version의 정의는 다음과 같다.Input: Positive integers $$W, w{1}, ... , w{n}$$ and $$v{1}, ... , v{n}$$Output: A subset S
7.백준 9252번 LCS 2
백준 9252번 링크Longest common subsequence를 찾는 전형적인 DP 문제다. 점화식은 다음과 같다.$$DPi = \\begin{cases}DPi - 1 + 1 &\\text{if } stri == strj \\max(DPi - 1, DPi) &\\
8.백준 9328번 열쇠
백준 9328번 링크조건이 많아서 BFS 문제처럼 생기긴 했는데 어떻게 풀어야 하나... 고민하다가 main queue, sub queue를 만드는 방식을 생각해냈다.Main queue는 일반적인 BFS에서 사용하는 queue다. Sub queue는 아직 열쇠가 없어서
9.백준 9466번 텀 프로젝
백준 9466번 링크Cycle을 찾는다는 점에서 그래프 문제처럼 생겼지만, 그래프 형태가 워낙 단순해서 스택 문제라고 생각해도 될 것 같다. 사실 DFS나 스택이나 뭐... 같은 방식이니 다른 분들과 다 비슷하게 푼 것 같다.각 vertex는 directed edge를