출처 프로그래머스 봉인된 주문 접근 문제 분석 알파벳 순으로 정렬된 주문서에서 주어진 숫자(n)에 해당하는 주문서를 찾는 문제입니다. 이 때, 특정 주문(bans)이 삭제되어 있는 상태입니다. 시간복잡도 분석 주어진 숫자는 n = 10^15 인 long 타입의 숫자입니다. 따라서 해당 숫자에서 글자를 가져오는 알고리즘은 O(N)보다 작아야 합니다. 주어진 주문인 bans는 길이가 300,000이하입니다. 또한, 각 주문의 길이는 최대 11입니다. 모든 주문의 알파벳을 비교하기 위해서는 300,000 x 300,000(주문 간 비교) x 11(주문 길이) = 9x10^12 x 11 이므로 시간복잡도가 초과될 가능성이 있습니다. 따라서 전체 주문을 최대 O(NlogN)까지 확인할 수 있습니다. ...
출처 Programmers 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT) 접근 문제 분석 주어진 자물쇠와 열쇠를 이동시키고 돌려서 맞출 수 있는지 확인하는 문제입니다. 열쇠 혹은 자물쇠를 돌리는 로직과, 이동시키는 로직을 구현하면 됩니다. 문제에서 주어진 열쇠보다 자물솨의 크기가 작기 때문에, 자물쇠를 이동시키고 돌리는 식으로 구현하는 것이 더 효율적입니다. 모든 칸에 대해서 자물쇠를 돌리면서 맞추고, 이동하는 식으로 완전탐색을 진행합니다. 시간복잡도 분석 자물쇠와 열쇠의 크기는 M <= N <= 20이므로, 전체 칸의 개수는 M^2 <= N^2 <= 400입니다. ...
출처 Programmers 표 병합(2023 KAKAO BLIND RECRUITMENT) 접근 문제 분석 표 편집 프로그램의 기능을 구현해야 합니다. UPDATE : 셀 1개의 값 바꾸기, 모든 셀의 값 찾아 바꾸기 MERGE : 셀 합치기(그룹화) UNMERGE : 셀 분리하기(그룹화 해제) PRINT : 셀 1개의 값 출력하기 표의 크기가 50 x 50이고, 명령의 길이가 1000 이하이므로, 시간복잡도는 충분한 편입니다. UPDATE는 비교적 쉽게 구현할 수 있지만, 문제의 이름처럼 표 병합을 얼마나 정확하고 빠르게 구현하는지가 중요한 문제입니다. ...
출처 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) 회전 ...
출처 메두사와 전사들 접근 복잡한 문제인만큼 구현하면서 순차적으로 처리해야 할 과정이 많은데, 이에 필요한 알고리즘을 정리해보면 다음과 같습니다. 메두사의 이동경로 구현 BFS + 경로 역추적 시선 생성 배열 탐색 구현 병사 이동 및 공격 배열 탐색 구현 알고리즘 자체는 어렵지 않으나, 배열 탐색을 구현하는 과정이 복잡합니다. 메두사 이동경로 구현(BFS) 메두사가 이동하는 과정에 장애물이 있기 때문에, BFS를 통해 미로를 탐색하는 최단경로를 구해야 합니다. 또한, 이동경로를 다시 돌면서 병사들과의 상호작용을 확인하기 위해 이러한 경로를 별도 배열에 저장해야 합니다. ...
출처 수식 최대화(2020 KAKAO Internship) 접근 완전탐색(DFS) 각 연산자의 우선순위를 변경하면서 전체 탐색을 하고, 변경된 우선순위마다 수식을 계산해서 최댓값을 갱신합니다. 연산자 순서에 따라 결과가 달라지므로, 순열(Permutation)에 해당합니다. 다양한 구현방법이 있지만, 개인적으로 다양한 조건을 만족하는 순열(조합)을 빠르게 구현할 수 있는 DFS를 선호합니다. 3가지 연산자만 있으므로, 모든 경우의 수를 구해도 6가지이기 때문에 시간복잡도는 충분합니다. 후위 표기 변환(InFix to PostFix) 보통 사람이 계산을 할 때는 A + B * C의 형태로 수식을 써서 계산을 합니다. 이 때, A와 B 사이에 연산자가 있는 형태를 중위 표기(InFix)라고 합니다. ...
출처 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 입니다. 따라서 각 좌표를 한번씩 방문하는 것은 불가능하며 주어진 철도의 범위로 문제를 해결해야 합니다. ...
출처 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/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; } } 결과 ...