출처 수식 최대화(2020 KAKAO Internship) 접근 완전탐색(DFS) 각 연산자의 우선순위를 변경하면서 전체 탐색을 하고, 변경된 우선순위마다 수식을 계산해서 최댓값을 갱신합니다. 연산자 순서에 따라 결과가 달라지므로, 순열(Permutation)에 해당합니다. 다양한 구현방법이 있지만, 개인적으로 다양한 조건을 만족하는 순열(조합)을 빠르게 구현할 수 있는 DFS를 선호합니다. 3가지 연산자만 있으므로, 모든 경우의 수를 구해도 6가지이기 때문에 시간복잡도는 충분합니다. 후위 표기 변환(InFix to PostFix) 보통 사람이 계산을 할 때는 A + B * C의 형태로 수식을 써서 계산을 합니다. 이 때, A와 B 사이에 연산자가 있는 형태를 중위 표기(InFix)라고 합니다. ...
출처 2021 KAKAO BLIND RECRUITMENT 순위 검색 접근 와일드카드 검색 와일드카드(-) 없이 검색을 구현하는 것은 각 지원자의 속성에 코딩테스트 점수를 저장하면, 속성별로 검색이 가능하기 때문에 큰 어려움이 없습니다. 와일드카드가 없는 상황은 다음과 같이 트리 구조로 데이터를 저장할 수 있습니다. 트리 구조로 지원자 정보를 저장합니다. 리프 노드에는 리스트로 코딩테스트 점수를 저장합니다. 하지만, 문제에서 주어진 것처럼 쿼리 시 와일드카드가 나오면 모든 정보를 포함하도록 탐색을 해야 하기 때문에 이를 구현하기 위해 별도의 공간에 와일드카드 속성들을 저장해야 합니다. ...
출처 백준 개미 접근 완전탐색(DFS) 자식 방에서 부모(Root) 방향으로 DFS를 하면서 지상에 도달하는데 걸리는 시간을 확인합니다. 개미 방의 개수가 최대 10^5이므로, 최악의 경우인 방이 일렬로 나열된 경우를 고려해야 합니다.1 선형적인 DFS로는 시간복잡도가 초과할 것이라고 생각해서 BinarySearch로 최적화를 했는데, 선형으로 조상들을 탐색해도 시간초과가 되지 않는 것으로 보아 DFS 만으로도 풀 수 있을 것 같습니다. TREE + BinarySearch 문제를 다시 읽어보면 자신 부모들의 집합, 즉, 조상들을 하나씩 타고 올라가면서 갈 수 있는 최대 조상의 번호를 반환해야 함을 알 수 있습니다. ...
출처 프로그래머스 숫자 타자 대회 접근 완전탐색 이전 숫자에서 왼손과 오른손을 움직여서 다음 숫자를 누르는 모든 경우를 방문하게 되면 매번 2번씩 방문이 발생합니다. 1,000개의 숫자를 왼손과 오른손으로 모두 누르려면 2^1000의 시간복잡도가 필요합니다.1 이는 불가능하므로, 완전탐색만으로는 풀이할 수 없습니다. DP 문제에서 필요한 값은 최솟값이니, 완전탐색 중 최솟값들만을 저장하면서 계산하면 100*1000 = 10^6으로 시간복잡도를 줄일 수 있습니다. 이전 값들 중 최솟값만 저장하면서 완전탐색을 최적화합니다. 위 과정을 자세히 살펴보면, 처음 위치[l : 4], [r : 6]에서 0번 패드를 누르려면 2가지 경우가 발생합니다. 이 경우에는 중복되는 가짓수가 없으니 진행합니다. 다음 위치[l : 0, 4], [r : 6, 0]에서 1번 패드를 누르려면 각각 2가지씩 총 4가지 경우가 발생합니다. 이 경우에도 중복되는 가짓수가 없으니 진행합니다. 다음 위치[l : 1, 1, 0, 4], [r : 6, 0, 1, 1]에서 3번 패드를 누르려면 각각 4가지씩 총 8가지 경우가 발생합니다. 이 경우 더 작은 값만을 저장하여 가지치기가 가능합니다. 좀 더 자세히 살펴보기 위해, 다른 경우는 제외하고 첫번째 중복의 경우만 추적해보겠습니다. 두 경우의 총 가중치를 비교해서 작은 값만을 남깁니다. ...
출처 프로그래머스 혼자 놀기의 달인 접근 숫자 더미를 여러 그룹으로 분리한 뒤, 가장 큰 그룹과 두번째로 큰 그룹을 선택합니다. 완전탐색(DFS) DFS를 통해 숫자 더미를 여러 그룹으로 분리할 수 있습니다. 문제에서 주어진 카드의 최대 개수가 100 이하이므로, 한번씩 방문한다면 O(N)으로 해결이 가능합니다. 100개의 카드가 1개의 그룹인 경우, DFS의 최대 Depth가 100이므로 재귀 호출을 하더라도 StackOverFlow1가 발생하지 않습니다. 재귀 호출을 통해 그룹 분리하기 풀이 import java.util.*; class Solution { // 카드 그룹을 넣을 전역변수 List<Integer> group; public int solution(int[] cards) { group = new ArrayList<>(); // 방문 체크를 위한 변수 boolean[] visited = new boolean[cards.length + 1]; // 카드를 돌면서 그룹화 for (int card : cards) { // 이미 방문한 카드는 다시 방문하지 않음 if (visited[card]) continue; // DFS dfs(card, 0, cards, visited); } // 그룹이 1개면 0 반환 if (group.size() == 1) return 0; // 내림차순 정렬 후 가장 큰 그룹과 두번째로 큰 그룹 곱해서 반환 group.sort(Comparator.reverseOrder()); return group.get(0) * group.get(1); } // DFS void dfs(int now, int cnt, int[] cards, boolean[] visited) { // 이미 방문한 그룹이 다시 등장 -> 같은 사이클(그룹)이므로 그룹에 현재 개수 추가 if (visited[now]) { group.add(cnt); return; } // 방문 체크 visited[now] = true; // now에서 1을 빼줘야 배열 범위를 벗어나지 않음, 방문할 때마다 현재 그룹의 개수 1개씩 추가 dfs(cards[now - 1], cnt + 1, cards, visited); } } 결과 소요시간 7:41 ...
출처 HackerRank No Prefix Set 문제 설명 주어진 단어 집합 중 Prefix(접두사)가 존재하는 단어가 있으면 BAD SET와 함께 처음으로 접두사가 발생한 단어를 출력합니다. 그런 단어가 없으면 GOOD SET을 출력합니다. 접근 완전탐색 가장 단순한 접근은 각 단어마다 나머지 단어들을 돌면서 prefix가 존재하는지 확인하는 것입니다. 문제에서 주어진 단어의 수는 최대 10^5 이므로, O(N^2)1 이상의 알고리즘을 사용할 수 없습니다. TRIE Trie2 자료구조를 통해 단어들의 탐색을 최적화할 수 있습니다. Trie 자료구조의 형태는 다음과 같습니다. Trie 자료구조 형태 ...
출처 HackerRank New Year Chaos 문제 설명 영문 사이트이므로 문제를 간단히 설명하겠습니다. 롤러코스터에 승객들이 n명 탑승중입니다. 각자는 탑승 순서대로 번호를 부여받습니다. 롤러코스터 승객들은 앞 사람과 최대 두 번까지 순서를 변경할 수 있습니다. bribe라는 단어를 처음 보고 해석이 안됐는데 ‘매수하다’ 라는 뜻으로, 앞 사람 자리를 매수한다는 뜻인 것 같습니다. 이렇게 변경된 롤러코스터의 상태가 큐로 주어집니다. 만약 3번 이상 변경한 사람이 있으면 “Too Chaotic"이라는 문자열을 출력합니다. 그런 사람이 없다면 승객들의 변경 횟수를 출력합니다. 접근 완전 탐색? 큐의 크기(n)가 최대 10^5이므로 O(N^2) 로직은 실행이 불가능하므로 완전탐색은 불가능합니다. Greedy 현재 승객이 타고있는 지점(idx)과 갖고 있는 번호의 관계를 통해 어떻게 변경이 이루어졌는지 유추해볼 수 있습니다. ...
출처 Programmers 2개 이하로 다른 비트 접근 완전탐색 가장 직관적인 풀이는 주어진 숫자를 1씩 증가시키면서 현재 비트와의 개수 차이를 구하는 것입니다. 그러나 이렇게 풀이하면 주어진 조건에서 시간복잡도가 초과합니다. numbers[i] <= 10^15 == 2^501이므로 50개의 비트열로 표현되는데, 비트를 비교하는 과정에서 숫자가 1개 증가할 때마다 50^2 = 2500의 시간복잡도가 소모됩니다.2 규칙성 찾기 완전탐색은 불가능하니 두 비트 중 다른 지점이 2개 이하이면서 가장 작은 수를 찾는 규칙을 찾아야 합니다. 현재 숫자와 다음 숫자의 이진수의 비트차이가 커지는 순간을 생각해보면, 맨 뒤에서부터 1이 쌓여있을 때 1을 더하면 비트차이가 크게 발생합니다. 255에서 256으로 증가하는 시점의 비트 차이 ...
출처 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)하여 탐색 종료여부를 결정할 수 있습니다. ...
출처 https://school.programmers.co.kr/learn/courses/30/lessons/86052 접근 문제의 예시를 잘 살펴보면, 모든 위치에서 네 방향을 적어도 한번씩 방문하는 것을 볼 수 있습니다. 즉, 빛이 갈 수 있는 모든 경로를 탐색하면서 한번 탐색을 돌면서 방문한 경로는 같은 사이클이라고 할 수 있습니다. 이러한 사이클의 개수를 세서 정렬 후 출력하면 됩니다. 모든 경로를 탐색하는 점에서 DFS나 BFS 모두 구현이 가능합니다. 저는 DFS를 통해 빛의 경로를 따라서 탐색하는 것이 문제를 이해하는데 더 직관적이라고 생각하여 DFS로 구현하였습니다. grid의 길이가 500 이하이므로 O(N^2) 알고리즘에서 4방향 탐색 시 최대 500 X 500 X 4 = 100,000의 시간복잡도가 필요해서 재귀적으로는 풀이할 수 없습니다.1 구현 구현에 도움이 되는 두 가지 스킬을 설명드리겠습니다. ...