Jinlib

세그먼트 트리 또는 인덱스 트리1. 정의위와같이 각 노드에는 구간에 대한 정보가 저장이 되어있는 트리를 의미한다.일반적으로 구간의 합 또는 곱, 구간의 최대값 또는 최솟값을 의미합니다. 예)배열의 데이터 수 : 8개배열의 데이터 A[8] = {1,2,3,4,5,6,7,8}목적 : 구간에 대한 합 세그먼트 이론시 높이 3인 트리가 만들어지며 오른쪽 위에 숫자만큼 각 구간에 대한 정보를 담고 있다. 위와 같이 각 노드는 자식에 대한 합을 포함 하고 있다. 배열은 0부터 인덱스가 시작하므로,A[3] ~ A[6]까지의 합을 구한다고 가정할때, 아래와 같이 주황색 부분의 합만 구하면 된다. 즉, 4+11+7 = 22로 부분에 대한 합을 쉽게 구할 수 있습니다. 위와같이 수행하면 부분의 합에 대한 부분을높이가 O(..

이번 글에서는 알고리즘의 계산복잡도 함수가 재귀식(Recurrence relation) 내지 점화식 형태로 표현되는 경우를 살펴보도록 하겠습니다. 재귀식 또는 점화식이란 피보나치 수열(다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열)처럼 수열의 항 사이에서 성립하는 관계식을 말합니다. 이로부터 데이터 수 nn에 대해 닫힌 형태(closed-form expression)의 정확한 계산복잡도 함수를 찾는 것이 이 글의 목표입니다. (복잡도의 기준은 알고리즘이 필요로 하는 시간과 메모리 등 자원인데 전자를 ‘시간복잡도’, 후자를 ‘공간복잡도’라 합니다) 이번 글 역시 고려대 김선욱 교수님 강의를 정리하였음을 먼저 밝힙니다. 그럼 시작하겠습니다.재귀식 형태로 표현된 시간복잡성알고리즘의 계산복잡도..

알고리즘의 가장 중요한 기본 성질은 "어떤 주어진 문제의 해결 능력"이다. 알고리즘의 성능을 분석하기 위한 기준으로 다음과 같은 요소들을 참고할 수 있다. 1. 정확성(correctness)2. 수행량(amount of work done) = 시간 복잡도(time complexity)3. 사용공간(amount of space used) = 공간 복잡도(space complexity)4. 단순성(simplicity)5. 최적성(optimality) 1. 정확성정확성이란 "알고리즘이 타당한 입력이 주어졌을 때 유한 시간 내에 계산이 수행되어 올바른 결과를 출력하는 것"이라고 정의할 수 있다.정확성을 증명하는 방법으로는 수학적 귀납법이다. 특히 수학적 귀납법은 알고리즘 내의 루프가 의도한대로 수행 되는지를 증..

안녕하세요정렬 알고리즘1 글을 써놓고 2는 바빠서 못썼네요ㅎㅎ..오늘은 퀵정렬만 정리해보려고 합니다. 퀵정렬은 개념을 아예 모르시는 분들이 보면 이해하기가 처음엔 힘들어요.그래서 그런분들을 위해 퀵정렬만!! 정리해보려고해요.하하 정렬 알고리즘 - Quick Sort 퀵정렬!!자, 이름부터 퀵(Quick)이네요.퀵은 다들 아시는 것처럼뜻은 ① (동작·활동 등이) (재)빠른 ②(속도상으로·걸리는 시간이 짧아서) (재)빠른 ③(재)빨리, 신속히 입니다. 이름부터 뭔가 빠른 정렬 알고리즘 같죠? 실제로다른 정렬 방법에 비해 일반적으로 가장 빠른 알고리즘으로 알려져 있습니다. 하지만!!대상 데이터의 특징이나 데이터 크기에 따라 반드시 위 말이 맞는 것은 아닙니다. 실제로 최악의 경우에 시간복잡도가 n^2기도 하구..

Quick Sort 분할할 축값을 정하는 방법의 개선Random vs Median-of-Three 삽입정렬을 소구간에 적용하는 방법 Partition을 사용해서 selection 문제를 해결할 수 있음 1. Divide and conquer (partition) algorithmpivot왼쪽: pivot(축) value 보다 작은 값오른쪽: 큰 값partitiontemplate int partition(TYPE a[], int n){TYPE v, t;int i, j; v = a[n - 1];i = -1;j = n - 1; while (true) {while (a[++i] v); // 우측부터 v 보다 작은 값..

문제 URL https://www.acmicpc.net/problem/2455 1. 문제의 접근을 하기전에 알아야 할 정보 3가지1) 문자열을 분리하는 방법자세히 모른다면 참조2) String형을 int형으로 형변환 2. 풀이이번엔 split 메서드 말고 stringTokenizer 클래스를 사용했다.1234567891011121314151617181920import java.util.*;import java.io.*; public class Main { public static void main(String[] args) throws Exception{ int max=0,temp=0; BufferedReader br = new BufferedReader(new InputStreamReader(Syste..

문제 URL https://www.acmicpc.net/problem/2775 1. 문제의 접근을 하기전에 알아야 할 정보 3가지 2. 풀이처음에 문제가 이해가 안가서 좀 보았는데, 내가 이해한 방식을 아래와 같이 설명하고자 한다.첫째줄에 Test case의 수를 받는데 만약 2라면 4개의 추가적인 입력을 받고 3이라면 6이라는 추가적인 입력을 받는다.위 예제에선 2이므로 4가지 입력을 받았다.다음 입력엔 첫번째 케이스의 층수, 그다음 입력엔 첫번째 케이스의 호수가 입력을 해야한다.다음 입력엔 두번째 케이스의 층수, 그다음 입력엔 두번째 케이스의 호수가 입력을 해야한다.출력은 각 케이스에 해당하는 거주자들의 수를 입력. 0층에는 1호부터 i호 까지 있는데 각 호엔 i명의 사람이 거주하고1층 1호에 살려면..

문제 URL 1. 문제의 접근을 하기전에 알아야 할 정보 3가지1) 문자열을 분리하는 방법자세히 모른다면 참조2) String형을 int형으로 형변환 2. 풀이이번엔 split 메서드 말고 stringTokenizer 클래스를 사용했다. 1) 내코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849package sanggun_chess;import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[]..

문제 URL https://www.acmicpc.net/problem/9517 1.문제의 접근을 하기전에 알아야 할 정보가 3가지. 1) 입력을 받을때 next메서드과 nextInt메서드의 차이.자세히 모른다면 참조 2) 문자열을 분리하는법.자세히 모른다면 참조 3) String형을 int형으로 형변환 자세히 모른다면 참조 2. 내 코드1234567891011121314151617181920212223242526package i_love_croatia;import java.util.Scanner;public class main { public static void main(String[] args){ int time_limit = 210; Scanner scan = new Scanner(System.in..