알고리즘
분할 정복 알고리즘
도입분할 정복과 일반적 재귀 호출의 차이일반적 재귀 호출문제를 한 조각과 나머지 전체로 나눔분할정복문제를 항상 거의 같은 크기로 나눔 일반적 재귀 호출분할 정복분할 정복의 구성 요소divide문제를 더 작은 문제로 분할하는 과정merge각 문제에 대해 구한 답을 원래 답으로 병합하는 과정base case매우 작은 문제의 해법예제: 수열의 빠른 합과 행렬의 빠른 제곱가장 간단한 방법은 수식을 이용하여 바로 계산하는 것이다.하지만, 우리는 분할 정복 알고리즘에 익숙해지기 위해 이를 이용하여 계산해보자 1+2+…+n 의 합을 분할 정복을 이용하여 계산해보자 문제를 반으로 나눠보기1부터 n2n\over22n까지의 합과 n2+1{n\over2}+12n+1부터 n까지의 합을 구하는 문제로 나눠보자sum(n)..
유클리드 알고리즘
유클리드 알고리즘💡두 수의 최대공약수를 구하는 방법정의두 수 p, q(p>q)의 공약수 집합은 p-q와 q의 공약수 집합과 같다. 증명p, q의 공약수 g가 존재한다고 해보자그럼 다음과 같이 나타낼 수 있다.p = p’gq = q’g 이때 p-q = (p’ - q’)g 이므로g는 p-q의 약수이며, q의 약수이다. 구현위를 이용하여 코드로 구현해보자int gcd(int p, int q) { if (p < q) { int tmp = q; q = p; p = tmp; } if (q == 0) { return p; } return gcd(p - q, q); }짧은 코드로 구현이 가능하나, 위 코드를 보면 p와 q의 차이가 클 경우에 많은 연산이 이루어 질 수 있다는 단점이 있다.gcd(1024,6)=gcd(1..
소수 판별
소수 판별💡양의 약수가 1과 자기 자신 2개 뿐인 자연수소수가 아닌 수는 합성수이다.가장 단순한 방법2부터 n-1까지 모든 수를 돌면서 나머지가 0이 아니면 소수이다.조금 더 발전한 방법합성수는 n = p*q (p, q ≠ 1, n) 형태로 나타낼 수 있다. 이때 (p≤q) 일때 p는 항상 √n 이하이고 q는 항상 √n 이상이다.따라서 범위를 n-1까지가 아니라 √n 까지 줄일 수 있다.코드// 자연수 n이 소수인지 판별한다. static boolean isPrime(int n) { // 1과 2는 예외처리 if (n
플로이드 최단 경로 알고리즘
플로이드 최단 경로 알고리즘💡모든 정점 쌍에 대해 최단 거리를 구할 때 쓰는 알고리즘개요board[u][v]정점 u에서 정점 v까지의 최단거리를 저장최단 거리를 찾는 방법정점 u에서 정점 v까지 바로 가는 거리를 w(u, v)라고 하자이 때, u→a→v를 가는 거리가 u→v 거리보다 짧다면 갱신하는 방식이다.코드public class 플로이드 { static int board[][]; static void floyd() { // 자기 자신의 거리는 0 for (int i = 0; i < board.length; i++) { board[i][i] = 0; } // 거리 계산하기 for (int k = 0; k < board.length; k++) { for (int i = 0; i < board.lengt..
벨판-포드의 최단 경로 알고리즘
벨판-포드💡다익스트라의 음수 간선 문제를 해결한 최단 경로 알고리즘다익스트라와의 차이벨판-포드는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄이는 방식동작 과정upper[]시작지점으로부터 각 정점까지 최단 거리의 상한시작점→시작점의 거리는 0나머지는 매우 큰 수로 저장시작점이 아닌 임의의 두 지점 u, vdist[u]시작지점 → u 까지의 최단 거리dist[v]시작지점 → v 까지의 최단 거리이때, 다음이 성립한다.dist[v] ≤ dist[u] + w(u, v)dist[u] ≤ upper[u]upper[u] + w(u, v) ≤ upper[v]종료 조건과 정당성의 증명어떻게 upper[] 의 값을 dist[] 값으로 만들 수 있..
이진 검색 트리
1. 이진 검색 트리란?💡자료들을 일정한 순서에 따라 정렬한 상태로 저장해두는 트리사용 예시캐릭터 생성 시 특정 닉네임이 이미 저장되어있는지 확인하기나보다 1등 위인 사람과 1등 아래인 사람을 찾기 대부분 언어 표준 라이브러리에서 제공하기 때문에, 직접 구현하지 않는다.2. 이진 검색 트리의 정의와 조작2-1. 이진트리란?💡한 노드당 최대 2개의 자식 노드만 가질 수 있는 트리따라서 관련 객체 작성 시 다음처럼 구현이 된다.class Node { int data; Node left, right; }2-2. 이진 검색 트리의 특징N개의 원소 중에서 원하는 원소를 찾기까지 걸리는 시간은 다음과 같다.O(logN)O(\log{N})O(logN)시간이 logN이 걸리기 위해선 노드들이 특별한 방식으로 저장될 ..
[BOJ/JAVA] 1822번: 차집합
키워드집합 A에는 속하면서 집합 B에는 속하지 않는 모든 원소를 구하는 프로그램구현집합 연산 중 차집합 연산을 이용하여 구현한다.A.removeAll(B)A집합에는 속하지만, B집합에는 속하지 않게 A를 바꾼다.코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Set; import java.util.StringTokenizer; import java.util.TreeSet; public class java_1822 { static Set aSet, bSet; public static void main(String[] args) throws IOExcepti..
[BOJ/JAVA] 2110번: 공유기 설치
2110번: 공유기 설치도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.https://www.acmicpc.net/problem/2110키워드집에 공유기 C개를 설치가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치구현huses[] 각 집의 좌표를 오름차순으로 정렬한다.solution()인접한 두 공유기 사이의 거리를 매개변수로 이분탐색을 진행한다.초기 low는 1초기 high는 마지막원소 - 첫번째 원소 (이 때가 차이가 가장 크므로..)[low, high]에 속하면서, mid = (lo..
[BOJ/JAVA] 2343번: 기타 레슨
키워드블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다.M개의 블루레이에 모든 기타 강의 동영상을 녹화하블루레이의 크기(녹화 가능한 길이)를 최소M개의 블루레이는 모두 같은 크기구현블루레이 크기를 매개변수로하여 이분 탐색을 진행한다.lectures[]강의의 누적합low = 가장 긴 길이의 강의high = 모든 강의 길이의 합canMake()mid = (low+high)/2 의 블루레이 크기로 녹화할 수 있는지 체크0부터 누적합을 계산하며 진행한다. mid보다 커지는 순간 → 현재 인덱스의 강의를 제외한 이전 강의를 현재 블루레이에 담는다.마지막 인덱스가 아닌데, 블루레이의 수가 M이상이라면 .. false 반환반복문이 끝난 경우 → 디스크가 남는 경우디스크의 크기는 항상 한 개의 강의를 넣을만큼 충분..
동적 계획법
동적 계획법이 뭔데?분할 정복에서 중복 부분문제를 캐시(cache)를 이용하여 계산 결과를 재활용하여 속도 향상을 꾀하는 기법이다.예시피보나치 수열의 [i]번째 결과값을 출력하고싶다고 하자.해당 메소드는 fibo(i)를 이용하여 값을 얻는다.int fibo(int i){ // 기저사례 if(i == 0 || i == 1){ return 1; } if(cache[i] != -1){ return cache[i]; } cache[i] = fibo(i-1) + fibo(i-2); return cache[i]; }초기 cache 상태는 다음과 같다.fibo(4)는 fibo(3) + fibo(2) 연산이 이루어진다.fibo(3)에서는 fibo(2) + fibo(1) 연산이 이루어진다.fibo(2)에서는 fibo(1..