www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 이 문제는 전형적인 dp이면서 가장 긴 증가하는 배열을 구하면 된다. 기본 예제에서 확인해보자 3 7 5 2 6 1 4 여기서 가장 길게 증가하는 배열은 3 5 6이다 이 사이의 값들만 옮겨서 1 2 3 4 5 6 7로 바꾸어주면 된다. 3 5 사이로 4 3 밑으로 1, 2 6 뒤로 7 이렇게 되면 1, 2, 4 ,7만 옮기면 되기 때문에 4가된다. 그래서 이 문제는 가장 길면서 증가하는 배열의 수를 구한 다음 입력 ..

백준 1563 개근상 www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 전형적인 dp문제이다. 이전의 정보를 이용해서 풀어야하는데 문제를 맞고나서 다른 사람들의 풀이를 보니 대부분 다르게 풀어서 내가 푼 방법을 공유하려고한다. 우선 3차원 배열을 이용해 dp[일][지각의 수][연속된 결석의 수]로 표현해주었다. 해당 일에 지각의 수와 연속된 결석의 수의 개근상이 가능한 사람의 수가 된다. 그럼 배열로 나타낼 수 있는 경우의 수는 얼마나 될까? dp[요일][0][0] = d..

백준 개미굴 14725 백준 개미굴 문제의 경우 전형적인 trie문제이다. trie이란 트리 구조를 활용하여 여러 개의 문자열 중 자신이 갖고 있는 문자열을 찾을 수 있는 알고리즘이다. hoony-gunputer.tistory.com/entry/%ED%8A%B8%EB%9D%BC%EC%9D%B4 트라이 트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있습니다. 문자열 집합 S={"BE", "BET", "BUS", "TEA", "TEN" }를 저장하는 트리의 예는 hoony-gunputer.tistory.com 입력되는 문자열을 기준으로 layer을 구성해서 출력하는 문제이다. 이문제에서 체크해주어야 하는 상황은 몇가지가 있다. 1. 이 ..

백준 2655번 - 가장 높은 탑 쌓기 가장 높은 탑 쌓기 문제의 경우 전형적인 dp문제 중 하나이다. 조건 중 하나가 밑의 블럭의 크기와 무게가 현재 블럭 보다 더 커야 한다는 조건이 있다. 이전의 위치한 블럭의 값 들과 계속해서 비교하면서 값을 업데이트해준다. 우선 시작하기전에 필자의 경우에는 넓이의 기준으로 내림차순으로 정렬했다. (물론 무게를 기준으로 정렬해도 된다.) 그래서 블럭의 이전의 값들과 비교하기 편하다. 내림차순이면 이전의 넓이는 항상 큰 값이 된다. 따라서 점화식은 아래와 같다. dp[i] i번째 블럭의 가장 높은 높이이다. if(올릴 수 있는 블럭이라면) { // 현재 블럭이 더 가볍고 부피가 작다면 dp[now] = max(dp[now], dp[prev] + height[now])..

문제는 아니고 이론이다. 특정한 트리가 주어졌을 때 이 트리가 이진탐색 트리의 조건에 만족하는지 만족하지 못하는지 체크하는 문제이다. 이진 탐색 트리를 만족하기 위해서는 부모의 노드 오른쪽에는 큰 값 왼쪽에는 작은 값이 위치하는 것을 체크해주면 된다. 하지만 이를 하나하나씩 다 체크해주면 확인하기에는 시간복잡도 부분에서 오래걸리게 된다. 따라서 O(n)만에 해결하는 방법을 작성해보려고 한다. 우선 아래 그림을 보자 해당 노드의 최대 값과 최소 값을 지정한 후 이 사이에 있다면 참이고 그 반대면 거짓이 된다. 참과 거짓을 밝히는 if문은 아래와 같다. if(minValue value) true; if(minValue > value || maxValue value valu..