https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 가장 기본적인 최장 거리 거리 수열 문제이다. O(n^2)의 시간복잡도를 가지기 때문! 해당 알고리즘은 백준에 '가장 긴 증가하는 부분 수열' 시리즈를 풀어보면 좋다 현재 위치 기준으로 이전 위치들을 탐색하며 본인보다 작은게 있다면 dp 값을 최대로 업데이트 해주는 방식이다. import sys #from collections import deque #import heapq #sys.setrecursion..
https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 문제가 조금 복잡하기 쓰여있지만, 하얀 색으로 칠할 수 없고 모든 입력이 칠할 수 있는 경우로만 주어지므로 그렇게 어렵게 생각하지 않아도 될 듯 하다. 기본적인 트리 탐색 알고리즘인 dfs와 bfs 중 하나 골라서 풀어도 되는데, 필자는 bfs로 골랐다. 핵심은 바로 부모와 나(자식)의 색깔 차이이다. 부모와 색이 다르다면 무조건 색을 한번 칠해야 하므로 그럴 때 마다 카운트를 해주면 된..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프인지 아닌지를 판단하는 문제이다 정점 하나하나씩 bfs 탐색을 진행해주는데, 주의해야 할 점은 그룹을 지어야 한다는 것이다! (왜 bfs를 한번에 돌리지 않고, 정점 하나씩 해주냐면 입력이 어떻게 들어올 지 모르기 때문이다. 비연결 그래프가 존재하는 경우, 시작점과 연결되지 않은 곳은 탐색할 수 없기 때문에 모든 정점에 대해 탐색해주는 것이다) 트리를 하나 떠올려 보자. level 0 ..
https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 간단한 위상정렬 문제이다. 내가 간단하다고 말하는 기준은 좀 어이없을 수 있지만, 내가 푼 풀이법 그러니까 내 코드가 구글링했을 때 수두룩하게 나오는 다른 사람의 코드와 거의 동일하면 간단한 문제라고 생각한다 ㅋㅋ 풀이법은 다음과 같다. 1. 위상 정렬의 첫 시작은 아무것도 건들지 않은 상태에서 진입차수가 0인 것부터 시작해주면 된다. 2. 하나씩 탐색하면서 해당 노드까지 가는 최장거리를 갱..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이 문제가 왜 DP를 이용하는지에 대한 이해를 도와주는 그림이다. start와 end가 같을 때, list[start+1, end-1]이 이미 팰린드롬이라면 list[start,end]가 팰린드롬인지 아닌지 바로 판별할 수 있기 때문이다. 1. 우선 dp 테이블을 하나 정의한다. ex) dp[i][j], i는 start를 의미하고 j는 end를 의미한다 2. 길이가 1짜리인 리스트 (= i와 j가 동일한) 는 모두 팰린드롬이다 3. 길..
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 1167번 문제와 입력만 다르지 풀이법은 동일하다. https://oh2279.tistory.com/167
