아무 말

https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 풀이 일단 간단하게 생각할 수 있는 점화식을 정의해 보자 D[i]는 문자열 S의 i번째 까지 고려했을 때 분할의 개수의 최솟값. 자연스럽게, if(S[i]~S[j]가 팰린드롬) D[i]=D[j-1]+1 이 성립함을 알 수 있다. 이제 매번 S[i~j]가 팰린드롬임을 어떻게 확인하냐는 건데, Manacher를 이용해도 좋지만 너무 ..

https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net N이 5e6이하로 매우 크다. O(N)짜리 풀이가 필요하다. 조금 생각해보면, deque을 이용해서 범위 밖에 있는 수는 없애주면 되고, 현재 수보다 큰 수는 이제 비교할 필요가 없으므로 없애주면 된다. 아래는 코드이다. 우선순위 큐로 푼 사람도 꽤나 있을 것 같은데, 조금만 생각해서 이 풀이대로 해결하면 코딩하는데 1분도 채 안걸린다. #include using ..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 D[i]={i번째 건물을 짓는데 걸리는 총 시간} D를 위와 같이 정의 하면, 마지막으로 짓고 싶은 건물 W에서 시작하여 각 건물에 대해 건물을 짓기 위해 필요한 건물들을 짓는데에 필요한 총 시간 중 최댓값만 가져오면 됩니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 문자열의 최대 길이가 5000이므로 O(N^2)풀이가 가능합니다. 알파벳에서 각 문자가 등장하는 자리를 배열에 저장하고 이를 이용하여 서로 같은 부분의 길이가 얼마나 되는지를 확인하여 주면 됩니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace ..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 심플하게 위상 정렬을 수행하는 문제 위상 정렬에 대한 설명은 아래의 포스트를 참조 https://jiuge-meogari-ps.tistory.com/14 위상 정렬(Topological Sort) 위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기..

https://www.acmicpc.net/problem/8913 8913번: 문자열 뽑기 a와 b로만 이루어진 문자열 s이 있다. 그룹은 같은 글자로 이루어진 가장 긴 연속 부분 문자열이다. 길이가 2 이상인 s의 모든 그룹 g는 제거할 수(뽑을 수) 있고, 남은 왼쪽 부분과 오른쪽 부분을 www.acmicpc.net 풀이 문자열의 길이가 최대 25정도로 매우 작기 때문에 모든 경우의 수를 다 확인할 수 있다. 문자열을 bit로 표현하여 뽑아낼 수 있는 부분을 차례대로 뽑아내면서 한번이라도 가능한 경우가 나오면 탐색을 중단하고 1을 출력한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ..

https://www.acmicpc.net/problem/9002 9002번: Match Maker Print exactly one line for each test case . The line should contain a stable match for the test case. Each match should be represented as a sequence of the women’s id, according to the increasing order of men ’s id. The woman with the first id in the www.acmicpc.net 풀이 여자와 남자를 정점으로 하고 모든 여자와 남자를 간선으로 이으면 이는 이분 그래프를 띤다. 안정된 매칭을 만들기 위해서 아래와 같..

https://www.acmicpc.net/problem/9008 9008번: Castle Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with integer n, the number of points, where 4 ≤ n ≤ 10,000. Each of the following www.acmicpc.net 사용 알고리즘 깊이 우선 탐색 정렬 풀이 문제의 "the interior angle formed by its two incident edge..

https://www.acmicpc.net/problem/9061 9061번: 두 직사각형 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스는 첫 줄에 자연수 N (1 ≤ N ≤ 10000) 이 주어지며, 그 이후 N www.acmicpc.net 사용 알고리즘 세그먼트 트리 (초반에 생각을 못해서 세그먼트 트리를 이용했다.) 정렬 풀이 그냥 x좌표나 y좌표 중 하나로 잡고 정렬해서 모든 점에 대해서 그 점을 기준으로 두 직사각형을 만들어서 답을 구하면 된다. 이때 두 직사각형은 모든 점을 다 포함해야 함으로 왼쪽과 오른쪽에 있는 모든 점들의 y좌표의 최대값과 최소값을 알아야 한다. 이를 구하기 ..

https://www.acmicpc.net/problem/22345 22345번: 누적 거리 KOI 나라는 수직선 위에 놓인 N개의 마을로 구성되어 있다. 이 중 i (1 ≤ i ≤ N)번째 마을은 xi 위치에 놓여 있으며 ai명이 거주 중이다. 또한 서로 다른 두 마을이 같은 위치에 놓인 경우는 없다. KOI www.acmicpc.net 이전에 포스팅한 Stadium이라는 문제와 매우 유사하다. 다만 이 문제에서는 x좌표가 정렬이 되어있지 않으므로 정렬을 해주어야 한다. 그리고 주어지는 후보지점에서의 값을 계산해주면 된다. Stadium에서는 변화량에 집중하였다면 이번에는 그냥 계산하면 된다. 누적 거리를 구하기 위해서는 각 쿼리가 어떠한 두 마을 사이에 있는지 알아야 하며, 이를 이분탐색을 통해 찾아..