4luv1015

https://www.acmicpc.net/problem/20191 20191번: 줄임말 문자열 A가 문자열 B의 줄임말이라는 것은 B의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 A를 만들 수 있다는 뜻이다. 정의에 의해서 B는 자기 자신의 줄임말임에 유의하라. 예를 들 www.acmicpc.net 이분 탐색 문제 풀이 아이디어는 다음과 같다. 문자열 S에 대해서 각각의 문자에 대해 반복문을 돌면서 문자열 T에서 가장 처음 등장하는 위치가 어디인지 찾는다. 문자를 찾으면 T에서 위치하는 인덱스를 기록해둔 뒤 S의 다음 문자에 대해 T에서 처음 등장하는 위치를 찾을 때는 기록해둔 인덱스 다음에 있는 문자들 중에서 가장 처음 등장하는 위치가 어디인지 찾는다. 만약 없다면 정답 값을 하나 증가..

https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 우선순위 큐를 활용한 그리디 문제 언뜻 보면 파일 합치기(11066번)과 비슷해 보일 수 있지만 이 문제의 경우에는 연속해있는 파일만 합칠 수 있다던지 하는 조건이 없으므로 현재 상황에서 가장 에너지가 작은 슬라임 두 개를 합치면 된다. 매번 가장 에너지가 작은 슬라임 두 개를 찾기 위해서 우선 순위 큐를 사용할 것이고 가중치가 가장 적은 것을 선택해야 되..

https://www.acmicpc.net/problem/14401 14401번: 악덕 나라 남규 나라의 왕 zych는 도로 정비 계획을 만들고 있다. 남규나라의 도시는 2차원 평면에 존재하며, 각 도시는 (xi,yi)에 위치한다. 새롭게 고속도로를 만들어 모든 도시를 고속도로를 통하여 다른 www.acmicpc.net MST(최소 스패닝 트리)+ CCW(선분 교차 판정) 아무 생각 없이 MST문제인 줄 알고 풀었는데 틀리고 뒤늦게 기하적인 요소가 있다는 걸 깨달았다. 문제의 기본 틀은 MST 변형과 같다. 노드들의 좌표를 받아 모든 간선을 다 계산하고(N^2) 기존에 연결된 간선들에 맞게 유니온 한 뒤 disjoint set의 개수(부모가 자신인 노도의 개수)를 세고 크루스칼 알고리즘을 이용해 그 개수..

https://www.acmicpc.net/problem/30400 30400번: 팰린드롬 제거 이안이는 팰린드롬을 싫어한다. 팰린드롬인 단어를 보면 당장 그 단어를 지워야 할 정도로 팰린드롬을 매우 싫어한다. 팰린드롬은 'level', 'bob'과 같이 양쪽으로 읽었을 때 동일하게 읽히는 단어 www.acmicpc.net 매내처 알고리즘 응용 문제 처음에 문제를 해결한 방식은 다음과 같다. (조금 복잡한 방식이다 아래에 훨씬 단순한 방법이 있다.) 우선 매내처를 이용해 길이가 M인 팰린드롬 구간을 모두 찾는다. 각각의 구간들이 이러한 시작과 끝을 같는다고 하자. 구간 각각의 문자들 중에서 하나 이상의 문자가 파괴되기만 하면 조건을 만족하므로 우리가 구해야 될 것은 그림에서 최소 몇개의 수직선을 그어야 ..

https://www.acmicpc.net/problem/5502 5502번: 팰린드롬 팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 www.acmicpc.net 서로 다른 방식의 두 가지 dp로 문제를 풀어보았다. 실행 시간은 1번 방법이 2번 방법보다 두 배 정도 더 빨랐다. 1. LCS를 활용한 방법 당연한 이야기지만 기존 문자열에 문자를 추가해 팰린드롬을 만든다면 추가할 문자는 기존에 존재하는 문자 중 하나에 대응하는(팰린드롬 상에서) 문자일 것이다. 그런데 여기서 문자를 추가하는 것은 추가할 문자에 대응하는 문자를 삭제하는 것과 동일하다. 따라서 최소 횟수를 구하는..

https://www.acmicpc.net/problem/30831 30831번: 선후수과목 첫 번째 줄에 과목 이수 체계도에 포함된 과목의 수 $N$, 권장 선후수 관계의 수 $A$, 필수 선후수 관계의 수 $B$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 1\ 000\ 000; \ 0 \leq A, B; \ A+B \leq N-1)$ 다음 www.acmicpc.net 2023 uospc(서울시립대 컴퓨터과학부 알고리즘 경진대회) div2의 최고 난이도 문제이다. 직접 참가했던 대회이니만큼 대회에 관해 얘기를 조금 하자면, 큰 대회가 아닌지라 당시 꽤나 자신만만히 대회에 참가했었는데 아쉽게 2등으로 대회를 마무리했다. 못 풀었던 문제 전부가 알고보니 상당히 스탠다드하거나 웰노운한 문제,..

https://www.acmicpc.net/problem/12990 12990번: A Heap of Heaps n개의 자연수로 이루어진 수열이 하나 주어진다. (a1, a2, …, an이라고 하자.) 성관이는 이 수열을 이용해 k진 힙을 작성하려고 한다. k진 힙이란 각 내부 노드가 k개씩의 자식을 가지는 루트 있는 www.acmicpc.net 문제 풀이 아이디어 자체는 상당히 단순한 편이다. 1 ~ N-1진 힙 각각에 대해서 각각의 노드의 자식들 중에 값이 자신보다 작은 자식의 개수를 세어 더한 뒤 출력해주면 된다. 우선 문제를 살펴보면 어떤 노드의 자식 노드들은 연속한다는 것을 알 수 있다. 또한 k진 힙에서 i번째 노드의 자식 노드의 구간이 2+(i-1)*k ~ 1+i*k이라는 것도 확인할 수 있다..

https://www.acmicpc.net/problem/9029 9029번: 정육면체 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20) 가 주어진다. 각 테스트 케이스에 대해 원목의 크기를 나타내는 W,L,H (1 ≤ W, L, H ≤ 200) www.acmicpc.net 특별할 것 없는 3차원 dp이다. 높이, 가로, 세로를 차원으로 하는 3차원 dp배열을 만들고 해당하는 높이, 가로, 세로를 가진 블럭을 최소 개수의 정육면체로 나눌 때 그 최소 개수를 배열에 저장하면 된다. 재귀를 통한 탑다운 방식으로 dp를 구현하면 깔끔하게 코드가 짜일 거 같아서 시도해봤는데 예상대로 잘 됐다. 높이, 세로, 가로가 같다면 1을 리턴..

https://www.acmicpc.net/problem/9460 9460번: 메탈 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 점(금속)의 개수 n과 k가 주어진다. (2 ≤ n ≤ 10,000) 다음 줄에는 점 p1, p2, ..., pn의 좌표를 나타내는 정수 2n개 (x1, y www.acmicpc.net 매개 변수 탐색 + 그리디 알고리즘 문제 설명이 복잡하지만 간단하게 요약하면 다음과 같다. 2차원 좌표에서 x축에 평행한 선 k개를 서로 x좌표가 겹치지 않도록 그을 수 있는데 주어지는 점들 각각의 x좌표를 포함하는 선과 그 점 사이의 거리의 최대값이 가장 적어지도록 k개의 선을 그었을 때의 그 최대값을 구하는 문제이다. 매개 변수 탐색은 이분 탐색의 응용으로..

https://www.acmicpc.net/problem/14505 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 승수는 주 www.acmicpc.net https://www.acmicpc.net/problem/14517 14517번: 팰린드롬 개수 구하기 (Large) 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이..