출처 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으로 증가하는 시점의 비트 차이 ...
출처 해커 랭크 : 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 구현 구현에 도움이 되는 두 가지 스킬을 설명드리겠습니다. ...
출처 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일 때, 이후의 값 위치 ...
출처 해커 랭크 : Lego Blocks 문제 설명 영문 사이트이므로 문제를 간단히 설명하겠습니다. 다음과 같은 총 네 가지 종류의 레고 블럭이 무한히 있습니다. d h w 1 1 1 [] : 길이가 1이고, 높이가 1인 레고 블럭 1 1 2 [ ] : 길이가 2이고, 높이가 1인 레고 블럭 1 1 3 [ ] : 길이가 3이고, 높이가 1인 레고 블럭 1 1 4 [ ] : 길이가 4이고, 높이가 1인 레고 블럭 문제에서 주어지는 높이와 길이만큼 레고 블럭을 쌓으려고 합니다. ...
출처 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; } } 결과 ...