트라이 (3) 썸네일형 리스트형 [C++] 개미굴 백준 14725번 삼성 프로를 따기 위해 다시 알고리즘을 열심히 해야겠다 아직 수업을 안들어서 뭘 할까 하다가 백준 알고리즘 분류에서 내가 좋아하는 트라이를 골라서 풀어봤다 이 문제는 개미들이 타고 내려간 정보를 보고 개미굴의 전체 모습을 파악하는 문제 전형적인 트라이라기 보다는 트라이를 알면 쉽게 풀 수 있는 문제였던 것 같다 map과 vector를 사용하면서 프로 시험에 이제 stl 허용인것이 행복했다 노드별로 string을 키로 갖고 노드 포인터를 value로 갖는 map을 만들어주었다 로봇개미가 찾은 경로는 insert 함수를 재귀적으로 불러 차례차례 넣어주었다 이때 이미 한 번 이상 찾은 경로는 map에서 찾아서, 처음 가는 경로는 새로운 노드를 만들어 재귀함수를 불렀다 출력 또한 재귀적으로 함.. [C++] 프로그래머스 전화번호 목록 삼성기출만 풀다가 시뮬레이션만 연습하나 싶어서 프로그래머스 코딩테스트 고득점 Kit을 풀어보기로 했다 해시부터 차례로 풀어보려했는데 이 문제는 보자마자 해시말고 Trie로 푸는 방법이 생각나서 그냥 트라이로 풀어보았다 구현도 쉽고 효율성도 좋아서 알고리즘 풀때 쓰기 좋아하는 자료구조 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include #include using namespace std; class Trie{ public: Trie* child[10]; bool isTerminal; Trie(){ for(int i = 0 ; i child[.. [C++] 백준 5052번 : 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록.. 이전 1 다음