본문 바로가기
반응형

알고리즘

[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..
[BOJ 19585] 전설 [문제] www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net [난이도] - Platinum 3 (solved.ac 20.12.10 기준) [필요 개념] - 트라이 (Trie) / (해싱) [풀이] 처음에는 색상과 닉네임을 모두 하나의 트라이에 넣고, 팀명을 탐색하면서 색상과 일치하는 모든 위치를 찾아 해당 위치 이후의 문자열들을 잘라 다시 트라이에 넣어서 닉네임과 일치하는지를 체크하였는데 83%에서 TLE가 발생했다. 만약 팀명이 2000자이고, ..
[BOJ 3080] 아름다운 이름 [문제] www.acmicpc.net/problem/3080 3080번: 아름다운 이름 상근 선생님은 학생들에게 번호를 붙여주려고 한다. 상근이는 미술 선생님이기 때문에, 이름의 순서도 아름다워야 한다고 생각한다. 따라서, 다음과 같은 규칙을 지켜서 번호를 정하려고 한다. www.acmicpc.net [난이도] - Platinum 2 (solved.ac 20.12.10 기준) [필요 개념] - 트라이 (Trie) - 재귀 - 순열 [풀이] 문제의 조건을 해석해보면, 특정 index에서 묶이는 문자열들이 있다. 예제 2를 통해서 이해해보자. 같은 알파벳 순서로 시작하는 두 이름 사이에는 모두 그 순서로 시작하는 단어가 있어야 한다. 이 말은, 같은 알파벳 순서로 시작하는 이름들은 모두 이웃해야 한다는 의미..
[BOJ 1533] 길의 개수 [문제] www.acmicpc.net/problem/1533 1533번: 길의 개수 첫째 줄에 교차점의 개수 N이 주어진다. N은 10보다 작거나 같고, 시작점의 위치 S와 끝점의 위치 E, 그리고 정문이가 늦는 시간 T도 주어진다. S와 E는 N보다 작거나 같은 자연수이다. T는 1,000,000,000 www.acmicpc.net [난이도] - Platinum 4 (solved.ac 20.11.28 기준) [필요 개념] - 그래프 - 분할 정복을 이용한 거듭제곱 [풀이] 가중치가 없는 그래프인 경우, 0 또는 1로 이루어진 그래프의 인접 행렬이 주어질 때 i에서 N번 이동해서 j로 가는 경우의 수는 인접행렬의 N제곱의 (i, j) 값이다. 이를 이용하기 위해서 가중치가 주어지는 이 문제의 그래프를 조..
[DFS] 그래프 간선의 분류 / 사이클(Cycle) 찾기 1. 깊이 우선 탐색(DFS)과 그래프 간선의 분류 어떤 방향 그래프를 깊이 우선 탐색(DFS)했을 때, 탐색이 따라간 간선들을 모으면 트리 형태를 가진다. 이때, 생성된 트리를 DFS 스패닝 트리 (DFS Spanning Tree)라고 부른다. DFS 스패닝 트리를 구성하고 나면 기존 그래프에서의 간선들을 네 종류로 나눌 수 있다. 1. 트리 간선 (Tree Edge) - DFS 스패닝 트리에 포함된 간선 2. 순방향 간선 (Forward Edge) - DFS 스패닝 트리의 선조(ancestor)에서 자손(descendant)으로 가는 간선이면서, 트리에 포함되지 않은 간선 3. 역방향 간선 (Back Edge) - DFS 스패닝 트리의 자손에서 선조로 가는 간선이면서, 트리에 포함되지 않은 간선 4...
[BOJ 1073] 도미노 [문제] www.acmicpc.net/problem/1073 1073번: 도미노 은진이는 도미노 게임을 좋아한다. 도미노는 직사각형 모양이고, 두 개의 정사각형으로 나누어져 있다. 그리고, 각 정사각형에는 0보다 크거나 같고, 9보다 작거나 같은 정수가 하나 쓰여 있다. www.acmicpc.net [난이도] - Platinum 4 (solved.ac 20.11.06 기준) [필요 개념] - 오일러 회로 (Eulerian Circuit) [풀이] (이 블로그를 참고했습니다. wootool.tistory.com/46) 이 문제는 코드나 풀이가 상당히 간단하지만, 생각해내기가 쉽지 않은 문제이다. 우선 오일러 회로 개념에 대한 이해가 필요하다. 짧게 설명하면, 무향 그래프에서 그래프의 시작점으로부터 출발해서..
[BOJ 5821] 쌀 창고 [문제] www.acmicpc.net/problem/5821 5821번: 쌀 창고 첫째 줄에 R, L, B가 주어진다. 둘째 줄부터 R개 줄에는 X[i]가 주어진다. (1 ≤ R ≤ 100,000, 1 ≤ L ≤ 1,000,000,000, 0 ≤ B ≤ 2,000,000,000,000,000) www.acmicpc.net [난이도] - Platinum 4 (solved.ac 20.10.29 기준) [필요 개념] - 이분 탐색 (Binary Search) - 누적 합 (Prefix Sum) [풀이] 각 논들이 일직선상에 주어져 있고, 해당 논을 수확하기 위해서는 쌀 창고와의 거리만큼 비용이 필요하다. 지불할 수 있는 비용 한도가 정해져 있고, 한도 내에서 쌀 창고의 위치를 잘 정해줘서 수확할 수 있는 최대..

티스토리툴바