MathTrauma

문제 링크 : https://www.acmicpc.net/problem/5735 5735번: Emoticons :-) 이모티콘은 채팅과 이메일에서 단어로 표현할 수 없는 감정을 나타내기 위해 종종 쓰인다. 이는 다양한 면에서 장점이 있지만, 많은 사람들은 이모티콘을 매우 짜증난다고 여기며, 없애고 싶어 www.acmicpc.net 아호-코라식(Aho-Corasick) 알고리즘 자체에 대해선 설명을 생략한다. 공백으로 대체해야할 문자의 개수를 최소화하는 방법은 무엇일까? 결론부터 말하면 텍스트를 검색해가면서 찾은 키워드(이모티콘)의 마지막 문자를 제거하면 된다. 텍스트 중에 등장하는 (-:-( 을 보자. 가운데에 위치한 : 를 제거하면 (-: 과 :-( 의 두 개의 키워드를 제거할 수 있음을 알 수 있다...

문제 링크 : https://www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net Aho-Corasick 연습 문제. 찾아야할 키워드는 마커(marker)의 부분 문자열을 뒤집은 모든 가능한 경우인데, 뒤집어야할 시작을 i , 끝을 j 로 두면 많아야 10000 가지이니 충분이 버틸만 하다. 한 가지 좋은 소식은 모든 키워드의 길이가 같아서 키워드 출현 횟수의 중복이 발생하지 않는다는 점! 그 외에 따로 설명할 것이 없다. #include u..

문제 링크 : https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp 문제에서 초기화는 늘 어려운 문제임을 상기시켜 주는 문제. 기본 연속합 문제에 두 가지 추가적으로 고려해야할 사항이 생겼다. 1. 적어도 하나의 수를 선택할 것. (모두 음수로 이루어지 수열의 경우를 주의해야 한다.) 2. 하나를 제거하고 연속합을 만들 수 있다. dp[0][i] = i 를 번째 항으로 끝나는 최대 연속합 으로 정의하자. 이 경우 $$ dp[0][i]= \max( ..

문제 링크 : https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 선행 관계가 작업 번호 순으로 주어지니 딱히 전처리할 것들은 없다. dp[i] 는 i 번째 작업을 마칠 수 있는 최소 시간으로 정의한다. $a[i]$ 를 i 번 작업에 소요되는 시간, $S_i$ 를 i 번 작업에 필요한 선행 작업이라 할 때, 다음 관계식이 성립한다. $$ dp[i]= \max\limits_{j \in S_i } dp[j] + a[i] $$ #include ..

문제 링크 : https://www.acmicpc.net/problem/9250 9250번: 문자열 집합 판별 집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하 www.acmicpc.net 여러 키워드를 동시에 검색하는 아호-코라식(Aho-Corasick) 알고리즘 연습 문제이다. 문서 전체의 내용을 하나의 스트링으로 간주하고 여러개의 키워드의 존재 여부나 등장 횟수를 찾는 상황을 생각해보자. 각 지점에서 키워드와 일치하는지 비교하는 무식한 방법이 있을 것이다. 하지만 키워드의 개수가 늘어나고 각 키워드의 길이가 짧지 않다면... 효율적인 알고리즘 대부분이 그러..

문제 링크 : https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 색 r,g,b 를 0,1,2 에 대응시키자. 주어진 입력은 $ arr[i][k] ( 1 \le i \le n \; , \; 0 \le k

문제 링크 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 트라이(trie) 기본 문제. 아호-코라식(Aho-Corasick) 알고리즘을 복습하기 전에 다시 풀어 봤다. 입력받은 문자열을 저장할 strs를 동적으로 할당하면 메모리는 많이 절약되지만 시간은 살짝 더 걸린다. #include using namespace std; vector strs; struct trie { char c; bool isEnd; trie*..

문제 링크 : https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 동전의 종류 N 이고 만들어야 할 금액은 V 이다. $recur(n,v)$ 는 $n \; (1\le n \le N)$ 번 이하의 동전들을 사용해서 v 금액을 만드는 방법의 수이다. #include using namespace std; int N,V; int arr[21]; int dp[21][10001]; int recur(int n, int v){ if(n==1){..