Brute-Force

출처 Programmers 불량 사용자(2019 카카오 개발자 겨울 인턴십) 접근 문제 분석 주어진 응모자 아이디에서 불량 사용자가 될 수 있는 모든 경우를 탐색하는 완전탐색(Brute Force) 문제입니다. 시간복잡도 분석 주어진 사용자 아이디와 조합의 개수가 n <= 8 이므로, 모든 경우를 선택하는 시간복잡도는 불량 사용자 조합의 크기인 8! = 40,302 가 됩니다. 또한, 모든 사용자와 조합을 각각 1회씩 비교할 경우 시간복잡도는 8 x 8 = 64입니다. 따라서 완전탐색을 구현하기만 하면 시간복잡도는 충분함을 알 수 있습니다. ...

출처 https://school.programmers.co.kr/learn/courses/30/lessons/84512 접근 단어의 길이가 5 이하이기 때문에, 완전탐색을 해도 시간복잡도가 초과되지 않습니다. 각 단어 Idx별로 단어를 1개씩 선택하는 경우의 수 이므로 O(N^N) = 5^5 입니다. 단어사전을 탐색하다가, 주어진 문자열과 동일한 단어일 때의 크기를 반환하면 됩니다. 단어사전에 부모노드부터 나오기 때문에(A -> AA -> …), PreOrder DFS1로 단어를 탐색합니다. 중간에 해당 단어가 나오면 탐색을 중단하여 최적화합니다.2 백트래킹3에서 자주 사용하는 기법으로, 재귀 탈출조건에서 값을 반환(아래 예시에서는 boolean)하여 탐색 종료여부를 결정할 수 있습니다. ...