Algorithm/문제풀이(47)
-
백준 1695 팰린드롬 만들기
www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 백준 1695 팰린드롬 만들기 팰린드롬이란 광고의 문구 앞뒤가 똑같은 전화번호와 똑같이 앞과 뒤가 같은 문자열을 뜻한다. 비슷한 문제로 이 문자열이 팰린드롬인지 판단하는 문제는 있었지만 이 문제의 경우 몇개의 숫자를 끼워 넣어야 팰린드롬이 되는지 맞추는 것이다. 우선 팰린드롬이 되는 규칙을 찾아야한다. 1 2 3 4 2 1, 2, 3, 4, 2의 경우 2..
2021.01.25 -
백준 1707 이분 그래프
www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 백준 1707 이분 그래프 정답률이 꽤나 낮았는데 한번에 맞추어서 기분이 좋았던 문제이다. 백준 이분 그래프는 인접하지 않는 정점들을 두개의 그룹으로 나눌 수 있는지 판단하는 문제이다. 필자의 경우 현재의 그룹이 0이면 방문한적 있는 정점의 그룹이 현재 정점의 그룹과 같다면 NO를 출력해주었다. 오른쪽의 경우 4의 정점을 방문하고 있을 때 다음 정점의 3과 그룹이 같기 때문에 NO를 출력하게된다. ..
2021.01.25 -
백준 2688 줄어들지 않아
www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1
2021.01.22 -
백준 2631 줄세우기
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가된다. 그래서 이 문제는 가장 길면서 증가하는 배열의 수를 구한 다음 입력 ..
2021.01.22 -
백준 1563 개근상
백준 1563 개근상 www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 전형적인 dp문제이다. 이전의 정보를 이용해서 풀어야하는데 문제를 맞고나서 다른 사람들의 풀이를 보니 대부분 다르게 풀어서 내가 푼 방법을 공유하려고한다. 우선 3차원 배열을 이용해 dp[일][지각의 수][연속된 결석의 수]로 표현해주었다. 해당 일에 지각의 수와 연속된 결석의 수의 개근상이 가능한 사람의 수가 된다. 그럼 배열로 나타낼 수 있는 경우의 수는 얼마나 될까? dp[요일][0][0] = d..
2021.01.22 -
백준 개미굴 14725
백준 개미굴 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. 이 ..
2021.01.20