Dev_Diary

https://www.acmicpc.net/problem/17435 17435번: 합성함수와 쿼리 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는 www.acmicpc.net 희소 배열에 관한 기본문제입니다. 기본적으로 희소 배열이란 어떤 구조를 탐색할 때 탐색 시간을 줄이기 위한 방법으로, 2^n 에 대한 정보를 미리 기록해놓고 이를 더 작은 2^m 으로 쪼개어 탐색합니다. 이 문제에서는 f(x) 를 중첩시키는 형태로 사용하게 되는..

https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net LCA 알고리즘의 개념문제입니다. 보통 희소배열 알고리즘을 통해 개선된 LCA 알고리즘을 구현하지만 이분탐색 알고리즘을 통해 구현해보고 싶었습니다. 다만 이분 탐색을 위해 모든 노드의 모든 조상을 기록하면 메모리 초과 문제가 생기므로 DFS를 통해 노드의 깊이를 잴 때 마지막 노드만의 조상을 기록했고 각 조상노드들의 최하위 노드를 기록해 조상 노..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬 알고리즘입니다. 다만 큐를 사용한 BFS 방식이 아닌 진입차수가 0 인 노드 하나 추가 -> 연결된 모드 노드 진입차수 -1 -> 진입차수가 0 인 노드 하나 추가 가장 작은 노드가 입력될 수 있도록 해야합니다. import sys def solution(N, M, data_list): # 위상정렬 알고리즘 # 트리, tree[i] = [[i 의 자식들], ..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬을 사용해 풀어야 하는 문제입니다. 우선 바뀐 순서를 트리에 추가하고 나머지 순서는 바뀌면 안되므로 미리 추가된 순서들을 제외하고 트리에 추가해줍니다. 그런 뒤에 위상정렬 알고리즘을 사용하면 되는데, 큐에 노드가 2개 이상 들어있다면 정확한 순서를 파악할 수 없으므로 '?' 를 출력합니다. 또 위상정렬 알고리즘을 모두 통과한 뒤에 생긴 새로운 줄에 속한 노드의 수가 전체 노드의 수와..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬 알고리즘을 사용하면 풀 수 있습니다. 간단하게 설명하자면 어떤 노드를 방문하는데 조건이 있는 경우 위상정렬을 사용하게 됩니다. 특정 노드 A 를 방문할 때 B, C 를 선행 방문해야 한다고 가정하겠습니다. A와 B, A 와 C를 간선으로 연결하고, 각 노드에서의 들어오고 나가는 간선을 체크해줍니다. A : 나가는 간선 0 / 들어오는 간선 2 ..

https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 트라이 자료구조를 사용해 풀 수 있는 문제였습니다. 처음에는 현재 노드의 자식이 하나면 카운트를 스킵했지만 어떤 단어의 부분집합이 함께 사전에 포함되어 있는 경우, 예를 들어 hello 와 hell 이 같은 사전에 포함되어 있는 경우, hello 의 버튼 클릭 횟수를 카운팅 할 때 o 를 자동으로 누르게 되어 카운팅이 제대로 되지 않습니다. 그러므로 자식의 수 + (value 가 존재할 때 1 / va..

https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 해시를 사용하면 조금 더 쉽게 풀 수 있는 문제지만 트라이 자료구조 학습을 위해 트라이로 풀어보았습니다. def solution(N, M, S, data_list): # 트라이 trie = Trie() # 데이터 입력 for string in S: # 트라이 insert 함수 trie.insert(string) # 집합에 포함되는 데이터 수 data_count = ..

https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net 트라이, Trie 라는 자료구조를 사용하는 기본 문제입니다. 트리 구조를 사용해 문자열 검색에 최적화된 자료구조 입니다. dev-diary 라는 문자열을 저장한다고 하면 d, e, v, - , d, i, a, r, y 를 순서대로 하위노드로 입력시키며 특정 문자열로 시작하는 문자열을 검색하기 쉽게 만듭니다. 구현은 클래스로 구현할 수 있으며 기본 구현과 문제를 위해 변형한 코드를..

https://www.acmicpc.net/problem/1305<figure id="og_1703250997520" contenteditable="false" data-ke-type="opengraph" data-ke-align="alignCenter" data-og-type="website" data-og-title="1305번: 광고" data-og-description="세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐..

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP 알고리즘을 사용하는 기본적인 문제입니다. 다만 시간 제한도 빡빡하고 KMP 알고리즘 자체의 난이도 때문에 플레티넘이 되어버린 문제입니다. 또 입력이 ' ' 처럼 공백으로 들어올 경우 입력을 받을 때 strip 처리를 해버리면 인덱스 오류가 날 수 있으므로 주의해야 합니다. 아래 코드에 디버깅 코드가 삽입되어 있으므로 복사해서 그래도 돌려보면 터미널에 과정이 나옵니다. 이를 코드와 비교..