아무 말

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를 이용해도 좋지만 너무 ..

iris.edu 에서 제공하는 자료를 이용한다. https://www.iris.edu/hq/inclass/lesson/determining_and_measuring_earths_layered_interior Determining and Measuring Earth's Layered Interior- Incorporated Research Institutions for Seismology Students work first in small groups, and then as a whole class to compare predicted seismic wave travel times, generated by students from a scaled Earth model, to observed seismic ..

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 ..

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2262&sca=99&sfl=wr_subject&stx=%EC%9E%A5%EC%95%A0%EB%AC%BC+%EA%B2%BD%EA%B8%B0 JUNGOL www.jungol.co.kr 물론 백준에도 이 문제가 있다. (문제번호 13303) KOI 2016 초등부 4번 문제로 뇌빼고 풀면 잘 풀리는 문제이다. 참고로 뇌를 사용해서 풀면 더 어렵다. 간단하게 상황을 구현하고, 이때 조금만 생각하면 알 수 있듯이 자동으로 정렬이 되는 set을 이용하며, 각 장애물에 대해 위 아래 둘 중 무조건 한곳으로만 빠져나간다는 사실로 부터 각 장애물 마다 두 가지 경우에서의 최소값만 insert 해주면 된다. 아래는 코드이다..

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://euleroj.io/problemset/viewer/5000 문제에 퇴각검색 태그가 달려있지만 신경쓰지 않아도 된다. 여기에서 각 칸의 색을 다른 칸에 영향을 주지 않고 바꾸기 위해서는 정확히 반대쪽 칸의 색을 바꾸었을 때 색이 변하는 부분의 색을 모두 바꾸어 주면 된다. (해보면 알 수 있다.) 원래 상태는 모두 하얀색으로 한다. 입력을 받아가면서 검은색이 있는 부분이 있다면 그 부분의 색을 바꾸었을 때 색이 바뀌는 부분과 그 부분의 색을 모두 바꾼다. 입력을 모두 받은 후 9번 칸 부터 1번칸 까지 탐색하며, 검은색이라면, 색을 바꾼다. 이때, 원래 상태에서 색을 바꾸는 경우는 여기서 색을 바꾸는 경우와 완전히 반대가 되어야 한다. 이대로 구현해 주면 된다. 코드 1 2 3 4 5 6 ..

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보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기..

위상 정렬(topological sort)은 G가 간선 (u,v)를 가질 때 u가 v보다 순서상으로 먼저 나타나도록 모든 정점을 선형으로 나열하는 것이다. 여기서 만약 그래프가 순환을 가진다면 선형 나열은 불가능하다. 아래와 같은 알고리즘은 하나의 방향 비순환 그래프를 위상 정렬 한다. 위상 정렬(G) 1 각 정점 v에 대해 종료 시간 v.f를 계산하기 위해 DFS(G)를 호출한다. 2 각 정점이 종료될 때마다 연결 리스트의 맨 앞에 삽입한다. 3 return 정점의 연결 리스트 중요한것은 위상 정렬한 순서대로 일을 수행할 때 일을 수행하지 못하는 일이 나오지 않는다는 것이다. 미리 어떠한 행동 A를 해야 B를 할 수 있다면 A를 하고 B를 해야한다는 것이다. 위 방식으로 위상 정렬을 할 때 시간복잡도는..

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 ..