괄호 추가하기 #16637
문제 이해
- 홀수 N 길이의 수식이 주어진다
- 수식에 괄호를 넣어 만들 수 있는 최댓값을 구하라
- 괄호 중첩은 불가하다 (괄호 안에 괄호 불가)
- 괄호 안에 연산자는 단 하나만 들어간다
풀이 방식 고안
모든 가능 구역에 괄호를 사용해 봐야 수식으로 가능한 최댓값을 알 수 있기 때문에 완전탐색 문제라고 판단한다
특히 각 탐색에 수식의 최댓값을 파악하고, 현재까지의 최댓값과 비교하여 기록해야 되기 때문에 BFS보다는 DFS에 가깝다고 생각한다
개념에 대한 설명
브루트 포스는 "무식하게" 모든 경우의 수를 탐색하는 완전 탐색 기법이다
DFS와 BFS는 브루트 포스, 즉 완전 탐색 기법을 구현한다
DFS는 깊이 우선 탐색으로, 주로 재귀나 스택으로 구현한다 (본인은 재귀가 더 익숙하다)
import java.io.*;
import java.util.*;
public class Main {
static int N, M, V;
static List<Integer> dfsRoute = new ArrayList<>();
static int[] dfsVisited;
static int[][] graph;
public static void main(String[] args) throws Exception {
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
V = Integer.parseInt(input[2]);
graph = new int[N][N];
for (int i = 0; i < M; i++) {
input = br.readLine().split(" ");
int x = Integer.parseInt(input[0]);
int y = Integer.parseInt(input[1]);
x--;
y--;
graph[x][y] = 1;
graph[y][x] = 1;
}
dfsVisited = new int[N];
dfs(V-1);
for (int i = 0; i < dfsRoute.size(); i++) {
bw.append((dfsRoute.get(i)+1)+" ");
}
bw.flush();
bw.close();
br.close();
}
private static void dfs(int start) {
dfsRoute.add(start);
dfsVisited[start] = 1;
for (int i = 0; i < N; i++) {
if (dfsVisited[i] == 0 && graph[start][i] == 1) {
dfs(i);
}
}
}
}start 정점과 연결되어 있는 정점을 오름차순으로 재귀 방문하는 것을 확인할 수 있다
코드에 대한 설명
코드는 크게 세 부분으로 분류된다
- 계산 기능 구현
수식이 하나의 문자열로 입력되기 때문에 연산자 또한 char로 주어진다. 이에 대응하기 위해 두 숫자값과 그 사이의 연산자 char에 대한 계산 결과를 리턴하는 함수를 구현한다
- DFS 구현
2-(1) 베이스 케이스(재귀 중단 조건): 현재 순회 중인 인덱스가 주어진 수식의 크기보다 같거나 크면 중단한다. 배열 크기 초과 오류. 이 때 최대 연산값을 반영한다.
2-(2) 매 재귀 시도마다 다음을 수행한다
-
인덱스는 다음 호출에서 계산할 첫 숫자의 인덱스를 의미한다
-
괄호가 가능한 경우, 즉 현재 인덱스(i) 포함 2개의 숫자와 1개의 연산자가 남아있는 경우에는 괄호 계산을 시도한다. 괄호 연산에는 숫자인 i와 (i+2)번째 값과 연산자인 (i+1)번째 값이 쓰인다. 괄호 연산 결과값을 여태 계산 결과값과 함께 연산하여 재귀 호출한다. 이 때 (i+3)번째 값은 연산자이기 때문에 인덱스는 (i+4)가 사용된다. 이 호출 내에서 (i+3)을 연산자로 활용할 것이다.
-
괄호가 가능하지 않은 경우에는 일반 연산을 시도한다. 여태 계산한 값, 연산자, 그리고 현재 인덱스의 숫자를 사용해 연산하고, 함수 호출에는 다음으로 계산할, i+2번째 값 (숫자)를 담는다.
- 메인 메서드
메인 메서드는 입력과 출력을 담당하고, DFS 메서드를 호출한다
우체국 #2141
문제 이해
- N개의 마을이 일직선상에 위치해 있다 (정수로 표현)
- 각 마을에 사는 사람의 수가 주어진다
- 각 마을에 대한 (마을까지의 거리)*(마을에 사는 사람 수) 값의 합의 최소가 되는 위치를 구하라
해결 방안 고안
쉬운 문젠데 생각을 잘못해서 생각보다 오래 걸렸다. 하여튼 중요한 거는 사람 수에 대한 중앙 값을 찾는 것이다.
0에 사는 사람 2명, 100에 사는 사람 1명 있다 치면, 0이 답이다.
3명에 대한 중앙값은 2다. 2명이 사는 곳은 0이다.
코드 설명
입력은 거리 X인 마을에 사는 사람 수 A명을 long[]으로 구성하여 이 배열들을 모아 long[][]을 이루었다
최소의 정답을 구하라 명시했기에 2차 배열을 거리 값에 대해 정렬한 후, 첫 배열부터 순회했다.
순회 시도마다 현재까지의 사람 명수를 더해서 총 사람 수의 중앙값에 이르면 답을 출력했다.
센서 #2212
문제 이해
- N개의 정점을 포함하는 범위 K개를 정의한다
- 모든 범위의 합의 최솟값을 구하라
해결 방안 고안
N개의 정점을 포함하는 범위 K개를 정의해서 각 범위의 합을 최소로 만들고자 하면, 당연히 가장 멀리 떨어져 있는 정점들 사이의 거리는 제외해야 한다
제외할 수 있는 거리의 개수는 K-1개이다.
정점 배열을 오름차순으로 정렬하고, 각 정점 간 거리를 배열로 만들어 오름차순으로 정렬한다.
그러면 가장 작은 거리차부터 순회하게 되는데, 이 때 마지막 K-1개의 거리는 제외시켜 범위의 합을 최소화한다.
코드 설명
문제가 직관적이라 해결 방안이 코드가 되어버렸다
