출처 Programmers 2개 이하로 다른 비트 접근 완전탐색 가장 직관적인 풀이는 주어진 숫자를 1씩 증가시키면서 현재 비트와의 개수 차이를 구하는 것입니다. 그러나 이렇게 풀이하면 주어진 조건에서 시간복잡도가 초과합니다. numbers[i] <= 10^15 == 2^501이므로 50개의 비트열로 표현되는데, 비트를 비교하는 과정에서 숫자가 1개 증가할 때마다 50^2 = 2500의 시간복잡도가 소모됩니다.2 규칙성 찾기 완전탐색은 불가능하니 두 비트 중 다른 지점이 2개 이하이면서 가장 작은 수를 찾는 규칙을 찾아야 합니다. 현재 숫자와 다음 숫자의 이진수의 비트차이가 커지는 순간을 생각해보면, 맨 뒤에서부터 1이 쌓여있을 때 1을 더하면 비트차이가 크게 발생합니다. 255에서 256으로 증가하는 시점의 비트 차이 ...
출처 해커 랭크 : Gridland Metro 문제 설명 영문 사이트이므로 문제를 간단히 설명하겠습니다. 가로등을 설치해야 하는데, 철도가 있는 지점에는 가로등을 설치할 수 없습니다. 철도는 가로로만 설치되며, 철도끼리는 겹칠 수 있습니다. 문제에는 철도의 개수(k)와 철도의 시작점(r, c1)과 끝점(r, c2)이 주어지며, 이 때 가로등을 설치할 수 있는 지점의 개수를 구해야 합니다. 접근 시간복잡도 계산 철도의 개수 k <= 1000인 반면 전체 좌표의 크기 (n, m) < 10^9 입니다. 따라서 각 좌표를 한번씩 방문하는 것은 불가능하며 주어진 철도의 범위로 문제를 해결해야 합니다. ...
출처 해커 랭크 : Non Divisible Subset 문제 설명 영문 사이트이므로 문제를 간단히 설명하겠습니다. 중복되지 않는 정수 배열(집합)이 주어집니다. 문제 예시에는 10이 중복되어 있는데 오타인 것 같습니다. K가 주어졌을 때, 두 수의 합이 k로 나누어 떨어지지 않는 부분 집합을 찾는 문제입니다. 부분 집합에서 임의의 두 수를 골라도 k로 나누어 떨어지지 않아야 하며, 부분 집합이 여러개가 있을 때는 최대 길이를 구해야 합니다. 접근 완전탐색 부분 집합을 만들 수 있는 각각의 경우에서 2개씩 고른 뒤 K로 나누어 떨어지는지를 일일히 확인하면 시간복잡도를 초과합니다. O(N! x nC_2) ...
출처 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 구현 구현에 도움이 되는 두 가지 스킬을 설명드리겠습니다. ...