반응형 알고리즘 썸네일형 리스트형 [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) 값이다. 이를 이용하기 위해서 가중치가 주어지는 이 문제의 그래프를 조.. Round #686 (Div. 3) 후기 및 풀이 처음으로 '언레가 되어버린 라운드'가 아닌 '언레로 적용되는' 라운드에 참여했다. 사실 부계도 1600을 이미 넘겨서 그냥 잘까 하다가 코포 중독증에 걸려버린 나로서는 그냥 자기는 아쉬워서 참가했는데 그냥 잤어야 했다... 다음날이 너무 힘들었다. 가볍게 참가해서 제출도 대충대충 하다 보니 WA가 많이 나왔다. rated 라운드였어도 신중하게 제출하지 않았을 것 같아서 조금 주의할 필요가 있을 것 같다. A. Special Permutation p[i] != i 를 만족하는 순열을 만드는 것이다. 1, 2, ... n 순서대로 구성된 순열을 한 칸씩 밀기만 하면 만족한다. #include using namespace std; int main(void) { ios::sync_with_stdio(false).. 2020 CPC (중앙대 프로그래밍 경진대회) Open contest 후기 및 풀이 2020 중앙대학교 프로그래밍 경진대회 (CPC) open contest에 참여했다. 본 대회랑 동시에 진행되었는데, 중간에 백준 사이트가 한 시간 정도 터져서 대회 주최자분들이 매우 안타까웠다.... 대회의 초반 절반정도는 거의 다 구현 문제였다. 그런데 생각보다 구현하기가 까다로워서 스코어보드 상에서도 많은 WA를 볼 수 있었다. 나도 제대로 말려버렸다 ㅠ [대회 문제] : www.acmicpc.net/category/detail/2345 [스코어보드] [풀이] (20.11.24 기준 난이도) A. 교수님 그림이 깨지는데요? (Bronze 1) - 문제에서 시키는대로 하면 된다. 가로로 K배, 세로로 K배의 개수만큼 출력해주면 된다. #include using namespace std; int A[1.. [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) 이 문제는 코드나 풀이가 상당히 간단하지만, 생각해내기가 쉽지 않은 문제이다. 우선 오일러 회로 개념에 대한 이해가 필요하다. 짧게 설명하면, 무향 그래프에서 그래프의 시작점으로부터 출발해서.. 이전 1 2 3 4 5 6 7 다음
