코딩테스트 준비 1월
백준 15650 백트래킹 문제
dfs 이용해서 각각의 node로 뻗어나가면서 배열에 순차적으로 수를 채워나가는데 정해진 길이가 되면 return 이 문제는 오름차순이라는 조건이 있어서 방문했는지 기록하고 방문했으면 담을 필요가 없다.
백트래킹 개념 까먹지 않기
import java.io.*;
import java.util.*;
public class Main{
static int N;
static int M;
static boolean[] visit;
static int[] arr;
static StringBuilder sb =new StringBuilder();
public static void dfs(int depth, int start){
if(M == depth){
for(int a : arr){
sb.append(a).append(" ");
}
sb.append("\n");
return;
}
for (int i = start; i <N; i++){
if(!visit[i]){
visit[i] = true;
arr[depth] = i+1;
dfs(depth+1,i+1);
visit[i] = false;
}
}
}
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());
visit = new boolean[N];
arr = new int[M];
dfs(0,0);
System.out.println(sb);
}
}백준 11660 누적합 문제
누적합 개념 알아두기 dp에 행과 열을 이용한 연산으로 누적합으로 저장한 뒤 원하는 배열 구할때 공식 사용해서 구하기
import java.io.*;
import java.util.*;
import java.util.stream.Stream;
public class Main{
static int x1, x2, y1, y2;
static int[][] map;
static int[][] dp;
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
dp =new int[N+1][N+1];
for (int i =1; i<=N; i++){
st = new StringTokenizer(br.readLine());
for(int j=1; j<=N; j++){
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]+ Integer.parseInt(st.nextToken());
}
}
int sum =0;
for (int i =0; i<M; i++){
st = new StringTokenizer(br.readLine());
x1 = Integer.parseInt(st.nextToken());
y1 = Integer.parseInt(st.nextToken());
x2 = Integer.parseInt(st.nextToken());
y2 = Integer.parseInt(st.nextToken());
answer = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
System.out.println(answer);
}
}
}
백준 17298 stack 활용
java의 stack 함수를 이용해서 풀었고 stack에 값이 아닌 배열의 index를 넣으면서 풀었다.
import java.io.*;
import java.util.*;
import java.util.stream.Stream;
public class Main{
static int N;
static int[] A;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
A = Stream.of(br.readLine().split(" ")).mapToInt(Integer :: parseInt).toArray();
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < N; i++){
while(!stack.isEmpty() && A[stack.peek()] <A[i]) {
A[stack.pop()] = A[i];
}
stack.push(i);
}
while(!stack.isEmpty()){
A[stack.pop()] = -1;
}
for(int i =0; i<N; i++){
sb.append(A[i]).append(' ');
}
System.out.println(sb);
}
}백준 1753 최단거리 구하기
예전에 풀어봤던 기억이 있었는데 막상 구현하려 하니 알고리즘이 제대로 기억나지 않아서 알고리즘을 이해하고 풀었다. ArrayList 배열에 각 Node와 연결되는 Node에 대한 정보를 담고 시작 지점에서 갈 수 있는 최단 거리를 업데이트하고 시작 지점과 연결된 Node에서 갈수 있는 최단 거리가 있으면 업데이트하는 방식으로 도착 지점까지 최단거리를 update해준다.
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
import java.util.stream.Stream;
public class Main{
static int V,E,start;
static int[] dist;
static ArrayList[] graph;
public static class Node implements Comparable<Node>{
int v,w;
public Node(int v, int w){
this.v = v;
this.w = w;
}
@Override
public int compareTo(Node n) {
return this.w - n.w;
}
}
public static void dijckstra(int start){
PriorityQueue<Node> pq = new PriorityQueue<>();
dist[start] = 0;
pq.add(new Node(start,0));
while(!pq.isEmpty()){
Node now = pq.poll();
int len = graph[now.v].size();
for(int i =0; i<len; i++){
Node next = (Node)graph[now.v].get(i);
if (dist[next.v] > next.w+ now.w){
dist[next.v] = next.w + now.w;
pq.add(new Node(next.v, dist[next.v]));
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
start = Integer.parseInt(br.readLine());
graph = new ArrayList[V+1];
dist = new int[V+1];
for (int i=1; i<=V; i++){
graph[i] = new ArrayList<Node>();
dist[i] = Integer.MAX_VALUE;
}
for(int i = 0; i<E; i++){
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
graph[u].add(new Node(V,W));
}
dijckstra(start);
StringBuilder sb = new StringBuilder();
for(int i = 1; i<=V; i++){
if(dist[i] == Integer.MAX_VALUE)
sb.append("INF").append("\n");
else
sb.append(dist[i]).append("\n");
}
System.out.print(sb);
}
}
백준 2805 이분 탐색 문제
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt(); // numbers of trees
int m = scan.nextInt(); // need m meters
int[] trees = new int[n]; //height of trees
int MAX = 0;
for (int i = 0; i < n; i++) {
trees[i] = scan.nextInt();
if (trees[i]>MAX) {
MAX = trees[i];
}
}
scan.close();
int low = 0;
int high = MAX;
int H = 0;
while (low<=high) {
int mid = (low+high)/2;
long count = 0;
for (int tree : trees) {
if(tree>mid)
count+= (tree - mid);
}
if (m <= count) {
low = mid + 1;
if(mid >= H)
H = mid;
}
else{
high = mid - 1;
}
}
System.out.println(H);
}
}백준 1697 bfs 문제
백엔드 개발자가 되기 위한 경험을 기록하는 블로그입니다.