본문 바로가기
반응형

알고리즘

 (136)
[백준] 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_..
[백준] 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..
[백준] 16637번 괄호 추가하기 16637번 괄호 추가하기 1. 이해하기 왼쪽부터 차례대로 계산한다. 연산자의 우선순위는 괄호만 신경쓴다. 괄호를 추가해도 되고 안해도 된다. 완전 탐색의 문제이다. 2. 구현하기 solve(index) index를 이용하여 현재 위치에 괄호를 추가하는 방법과 추가하지 않고 넘어가는 방법으로 모든 방법을 살펴보고 그에 따른 값을 계산하였다. static int solve(int index) { if(index == str.size()) { int sum = 0; int idx = 0; while(idx < str.size()) { if(str.get(idx) == '(') { int cur = 0; int a = str.get(idx+1)-'0'; char op = str.get(idx+2); int b..
[백준] 9935번 문자열 폭발 9953번 문자열 폭발 1. 이해하기 폭발 문자열이 발견되면 그 문자열을 없애버려야 한다. 스택의 개념을 쓰는 문제이다. 가장 중요한 String +연산은 시간과 메모리가 많이 쓰인다는 것을 알아야 한다. 2. 전체 코드 주석의 코드를 실행하면 시간이 오래 걸린다. 그 이유가 모든 문자에 대해서 print를 하는데 시간이 걸리기 때문이다.(추측) 이를 줄이기 위해서는 StringBuilder를 사용하면 된다. package algo; // //import java.io.BufferedReader; //import java.io.IOException; //import java.io.InputStreamReader; // //public class Acm9935 { // static char[] cStk =..

티스토리툴바