Backjoon

출처 https://www.acmicpc.net/problem/17470 접근 시간복잡도 분석 문제에서 주어진 배열의 크기는 최대 100 x 100이고, 전체 연산의 개수는 2,000,000개 이므로, 일반적인 회전을 구현할 경우 시간 초과가 발생합니다. O(N) = 100 x 100 x 2,000,000 = 2 x 10^13입니다. 배열 연산 압축하기(X) 해당 접근은 잘못된 풀이입니다. 올바른 풀이는 아래를 참고하시기 바랍니다. 연산을 구현하고 배열을 돌리다 보면, 뭔가 최적화할 수 있는 것 같은 느낌이 듭니다. 상하(1)-좌우(2) 반전 2번 하면 원래 배열로 복귀합니다. 오른쪽(3) 왼쪽(4) 회전 ...

출처 백준 1005 ACM Craft 접근 완전탐색(BFS) 특정 건물이 나올때까지 각 건물들을 탐색하는 과정을 BFS로 구현할 수 있습니다. 건물 사이의 관계(간선)의 개수가 100,000이므로, 각 간선을 한번씩만 방문한다면 시간복잡도 내 풀이가 가능합니다. 위상 정렬 각 건물은 해당 건물이 지어지기 전에 특정 건물을 지어야 하는 선행조건이 있습니다. 이를 구현하기 위해 위상정렬을 활용할 수 있습니다. 위상정렬은 다음과 같이 해당 건물을 짓기 전에 선행되어야 하는 건물이 모두 지어졌는지(선행 건물의 개수가 0인지) 확인하는 과정을 통해 구현할 수 있습니다. ...

출처 백준 9202 Boggle 접근 Backtracking 특정 단어를 한 글자씩 찾아들어가면서 단어 사전에 존재하는지 확인하는 방식은 전형적인 DFS의 형태입니다. 주어진 단어의 개수가 w < 300,000 이지만 탐색해야 하는 전체 Boggle 보드의 크기가 4X4이고, 이러한 Boggle의 개수가 b < 30이기 때문에 DFS 자체는 많은 시간복잡도가 필요하지 않습니다. DFS 탐색 과정에서 다음 글자를 추가했을 때, 단어 사전에 포함된 단어를 만들 수 있는지를 빠르게 확인하여 불가능한 경우를 가지치기(pruning)한다면, 시간복잡도를 더욱 줄일 수 있습니다. 이러한 기법을 Backtracking이라고 합니다. ...

출처 백준 개미 접근 완전탐색(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가지 경우가 발생합니다. 이 경우 더 작은 값만을 저장하여 가지치기가 가능합니다. 좀 더 자세히 살펴보기 위해, 다른 경우는 제외하고 첫번째 중복의 경우만 추적해보겠습니다. 두 경우의 총 가중치를 비교해서 작은 값만을 남깁니다. ...

출처 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)과 갖고 있는 번호의 관계를 통해 어떻게 변경이 이루어졌는지 유추해볼 수 있습니다. ...

출처 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; } } 결과 ...

출처 https://www.acmicpc.net/problem/2573 접근 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 _ 10,000 _ 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색이 가능하다고 판단했습니다. 매 회마다 빙산을 녹이고, 빙산을 bfs(dfs)로 탐색해서 두 덩어리가 있는지 확인한다. 모든 빙산이 다 녹았지만 2개로 분리되지 않는 경우를 주의한다.1 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /* * [조건] * 시간제한 : 1초, 메모리 제한 : 256MV * 이차원 배열의 크기가 300^2 이하이며 전체 칸의 개수는 10,000개 이하, 각 칸의 크기는 10 이하 * [풀이] * 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 * 10,000 * 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색 * 매 회마다 빙산을 녹이고, 빙산을 bfs로 탐색해서 두 덩어리가 있는지 확인한다. */ public class bj_2573_빙산 { static int N, M, count; static int[] dr = {0, 0, 1, -1}; static int[] dc = {1, -1, 0, 0}; static int[][] pole; public static void main(String[] args) throws IOException { // 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); pole = new int[N][M]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < M; j++) pole[i][j] = Integer.parseInt(st.nextToken()); } count = 0; // 빙산을 녹이면서 두 개로 분리되는지 확인 while (!isFinished()) { melt(); count++; } System.out.println(count); } // 빙산 녹이기(녹은 값을 별도의 리스트에 저장 후 마지막에 반영) private static void melt() { List<int[]> melted = new ArrayList<>(); for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (pole[i][j] == 0) continue; int now = pole[i][j]; for (int k = 0; k < 4; k++) { int nr = i + dr[k]; int nc = j + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= M || pole[nr][nc] != 0) continue; now --; } if (now < 0) now = 0; melted.add(new int[] {i, j, now}); } } for (int[] now : melted) pole[now[0]][now[1]] = now[2]; } // 2개로 분리되었는지 확인(BFS) private static boolean isFinished() { // 두 덩이로 분리되지 않고 모든 빙산이 녹았을때 예외처리(중요) int sum = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { sum += pole[i][j]; } } if (sum == 0) { count = 0; return true; } // BFS 초기화 Queue<int[]> q = new ArrayDeque<>(); boolean[][] isVisited = new boolean[N][M]; boolean isOneBlock = false; // 한 얼음을 만날때까지 확인 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (!isVisited[i][j] && pole[i][j] != 0) { // 이미 얼음을 만났음에도 다시 만난 경우 true(빙산이 2개로 나눠짐) if (isOneBlock) return true; isOneBlock = true; // BFS를 돌면서 방문처리 q.offer(new int[] {i, j}); isVisited[i][j] = true; while (!q.isEmpty()) { int[] now = q.poll(); for (int k = 0; k < 4; k++) { int nr = now[0] + dr[k]; int nc = now[1] + dc[k]; if (nr < 0 || nr >= N || nc < 0 || nc >= M || pole[nr][nc] == 0 || isVisited[nr][nc]) continue; isVisited[nr][nc] = true; q.offer(new int[] {nr, nc}); } } } } } return false; } } 결과 ...

출처 https://www.acmicpc.net/problem/1753 접근 각 정점에서 다른 정점으로의 최솟값을 다익스트라1를 통해 구합니다. 정점으로부터 최단거리의 간선으로만 이동하기 때문에 O(ElogV) ≈ 1,200,0002으로 모든 간선을 확인하는 것이 가능합니다. 탐색하는 간선 개수를 최적화하기 위해 LinkedList로 저장합니다.3 문제에서 주어진 예제를 그래프로 표현했습니다. 그래프 1 2 3 4 5 초기화 0 INF INF INF INF 1 -> 2, 3 0 2 3 INF INF 2 -> 3, 4 0 2 3 7 INF 3 -> 4 0 2 3 7 INF 5 -> 1 0 2 3 7 INF 위와 같이 거리 배열을 초기화한 후, 각 정점의 간선들을 탐색하며 배열을 채워나갑니다. 이 때, Greedy 알고리즘인 다익스트라가 도입되는데, 각 지점에서 가중치의 최솟값인 경로만 선택하면서 목표지점까지 이동하면 최소 경로를 구할 수 있다는 것입니다. ...