반응형 백준 썸네일형 리스트형 [BOJ 5670] 휴대폰 자판 [문제] www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net [난이도] - Platinum III (solved.ac 20.12.13 기준) [필요 개념] - 트라이 (Trie) [풀이] 자동 입력이 되는 순간은 현재 노드에서 끝나는 문자열이 없으면서, 자식 노드가 하나밖에 없는 경우이다. 따라서 트라이를 생성할 때 자식의 수를 저장해두고, 문자열을 탐색할 때 자식의 수가 둘 이상이거나, 현재 노드에서 끝나는 다른 문자열이 있고 자식의 수가 1이면 버튼을 눌러줘야 하.. [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.. [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) 값이다. 이를 이용하기 위해서 가중치가 주어지는 이 문제의 그래프를 조.. [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 다음
