본문 바로가기
반응형

전체 글

 (168)
DISJOINT-SETS, MST MST(최소 신장 트리) MST의 목적 낭비를 줄이고 최적의 비용으로 모두를 연결하기 위함 그리디한 기법을 쓴다. 팩토리얼 보다 적게 만들기 위해서 쓴다. 모든 경로의 합이 최소를 찾기 위해서 쓴다.(나중에 나올 다익스트라와 용도가 다르다.) MST를 만들기 위한 기법은 두가지 프림, 크루스칼 프림 disjoint-sets을 기반으로 깔고 들어간다. 크루스칼 크루스칼에서 다음 노드를 선택했을 때 그 노드를 union한다. 또한 사이클이 발생할 수 있는 경우를 방지한다. 트리이기 때문에 사이클이 발생하지 않아야 한다. 간선이 많으면 터진다. 간선이 적으면 크루스칼, 간선이 많으면 프림 DISJOINT-SETS 서로소 집합을 의미한다. 각 집합의 부모 노드를 가지고 있고 부모 노드가 다르면 다른 집합을 의미..
[백준] 17471번 게리맨더링 17471번 게리맨더링 1. 이해하기 선거구를 둘로 나누는데 나눠진 각 선거구끼리는 연결이 되어야한다. 선거구가 둘로 나눠졌으면 그 중에 선거구의 인구수의 차이가 최소가 되는 때를 찾아야 한다. 완전 탐색과 bfs를 이용하는 문제 2. 구현하기 select(index,cnt,limit) index를 N+1까지 증가시키면서 그 때의 index를 선택하는 경우와 선택하지 않는 경우로 나눈다. 그리고 그 때의 결과를 비교해 최솟값을 반환한다. index가 N+1에 도달하고 선택한 갯수가 limit이라면 그 경우가 선거구로 나누는 것이 가능한 경우인지 판단한다. 가능하다면 선택된 선거구와 아닌 선거구로 나누어 합을 구하고 그 합들의 차이를 반환한다. 가능하지 않다면 MAX값을 반환한다. static int se..
BFS 거리 구하기 팁 package test; import java.util.LinkedList; import java.util.Queue; public class Test03_BFS_dist { static int N; static boolean[] visited; static int[][] map; static void bfs(int start) { Queue q = new LinkedList(); q.add(start); visited[start] = true; int dist = 0; while(!q.isEmpty()) { int size = q.size(); for(int s = 0; s < size; s++) { int now = q.poll(); for(int i = 1; i
[백준] 2660번 회장뽑기 2660번 회장 뽑기 1. 이해하기 자신을 기점으로 가입한 회원이 얼마나 멀리 떨어져있는지를 구하는 문제이다. bfs를 이용하여 문제를 풀 수 있다. dfs로는 힘든 것이 사이클이 발생할 경우 제일 깊은 노드가 무엇인지 찾기 힘들기 때문이다. 2. 구현하기 먼저 현재 위치와 얼마나 멀리 떨어져있는지를 저장할 Pair 클래스를 선언한다. static class Pair { int x, depth; Pair(int x, int depth) { this.x = x; this.depth = depth; } } bfs(start) bfs를 이용하여 자신과 얼마나 멀리 떨어져 있는지를 구한다. 한번 멀어질 때마다 현재 depth+1을 기록해줘서 가장 멀리 떨어진 사람의 depth가 몇인지 구해준다. static v..
[백준] 1248번 맞춰봐 1248번 맞춰봐 1. 이해하기 설명은 길게 되어 있지만 결국은 N개의 숫자를 선택하는 문제이다. 하지만 부호를 잘 맞춰야 하는 문제이다. 완전 탐색과 백트랙킹으로 풀 수 있다. 2. 구현하기 solve(index) index를 N까지 진행해보며 N에 도달했다면 true를 반환한다. 0 ~ 20 부터 반복하면서 result배열에 하나씩 넣어본다. 이때 -10을 하고 넣어줘서 -10 ~ 10의 구간을 만들어준다. 이때 가장 중요한 것은 추가를 했을 때, 바로 가능한 경우인지를 비교해줘서 체크를 해야 시간 초과 등의 문제를 피할 수 있다. static boolean solve(int index) { if(index == N) return true; for(int i = 0; i = 0; i--) { sum ..
[백준] 1918번 후위표기식 1918번 후위표기식 1. 이해하기 중위 표기식을 후위 표기식으로 바꾸는 문제. 스택을 어떻게 사용하는지 알아야 하는 문제이다. 2. 구현하기 현재 값이 알파벳이라면 출력하는 배열에 넣어준다. 현재 값이 +,- 라면 ( 이외의 연산자는 모두 빼고 출력하는 배열에 넣어준다. 그 이후 스택의 가장 윗부분에 현재 값을 넣어준다. 현재 값이 *,/ 라면 +,-,( 이외의 연산자는 모두 빼어 출력하는 배열에 넣어준다. 이후, 스택의 가장 윗부분에 현재 값을 넣어준다. 현재 값이 ( 라면 스택의 가장 윗부분에 넣는다. 현재 값이 ) 라면 ( 이 나올 때까지 빼어 출력하는 배열에 넣어준 후, (를 빼버린다. package algo; import java.util.Scanner; public class Acm1918_..
[자바] String String Stirng의 +연산은 메모리 내부에서 String객체 값이 바뀌는 것이 아니고 StringBuilder를 통하여 연산을 하고 String값으로 다시 반환을 하기 때문에 효율적이지 않다.(메모리 초과가 발생하는 가장 큰 요인이 될 수 있다.) 따라서 연산이 자주, 많이 일어나는 경우에는 StringBuilder를 이용하는 것이 바람직하다. StringBuilder 사용 가능한 메소드 append(String s): 가장 마지막에 s를 추가한다. insert(int offset, String s): offset위치에 s를 추가한다. reverse(): 순서를 바꾼다. 현재 StringBuilder에 영향을 미친다. setCharAt(int index, char c): index의 문자를 c로 ..
[백준] 17070번 파이프 옮기기1 17070번 파이프 옮기기1 1. 이해하기 파이프를 N,N으로 옮기는 경우의 수를 구하는 문제이다. DFS를 이용하여 구할 수 있다. 참고로 DFS에 DP를 추가하여 구할 수도 있다. 시간을 단축시킬 수 있다. 2. 구현하기 dfs(x,y,prev) 현재 위치와 이 전에 어떤 방향으로 있었는지를 받는다. 이를 이용해서 파이프가 어떤 모양으로 이어질 수 있는 지를 구한다. static int dfs(int x, int y, int prev) { if(x == N-1 && y == N-1) return 1; int ret = 0; for(int i = 0; i < 3; i++) { if((prev == 0 && i == 2) || (prev == 2 && i == 0)) continue; int nx = x..

티스토리툴바