본문 바로가기

728x90
반응형

BOJ

[BOJ 1396] 크루스칼의 공 [문제] https://www.acmicpc.net/problem/1396 1396번: 크루스칼의 공 첫째 줄에는 그래프의 정점의 개수 n과 간선의 개수 m이 주어진다. 그리고 두 번째 줄에서 m+1번째 줄까지는 a b c의 형태로 a와 b를 잇는 간선의 고유값이 c라는 의미이다. m+2번째 줄에는 알고 싶은 www.acmicpc.net [난이도] - Platinum I (21.06.10 기준) [필요 개념] - Union-Find - Parallel Binary Search (병렬 이분 탐색) or LCA [풀이] 이 문제는 크게 두 풀이로 나뉜다. 첫 번째로는 PBS(병렬 이분 탐색)이다. 흔히 PBS의 대표 예제 문제로 알려져 있는데, 조만간 PBS에 대한 글을 따로 작성할 예정이라 자세한 풀이는 ..
Platinum DP 문제들 풀이 (1) 요즘 DP에 약한 기분이 많이 들어서, 플래티넘 DP 문제 중 특별한 기법이나 최적화를 이용하지 않는 문제들을 푼 사람 수로 정렬해서 안 푼 문제들을 선별하여 조금씩 풀고 있다. 푼 사람 수로 정렬한 문제라 이미 남들에겐 웰논일지도 모른다. 많이 풀린 문제들답게 플래티넘임에도 불구하고 꽤 잘 풀리는 것도 있는 반면 해설 없이는 못 풀었을 문제들도 많았다. 아마 DP라는 걸 모르고 풀었다면 체감 난이도가 훨씬 높았을 것 같다. [BOJ 1126] 같은 탑 (Platinum III) N = 50개의 블록을 이용하여 높이가 같은 두 개의 탑을 만든다. 모든 블록을 사용할 필요는 없으며, 각 블록의 높이는 최대 50만이고, 모든 블록의 높이의 합이 50만 이하이다. 이때, 만들 수 있는 탑의 높이의 최댓값을 구..
USACO 2020 US Open Contest [Bronze] 풀이 1. [BOJ 18880] Social Distancing I Gold V [문제 설명] 일렬로 N개의 공간이 있고, 각 공간은 소가 들어있거나(1) 들어있지 않다(0). 그리고 빈 두 공간을 골라 소를 넣어주는데, 이때 소가 들어있는 두 공간 사이의 간격의 최솟값을 D라고 하면 D가 최대가 되어야 한다. [풀이] Case work 문제이다. 경우들을 잘 처리해주어야 한다. 지금부터 말하는 '구간'은 소가 배정되어있지 않은 연속된 공간을 의미한다. 우선, 가장 긴 구간에서 하나를 뽑아서 구간을 나눈 후, 다시 가장 긴 구간에서 하나를 뽑는 것이 최적일 것이라고 생각할 수 있다. 하지만 이 문제에서는 공간을 두 개 고르기 때문에 단순히 이 방식으로는 D를 최대로 만들지 못한다. 예를 들어 1, 10, 13..
[BOJ 20190] 버블버블 [문제] www.acmicpc.net/problem/20190 20190번: 버블버블 여러분은 N개의 정수 A1, · · · , AN을 버블 정렬(bubble sort)를 이용하여 단조증가하도록 (감소하지 않는 순서가 되도록) 정렬하려고 한다. 주어진 정수들 중에는 같은 값이 있을 수 있다. 버블 정렬 www.acmicpc.net [난이도] - Platinum II (20.12.28 기준) [필요 개념] - Lazy Propagation - Segment Tree / Fenwick Tree [풀이] 올해 koi 중등부 2차 문제이다. 중등부에 이런 난이도 문제가 나온다는 거에 한 번 놀랐고, 이 문제 만점자가 4명이나 된다는 거에 두 번 놀랐다. 이 문제를 보고 lazy propagation을 떠올리기도..
[BOJ 17353] 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 [문제] www.acmicpc.net/problem/17353 17353번: 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 욱제의 은밀한 취미 중 하나는 매일 밤하늘을 감상하는 것이다. 😓 욱제는 하늘의 별들이 다음과 같은 규칙들을 따르며 떨어지는 걸 관찰했다. 별이 떨어지는 위치는 N개의 점이다. 점은 순 www.acmicpc.net [난이도] - Platinum II (solved.ac 20.12.22 기준) [필요 개념] - Lazy Propagation with Segment Tree - Fenwick Tree 디스크립션은 간단하다. 두 종류의 쿼리가 들어오고, 한 쿼리는 구간 [L, R]에 순서대로 1, 2, ..., R-L+1을 더해준다. 나머지 한 쿼리는 X번째 원소의 값을 출력해준..
[BOJ 2809] 아스키 거리 [문제] www.acmicpc.net/problem/2809 2809번: 아스키 거리 첫째 줄에 거리의 길이 N이 주어진다. 다음 줄에는 거리에 원래 적혀져있는 알파벳이 주어진다. 셋째 줄에는 묶음 타일의 종류의 개수 M이 주어진다. 다음 M개 줄에는 각 묶음 타일에 적혀져있는 www.acmicpc.net [난이도] - Platinum 2 (20.12.11 solved.ac 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 아호코라식 문자열 판별 알고리즘의 응용문제이다. 타일과 일치하는 부분을 제외한 문자의 개수를 구하는 문제인데, 단순하게 아스키 거리의 각 위치(index) 별로 끝에 일치하는 타일들을 모두 고려한다면 시간 초과가 발생할 것 같다....? (정확하게는 모르겠다) 따..
[BOJ 10256] 돌연변이 [문제] www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net [난이도] - Platinum 3 (solved.ac 20.12.11 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 마커(marker)의 돌연변이의 경우의 수는 최대 $m^2$이다. m이 100이하이므로 모든 돌연변이를 직접 다 만들어도 무리가 없다. 그리고, 만들어진 돌연변이들을 트라이에 넣어두고, DNA문자열을 탐색한다. 이때, 모든 돌연변이들의 길이가..
[BOJ 9250] 문자열 집합 판별 [문제] www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net [난이도] - Platinum 2 (solved.ac 20.12.11 기준) [필요 개념] - 아호코라식 (Aho-corasick) [풀이] 아호코라식 알고리즘의 가장 기본 문제이다. 집합에 주어지는 모든 단어들을 트라이에 넣고, 판별해야하는 문자열별로 체크하면 된다. #include using namespace std; struct Trie { Trie* ch[26]; Trie* fail; b..