혼종 꼬지마루

알고리즘 단톡방에 어떤분의 요청으로 stl map이나 hash를 사용하지 않고 푼 코드가 있냐고 물어보길래 trie를 사용해서 풀어보았다 1. N개의 문자열이 들어오는 순서대로 TRIE안에 넣어준다. - 이때 마지막 문자열의 길이가 끝날 때는 NODE의 end를 true로 바꾸어 노드가 끝났음(문자열의 마지막)을 표시한다. 2. 이 후 M개의 문자열이 들어오는 순서대로 N개의 문자열이 들어 있는 TRIE에 넣어 비교한다. 3. 문자열이 탐색하다가 next 문자가 NULL포인터를 가지거나, 문자열이 끝났음에도 end가 false인 경우는 그냥 리턴 4. 찾을 경우에는 dab_cnt를 하나 늘려서 리턴한다 5. check함수를 모두 빠져 나왔을 때 답을 찾은 것인지 체크하기 위한 check_num과 비교하여..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN(이 글이 문제가 될 시 삭제하도록 하겠습니다.) 이 문제도 K번째 접미어 처럼 TRIE로 풀면 된다. TRIE를 사용하는 이유는 입력과 동시에 자동으로 정렬하는 효과를 볼 수 있기 때문이다. 순회하며 순서대로 탐색하기 때문이다. 일단 입력되는 문자열을 TRIE로 만들어 준다. 순회하며 처음 방문하는 node에 check를 하며 갯수를 세준다. 이때 중복되는, 문제에서 처럼 food 의 경우는 o가 두번 나오게 되는데 node에 check 변수를 넣어주는 이유는 이 중복을 제거하기 위해서이다. 따라서 현재 방문한 노드에 check가 ..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18GHd6IskCFAZN(이 글이 문제가 될 시 삭제하도록 하겠습니다.) TRIE 유형을 다시 공부하게 되는 계기가 되었다. 접미어가 나올 수 있는 갯수가 문자열의 숫자랑 같기 때문에 그렇게 탐색에 많이 걸리지는 않는다. 입력받는 문자열을 모두 TRIE로 접미어화 시켜서 입력한다. 그 후에 문자열을 모두 끝까지 순회하면서 검색한다. 끝에 도달했을 때 숫자를 세면서 K번째가 되는 접미어를 찾는다. 순회하며 탐색할때는 vector로 구현해줘도 되고, 단순히 배열로 해줘도 되는데 간편하게 vector로 구현했다. 123456789101112131415161718..

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS(이 포스팅이 문제가 될 경우 삭제하도록 하겠습니다) 삼성 SW Test B형을 준비하면서 건드렸다가 TRIE라는 새로운 알고리즘을 공부하게 해준 문제 그냥 말그대로 TRIE를 구현하고, 조건의 문자열로 시작하는 문자열이 몇개가 되는지 반환하는 문제 다만, 문자열의 갯수를 저장하는 cnt배열을 각 노드안에 만들어서 각 문자열이 각 노드에서 몇번이나 중복되는지 검사 ex) ippp, ippx, ip와 같이 입력되고, ipp로 시작되는 것을 찾으라 할때,첫번째 노드에서 i 는 3개, 두번째 노드에서 p는 3개, 세번째 노드에서 p 는 2..

이 문제는 TRIE를 구현해서 모든 전화번호를 입력시킨 후, 하나하나 비교하면서 탐색주시면 됩니다. 전화번호 입력과 동시에 TRIE에 입력시켜 주고, 각 전화번호가 모두 포함되어 있다면 NO, 하나라도 포함되어 있지 않고 모두 다르다면 YES 이 문제를 풀면서 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 ..

블로그 시작하고 첫 포스팅... 요즘 TRIE에 빠져서 문제를 찾아서 풀어보는중에 좀 쉬운문제를 만났습니다 ㅎㅎ 이진트리를 구현하는거라 TRIE라고 하기도 뭐하고, 그냥 이분탐색과 재귀로 할 수 있는 문제지만 연습을 위해 트리를 구현해서 풀어보았습니다. 그냥 트리를 구현하면서, 각각 깊이에 도착할 때, 선언한 2차원 배열에 차례대로 각 깊이에 대한 숫자를 입력해놀고 탐색이 끝나면 출력하면 끝! 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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include #include #i..