출처 수식 최대화(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; } } 결과 ...