코드 낙서장

5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 확인 문자열 처리, 사전 검색 문제입니다. 사전 순으로 정렬하여 dfs 탐색으로 풀 수 있지만 간단하게 트라이 자료구조를 이용해서 풀 수 있습니다. 풀이 모든 입력을 트라이 자료구조에 삽입하고 현재 단어 위치에서 갈 수 있는 문자의 종류 개수를 count 변수로 둡니다. count 변수를 활용해서 자동완성이 가능한지 여부를 구할 수 있습니다. count == 1 : 현재 위치에서 갈 수 있는 문자의 종류는 하나, 따라서 자동완성이 가능합니다. count > 1 ..

9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 확인 소수 관련 문제입니다. 범위가 10000으로 적으므로 에라토스테네스의 체 알고리즘으로 간단하게 풀 수 있습니다. 풀이 10000 이하의 수를 에라토스테네스의 채 알고리즘을 통해 소수를 미리 구해둡니다. 그 후 가장 가까운 두 소수를 찾기 위해 입력받은 수에서 2를 나눈 2개의 변수를 두고 하나는 증가, 하나는 감소하며 두 변수 모두 소수일 때 출력합니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제 확인 괄호를 기준으로 이전 길이 값이 변경되므로 스택을 활용해서 풀 수 있습니다. 풀이 배열을 따라가면서 문자마다 3가지 경우로 나눌 수 있습니다. '(' : 바로 이전의 숫자의 곱만큼 길이가 길어지므로 ary[i-1], 이전 문자열의 길이를 저장합니다. ')' : 기록해둔 스텍을 반영합니다. 문자 : 현재 길이를 +1 합니다. 스택을 재활용하기 때문에 ')' 문자를 만나면 결과를 반영한 후 stack[top]=0 으로 초기화를 해 주어야 합니다. 코..

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 문제 확인 dfs 커팅, 완전 탐색으로 풀 수 있지만 500x500 이므로 크기가 커서 효율성이 떨어지기 때문에 dfs, dp로 풀어야 합니다. 풀이 판다는 전 지역보다 옮긴 지역이 더 많은 대나무가 있어야 하므로 다음식을 항상 만족합니다. ary[ path[i][x] ][ path[i][y] ]

1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문제 확인 스트링에서 패턴 스트링을 찾는 문제는 대부분 kmp 알고리즘으로 풀 수 있습니다. 풀이 kmp 알고리즘을 그대로 적용하면 풀리는 문제입니다. 커누스-모리스-프랫 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다. 문자열 ko.wikipedia...

1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net 문제 확인 이분 매칭 그래프에서 최소 버텍스 커버 문제입니다. 풀이 백준 돌멩이 제거 문제와 동일합니다. [백준] 1867 돌멩이 제거 문제 주소 : www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째.. latter2005.tistory.com 학생과 노트북을 이분 매칭..

14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net 문제 확인 구간 업데이트 처리 문제입니다. 세그먼트 트리를 활용해서 풀 수 있지만 점 쿼리 처리에 특화된 펜윅트리를 사용하여 더욱 빠르게 풀 수 있습니다. 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)란? 이전 게시물에서는 세그먼트 트리에 대해 게시물을 올렸다. (세그먼트 트리 :: http://www.crocus.c..

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 확인 1000 x 1000 크기 이므로 완전 탐색으로 풀면 시간 초과가 나므로 dp로 풀어야 합니다. 풀이 dp 배열의 의미를 현재 위치에서 만들 수 있는 최대 크기의 정사각형으로 둡니다. 현재 위치(i, j)에서 만들 수 있는 가장 큰 정사각형은 (i-1, j), (i-1, j-1), (i, j-1)의 최솟값 + 1 이 됩니다. 그 이유는 (i-1, j-1)의 값이 뒷부분 정사각형을 채워주고 (i, j-1), (i-1, j) 값이 새로워 가로를 채워주는 역할을 하기 때문입니다. 다음의 경우 dp[i-1, j-1] = 3, d..

1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 문제 확인 dp 문제입니다. left, right를 나누어 dp를 작성하면 dp[500000][500000]이 되므로 메모리 초과가 일어나기 때문에 | left-right | 를 기준으로 dp를 작성해야 합니다. 풀이 탐색 횟수를 줄이기 위해 입력 받은 수를 정렬하고 현재 단계에서 갈 수 있는 최댓값까지 탐색을 합니다. 조각을 쌓을 때 2가지 경우로 나눌 수 있습니다. 높은 탑에 쌓기 : 높은 탑에 쌓는 경우 현재 dp[j] 를 가리키고 있으며 ..

20541번: 앨범정리 지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든 앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다. www.acmicpc.net 문제 확인 알고리즘이 필요 없는 구현 문제입니다. 풀이 주어진 문제대로 구현을 하면 간단하게 풀 수 있습니다. 앨범, 사진 모두 중복이 허용되지 않으므로 앨범은 map, 사진은 set 컨테이너를 활용해서 관리합니다. 주의해야 할 것은 rmalb을 구현할 때 앨범을 삭제하면 하위 앨범 모두 삭제가 되어 삭제한 앨범수 = 1 + 삭제할 앨범의 모든 하위 앨범, 삭제한 사진 수 = 하위 앨범들의 사진 수 가 됩니다. 이를 위해 트리 탐색을 하면 많은 시간이 걸리므로 ..