hotamul의 개발 이야기

url: https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 풀이 핵심 1. Trie 자료구조를 활용한다. 2. Trie root에 문자열을 insert 할 때 문자 ('a' ~ 'z') 가 나온 수를 각 문자마다 체크 한다. ex) "hello", "hell" - "hello" insert하고 난 뒤 - "hell" insert하고 난 뒤 3. search 할 때 post_cnt와 비교하면서 버튼 누를 횟 수를 증가 시킨다. (post_cnt와 다음 ..

url: https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 풀이 핵심 (HashTable 구현 참고) 1. S 집합 문자열 hashTable에 저장 2. find 함수로 hashTable 검색 코드 #define MAXN10000 #define MAX_TABLE10007 #define MAXL26 typedef unsigned long long ull; #include ull getHashCode(const cha..

url: https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 핵심 1. 문자열 처리 문제로 접두어를 이용해 자료구조를 만들어야 하므로 Trie 자료구조 사용 2. Trie에 번호들을 저장, 탐색하고 문자열이 끝나기 전 isTerminal이 true일 경우 접두어가 존재하는 것이므로 false를 반환한다. 코드 #include #include #define MAX_N10000 #define MAX_L11 int charT..

url: https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 풀이 핵심 1. 상어가 벽을 만났을 때 방향 전환을 쉽게 하기 위해 dr, dc 배열과 GetReverseDir 함수를 이용한다. const int dr[] = { 0,-1,1,0,0 }; const int dc[] = { 0,0,0,1,-1 }; // 1-->Up, 2--> Down, 3-->Right, 4-->Left int GetReverseDir(int idx)..

url: https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 핵심 1. BFS 활용 가장 가까운 물고기를 먹으러 간다 2. 우선 순위 큐 활용 (algorithm 헤더의 sort() 함수를 이용) 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다. 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. 거리가 가장 가까..