본문 바로가기
반응형

알고리즘

 (136)
투 포인터 투 포인터 1차원 배열이 있고 두개의 포인터를 이용해 원하는 값을 찾아내는 알고리즘이다. 가장 대표적은 예로는 N개의 수에서 합 M의 개수를 찾는 문제이다. 포인터로 사용할 s,e와 합을 저장할 S가 있다고 한다면 이론적으론 다음과 같다. 1. S >= M 이면 S -= A[s++] 2. e == N 이면 break 3. S < M 이면 s += A[e++] 4. S == M 이면 ans++ 이 과정을 거쳐서 M의 개수를 찾는 방식이다. 그림과 같이 이해하면 다음과 같다. 처음은 다음과 같다. 초록색 화살표를 s, 파란색 화살표를 e라고 한다면 처음은 0에서부터 시작한다. 현재 S값이 M보다 작기 때문에 3번 과정이 수행된다. 지금 상태는 S == M인 상태이다. 그렇기 때문에 ans를 4번이 실행되고 ..
[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) * 현..
JAVA EOF 판단 Scanner while(sc.hasNextInt()) { sc.nextInt(); } while(sc.hasNextLine()) { sc.nextLine(); } BufferedReader BufferedReader br = new BufferedReader(new InputStreamReader(System.in); String input = ""; while((input = br.readLine()) != null) { } 만약 입력의 끝이 주어지지 않고 계속 받는다는 문제가 나오면 이렇게 쓰면 된다. 문제 예시 http://boj.kr/3745 3745번: 오름세 문제 주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다. 정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보..
구간 트리(세그먼트 트리) 세그먼트 트리 저장된 자료들을 적절히 전처리해 그들에 대한 질의들을 빠르게 답할 수 있도록 하는 방법이다. 구간 트리의 기본적인 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것이다. 구간 트리의 루트는 항상 배열의 [0,n-1]을 표현한다. 구간 트리에서 질의에 응답하는 시간복잡도는 O(logn)이다. 구간 트리에서 구간을 모두 저장하기 위한 배열의 길이는 n이 2의 거듭제곱이라면 2n이면 된다. 그렇지 않다면 가장 가까운 2의 거듭제곱으로 n을 올림한 뒤 2를 곱해야 한다. 하지만 간단한 방법으로 4n으로 배열의 길이를 잡으면 된다. 메모리가 낭비된다는 단점이 있지만 편리하게 쓸 수 있다. 구간 트리 초기화 static long init(int node, int s, int e) { i..
다익스트라,벨만포드,플로이드 워샬 다익스트라 한 정점에서 다른 정점까지 최소로 가는 경로를 구하는 최단 경로 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식. 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재한다. 이때, 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지의 최단 경로로 구성된다. 음의 가중치가 있을 경우 사용하지 못한다. 시간복잡도는 일반적으로 O(V^2), 우선순위큐를 사용한다면 O(ElogV)이다. 동작과정 1. 시작 정점을 입력 받는다. 2. 거리를 저장할 D배열을 무한대로 초기화 한 후 시작점에서 갈 수 있는 곳의 값은 바꾼다. 3. 아직 방문하지 않은 점들이 가지고 있는 거리 값과 현재 정점에서 방문하지 않은 정점까지의 가중치 합이 작다면 변경한다. 4..
[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 할 때 필요한 정보이기 때문이다. 맵기를 기준으로 정렬한 후 낮은 맵기부터 차례로 ..

티스토리툴바