출처 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 구현 구현에 도움이 되는 두 가지 스킬을 설명드리겠습니다. ...
출처 https://school.programmers.co.kr/learn/courses/30/lessons/131701 접근 원소의 길이가 1,000 이하이기 때문에 N^2 알고리즘을 사용해도 풀이가 가능합니다. 각 수열의 시작점에서 인덱스를 1칸씩 증가시키면서 합의 가지수를 찾는 문제입니다. 인덱스는 원형으로 연결되어 있기 때문에, 전체 수열의 길이보다 큰 인덱스는 다시 0부터 시작해야 합니다. 원형 배열을 구현하기 위해 다음과 같이 modular연산을 사용하면 쉽게 구현이 가능합니다. 예시에서 주어진 수열 [7, 9, 1, 1, 4]에서 원형 배열을 더하는 방법을 알아보겠습니다. 현재 값이 9(idx == 1)일때 이후의 값들은 다음과 같습니다. 현재 값이 9일 때, 이후의 값 위치 ...
출처 https://www.acmicpc.net/problem/16236 접근 알고리즘 시작지점부터 가장 가까운 물고기부터 탐색합니다. 문제 조건에서 주어진 물고기를 선택하는 기준을 만족하기 위해, Heap1에 다음 물고기를 넣어 정렬하였습니다. 다음 물고기가 먹을 수 있는 물고기라면, 해당 위치를 시작점으로 다시 BFS를 수행합니다. 시간복잡도 고민 BFS로 물고기를 먹으러 이동하면서 걸리는 시간 : O(N^2) 이동하면서 물고기를 정렬하는 시간(Priority Queue 사용 시) : O(NlogN) N = 20 이므로 시간복잡도 내 충분히 가능하다고 판단했습니다. 유의사항 PriorityQueue를 정렬할 때, Integer의 유틸리티 메서드인 compare()를 활용하면 좋다고 합니다.2 물고기를 먹은 뒤 해당 위치에서 BFS를 다시 수행하기 위해 방문 배열을 초기화하는 로직이 필요합니다. 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /* * [조건] * 시간 제한 : 2초 / 메모리 제한 512MB * [풀이] * 오른쪽 아래부터 역으로 공간을 돌면서 가장 가까운 물고기의 위치를 확인한다.(N^2) * 해당 물고기를 먹으러 이동하면서 걸리는 시간을 측정한다.(N^2) * 더이상 이동할 수 없거나, 모든 칸이 빌때까지 이를 반복한다(N^2) * => N^6 = 20^6 = 32 x 10^6 이므로 시간복잡도 내 가능 * 시작지점부터 가장 가까운 물고기를 탐색한다. * 해당 지점까지 bfs로 이동하여 해당 지점이 나오면 걸린 시간을 현재시간에 더한다. * 더이상 이동이 불가능하다면 현재 시간을 출력한다. * 이동이 가능하다면 먹은 횟수를 더하고, 먹은 횟수가 상어의 크기만큼 쌓이면 상어 크기를 1 늘린다. */ public class bj_16236_아기_상어 { static int N, eatCount, size = 2; static int[] start; static int[][] space; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); space = new int[N][N]; start = new int[2]; for (int i = 0; i < N; i++) { StringTokenizer st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) { int now = Integer.parseInt(st.nextToken()); if (now == 9) start = new int[]{i, j}; space[i][j] = now; } } System.out.println(bfs()); } // 먹을 수 있는 물고기가 더 없을떄까지 bfs 이동 static int[] dr = {-1, 0, 0, 1}; static int[] dc = {0, -1, 1, 0}; private static int bfs() { boolean[][] visited = new boolean[N][N]; // 우선순위 큐 : 거리 > 위 > 왼쪽 순으로 내부 정렬 PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> { if (o1[2] != o2[2]) return Integer.compare(o1[2], o2[2]); // Integer.compare() 메서드 활용 if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]); return Integer.compare(o1[1], o2[1]); }); int ret = 0; q.offer(new int[] {start[0], start[1], 0}); visited[start[0]][start[1]] = true; while (!q.isEmpty()) { int[] now = q.poll(); // 자신보다 작은 물고기를 만났을 때 : 해당 물고기를 먹은 후 큐를 비우고 다시 bfs 시작 int fish = space[now[0]][now[1]]; if (fish != 0 && fish < size) { if (++eatCount >= size) { size++; eatCount = 0; } // 이동시간 갱신 ret += now[2]; // bfs 초기화 + 방문배열 초기화 q.clear(); q.offer(new int[]{now[0], now[1], 0}); for (int j = 0; j < N; j++) Arrays.fill(visited[j], false); visited[now[0]][now[1]] = true; // 공간 변화 : 아기상어 위치 이동 + 최초위치 아기상어 칸 비우기 space[now[0]][now[1]] = 9; space[start[0]][start[1]] = 0; start = new int[]{now[0], now[1]}; continue; } for (int i = 0; i < 4; i++) { int nr = now[0] + dr[i]; int nc = now[1] + dc[i]; if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue; if (visited[nr][nc] || space[nr][nc] > size) continue; visited[nr][nc] = true; q.offer(new int[] {nr, nc, now[2] + 1}); } } return ret; } } 결과 ...