dev-hunmin

www.acmicpc.net/problem/9997 9997번: 폰트 첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다. www.acmicpc.net - 접근법 N이 25이므로 브루트포스로 모든 단어를 조합해도 O(2^25)로 가능하다. 그러나 탐색과 연산횟수도 합해진다면 O(2^25*alpha)로 TLE가 날수있으므로 가지치기를 잘해줘야한다. 사실 이 문제는 비트마스킹으로 해당 알파벳이 존재하면 TRUE, 안하면 FALSE같이 저장해서 간단히 비트연산으로 알파벳 26개 다 존재하는지 볼 수 있다. 하지만 나는 당시에 파이썬으로 비트마스킹하는법을 몰라서 처음에 단어들을..

www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net - 접근법 행렬 제곱 문제이다. 직접 행렬 계산하는 방식으로 분할 정복 개념을 추가해 제곱하는 횟수를 logM (M=제곱횟수)만으로 행렬의 M제곱을 얻으면 된다. https://greeksharifa.github.io/algorithm%20&%20data%20structure/2018/07/04/algorithm-matrix-power/#%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 위의 게시글에 굉장히 ..

www.acmicpc.net/problem/1501 1501번: 영어 읽기 첫째 줄에 사전에 있는 단어들의 개수 N(0 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄에 하나씩, 영어 사전에 있는 단어들이 주어진다. 각 단어의 길이는 100자를 넘지 않는다. 다음 줄에 www.acmicpc.net - 접근법 주의) 이 문제에서 N개의 단어가 주어지고 M개의 해석할 '문장'이 주어진다. abcde와 같은 단어는, abcde, abdce, acbde, acdbe, adbce, adcbe 같은 단어들로 해석될 수도 있다. 결국 문자의 첫 글자, 마지막 글자가 같고 이것을 제외한 문자들의 존재 빈도가 같으면 같은 단어로 해석될 수 있다. 이 문제는 단어가 10000개, 그리고 길이가 100자까지..

www.acmicpc.net/problem/6581 6581번: HTML 원래의 HTML 문서가 입력으로 주어진다. 이 텍스트는 단어와 HTML 태그들로 이루어져 있으며, 태그는 한 개 이상의 공백문자나 탭, 개행 문자 등으로 구분된다. 단어는 연속된 알파벳, 숫자, 또는 www.acmicpc.net - 접근법 입력 받는 부분이 제일 까다로웠던 간단한 문자열 구현문제. 입력의 끝은 개행문자가 아닌 Ctrl+D로 끝난다. 전체 문자를 받고, 그것들을 단어별로 나누고 연속된 공백은 한개의 공백으로 처리하여 리스트에 저장한다. 그 후 리스트 요소들을 순차적으로 탐색하면서 태그를 만나면 즉시 태그에 해당하는 출력을 갱신하고, 단어들이라면 단어들을 연결시켜주면서 담겨있는 문장의 길이가 80이 넘으면, 넘기전으로 ..

www.acmicpc.net/problem/1298 1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net - 접근법 각 노드들이 선호하는 방번호가 있고 최대한 많은 노드들을 각기 다른 방에 1개씩 넣는 법을 묻는 문제이다. 즉, 단순한 이분매칭으로 해결할 수 있다. 문제에서 주어진 노드들의 개수(N)도 100으로 여유있고 간선들의 개수(5000)도 여유있으므로 단순하고 빠른 DFS로 해결할 수 있다. 로직은 간단히 말하면, 탐색하는 노드가 선호하는 방 번호에 '비어'있다면 바로 매칭시켜주고 누가 점거하고 있다면..

www.acmicpc.net/problem/2376 2376번: 단말 정점들의 거리 첫째 줄에 단말 정점의 개수 n(2≤n≤1,000)이 주어진다. 다음 n-1개의 줄에는 차례로 1, 2번 단말 정점 사이의 거리, 2, 3번 단말 정점 사이의 거리, …, n-1, n번 단말 정점 사이의 거리가 주어진다. 다 www.acmicpc.net - 접근법 이진 트리에서 각 단말 정점들의 거리를 가지고 트리 전체를 복원하는 문제이다. 이진 트리는 부모가 자식을 항상 2개씩(왼쪽노드,오른쪽노드)를 가지기 때문에, 단말 정점들의 거리에서 거리가 2인 경우가 항상 존재한다. 단말 정점의 거리가 2라는 것은 같은 부모(조상)을 가지고 있다는 얘기이므로, 이 두 단말 노드들을 공통된 부모(조상)으로 묶어주고 그 노드를 다시..