알고리즘/백준 (70) 썸네일형 리스트형 [BOJ] 3653번 영화 수집 이해하기 영화를 한 편 보려면 해당 DVD의 위치를 찾아 뺀다. 그리고 다 본 후에는 맨 위로 가져다 놓는다. 영화 한 편을 볼 때마다 그 DVD의 위에 몇 개의 DVD가 있었는지를 구해야하는 문제이다. 구간 트리를 이용하여 문제를 풀 수 있다. 구간 트리를 만드는 아이디어는 DVD의 위치에 0 또는 1을 기록해 놓는 것이다. 이를 바탕으로 누적합을 구하는 구간 트리를 만들어서 현재 위치+1에서 맨 위까지 몇개의 책이 쌓여있는지를 구할 수 있도록 한다. 전체 코드 import java.util.Scanner; public class B3653영화수집 { static final int MAX = 200000; static int T,N,M; static int[] arr; static long[] tree.. [BOJ] 1280번 나무심기 이해하기 - 1번부터 N번까지 X의 위치에 나무를 심는다. 이때 나무를 심는 비용은 1-N-1까지의 거리의 차이의 합이다. - 이를 하나씩 써보면 다음과 같다. Ai = |Xi-Xi-1|+|Xi-Xi-2|+...+|Xi-X1| - 이는 두 가지 경우로 나눌 수 있다. - 첫번째는 현재 심으려는 위치보다 이전 경우에 심어져 있는 나무의 경우. - 두번째는 현재 심으려는 위치보다 이후 경우에 심어져 있는 나무의 경우. - 먼저 첫번째 경우는 현재 위치보다 이전 위치에 심어져 있는 나무의 수(pc) * 현재 심으려는 나무의 위치(x) - 이전 나무 위치들의 합(ps). 즉, pc*x-ps 로 나타낼 수 있다. - 두번째 경우는 이후 나무 위치들의 합(ns) - 이후 위치에 심어져 있는 나무의 수(nc) * 현.. [BOJ] 17398번 통신망분리 1. 이해하기 하나의 통신망을 Q번을 통해서 분리하는데 드는 비용을 구하는 문제이다. 통신탑 연결을 끊었는데 통신망이 나눠지지 않는다면 비용은 0이다. 통신망이 나눠진다면 나눠진 통신망이 가지고 있는 통신탑의 갯수를 곱한 값이 비용이다. 예를 들어 통신탑 연결을 끊었는데 3개의 통신탑, 3개의 통신탑 이렇게 두개의 통신망으로 나눠졌다면 3*3=9의 비용이 드는 것이다. 유니온 파인드를 이용해서 풀 수 있다. 유니온 파인드는 각 정점을 잇는 방법인데, 여기서는 각 정점을 끊는 방법이다. 역으로 생각하면 풀 수 있다. 끊는 통신탑에 대해서는 처음에 연결을 하지 않고 한번 더 역으로 방문하면서 이어주는 방법이다. 2. 구현하기 package algo; import java.util.Arrays; import .. [BOJ] 15459번 Haybale Feast 1. 이해하기 음식을 준비하는데 각 음식에는 맛과 매운 정도가 있다. 한 코스를 준비하는데 그 코스의 전체 맵기는 코스 내의 전체 요리 중 가장 높은 맵기로 결정이 된다. 코스는 연속된 음식을 말한다. 이때, 적어도 M의 맛이 되면서 준비할 수 있는 코스 중 맵기가 가장 낮은 코스를 알아내는 문제이다. 유니온 파인드를 응용해서 문제를 풀 수 있다. 각 노드의 부모를 담았던 배열에 맛을 저장한다. 맵기를 기준으로 정렬할 배열이 필요하다. 이때 이 배열이 담고 있어야할 정보는 맵기와 이 요리의 인덱스이다. 인덱스가 필요한 이유는 양 옆에 코스로 만들 수 있는 음식이 있고 그 음식과 같이 함께 코스로 나갈 수 있도록 union 할 때 필요한 정보이기 때문이다. 맵기를 기준으로 정렬한 후 낮은 맵기부터 차례로 .. [백준] 16932번 모양만들기 https://www.acmicpc.net/problem/16932 16932번: 모양 만들기 N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다. 배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자. www.acmicpc.net 1. 이해하기 0과 1로 이뤄진 배열에서 1을 하나 놓음으로 1로 이뤄진 가장 큰 영역을 찾는 문제이다. 모든 0에 1을 놔보면서 크기를 비교한다. 하지만 1을 놓고 그때마다 dfs를 수행한다면 시간 초과가 일어난다. .. [백준] 7662번 이중 우선순위 큐 1. 이해하기 자료구조 트리를 사용하는 법을 물어보는 문제이다. java에서 TreeMap을 사용한다. HashMap은 정렬이 되지 않기 때문에 Key값으로 정렬이 되는 TreeMap을 사용한다. 이때, 값이 int값을 벗어날 수 있으므로 long을 key값으로 저장해준다. 2. 전체코드 package algo; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.TreeMap; public class Acm7662_이중우선순위큐 { static TreeMap map; public static void.. [백준] 17471번 게리맨더링 17471번 게리맨더링 1. 이해하기 선거구를 둘로 나누는데 나눠진 각 선거구끼리는 연결이 되어야한다. 선거구가 둘로 나눠졌으면 그 중에 선거구의 인구수의 차이가 최소가 되는 때를 찾아야 한다. 완전 탐색과 bfs를 이용하는 문제 2. 구현하기 select(index,cnt,limit) index를 N+1까지 증가시키면서 그 때의 index를 선택하는 경우와 선택하지 않는 경우로 나눈다. 그리고 그 때의 결과를 비교해 최솟값을 반환한다. index가 N+1에 도달하고 선택한 갯수가 limit이라면 그 경우가 선거구로 나누는 것이 가능한 경우인지 판단한다. 가능하다면 선택된 선거구와 아닌 선거구로 나누어 합을 구하고 그 합들의 차이를 반환한다. 가능하지 않다면 MAX값을 반환한다. static int se.. [백준] 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.. 이전 1 2 3 4 ··· 9 다음
