https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 각 나라가 싸우는 경우를 확인하여 입력으로 받은 상태에 도달할 수 있는지 확인했다. 그런데, 모든 경우를 확인하는 건 아니고 입력으로 받은 상태에 도달할 가능성이 존재할 때만 확인을 해 나아갔다. 예를 들어, A팀과 B팀이 싸우는데, 입력받은 상태의 A팀의 승리 횟수는 1, B팀의 패배 횟수가 0이라면, A가 B를 이기는 경우가 있지 않은 것이므로 A가 B를 이기는 경우는 탐색해 나아가지 않는다. 코..

https://www.acmicpc.net/problem/20542 20542번: 받아쓰기 세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는 www.acmicpc.net 2차원 배열 cache에 cache[답안의 확인 인덱스][정답의 확인 인덱스] = "해당 위치의 답안과 정답을 확인할 때, 최소 점수"를 저장하는 다이나믹 프로그래밍을 통해 문제를 해결했다 코드 #include #include #include #include using namespace std; int n, m; string input; string answer; v..

https://www.acmicpc.net/problem/25577 25577번: 열 정렬정렬 정 첫 번째 줄에 배열의 크기 $N(4 ≤ N​ ≤ 100\,000)$이 주어진다. 그다음 줄에 배열의 원소 $A_1, A_2, \cdots, A_n (-10^9 ≤ A_i ≤ 10^9, i \neq j $ 이면 $ A_i \neq A_j )$ 이 주어진다. 배열의 원소는 모두 정수이다 www.acmicpc.net 순열 사이클(순열 그래프) 문제로, 주어진 배열과 완전히 정렬된 이후 옮겨진 위치 관계를 그래프로 만들어 순열 그래프를 만들고, 각 위치에서 dfs 하며, 순열 그래프에서 생기는 각 사이클의 크기를 확인해서 해당 사이클을 정렬하는 최소 연산 횟수를 구해가는 방법으로 문제를 해결했다. 코드 #inclu..

https://www.acmicpc.net/problem/12003 12003번: Diamond Collector (Silver) The first line of the input file contains \(N\) and \(K\) (\(0 \leq K \leq 1,000,000,000\)). The next \(N\) lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed \(1,000,000,000\). www.acmicpc.net 두 구간을 정하는데, 두 구간 모두 구간에서 다이아몬드 사이 차이가 k이하여야 하고, 두 구간의 합이 최댓값이 되는 ..

https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 슬라이딩 윈도우를 통해 조건을 만족하는 비밀번호의 개수를 구했다. 코드 #include #include #include #include using namespace std; int s, p; string dna; int check[4]; int result = 0; int main() { cin.tie(NULL); ios_base::sync_with_stdio(false);..

https://www.acmicpc.net/problem/27652 27652번: AB 집합 $A, B$와 문자열 $S$에 대하여, 다음 쿼리를 수행하는 프로그램을 작성하시오. add A $S$: $A$에 $S$를 추가한다. delete A $S$: $A$에서 $S$를 제거한다. add B $S$: $B$에 $S$를 추가한다. delete B $S$: $B$에서 $ www.acmicpc.net 집합 A의 문자열을 관리하는 트라이와, 집합 B의 문자열을 관리하는 트라이를 사용했는데, 집합 B는 접미사를 확인하므로, 문자열 순서를 거꾸로 저장해서 관리했다. 그리고 find S 쿼리에 대해, 해당 문자열을 접두사 + 접미사로 나누어지는 경우를 모두 확인하는데, 접두사는 A 집합의 트라이에서, 접미사는 B 집합..