코드 낙서장

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

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..

문제 주소 : www.acmicpc.net/problem/2983 2983번: 개구리 공주 트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르 www.acmicpc.net 문제 확인 링크로 연결해서 풀 수 있지만 링크를 사용하는 것 자체가 인덱싱에 비하여 느리므로 그래프 형식으로 인덱스를 저장해서 풀었습니다. 풀이 개구리는 4방향 (P, P), (-P, -P), (-P, P), (P, -P) 방향으로 점프를 하기 때문에 x, y축에 대하여 식을 새워 다음과 같이 m값으로 나타냅니다. 따라서 점 x, y에서 특정 방향으로 이동하기 위해서는 x, y와 움직일 위치가 같은 m..