Kwin's Development Diary.

문제 인하 은행에는 ATM이 1대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는 데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분 만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게..

TreeSet : Set자료형의 특징으로 중복을 허용하지 않으며, 정렬을 지원하는 클래스이다. : *레드-블랙 트리(Red-Black Tree)로 구현되어 있다. * 레드-블랙 트리(Red-Black Tree) : 편향 이진트리의 단점을 보완하기 위한 트리로, 데이터의 삽입/삭제 시 좌우 균형을 맞춰주는 트리 선언 import java.util.TreeSet; import java.util.Collections; // TreeSet 변수명 = new TreeSet (); 정렬 1. 오름차순 TreeSet 변수명 = new TreeSet(); 2. 내림차순 TreeSet 변수명 = new TreeSet(Collections.reverseOrder()); 3. 사용자 정의 TreeSet 변수명 = new T..

문제 수직선 위에 N개의 좌표 X1, X2,..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2,..., XN에 좌표 압축을 적용한 결과 X'1, X'2,..., X'N를 출력해보자. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2,..., XN이 주어진다. 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 109 출력 첫째 줄에 X'1, X'2,..., X'N을 공백 한 칸으로 구분해서 출력한다. 문제 접근 방법 이번 문제는 입력된 수의 크기 순위를 0부터 매겨 수를 압축하여 출력하는 문제이다. 따라서, 숫자를 정렬하여 해당 숫자가 입력된 수..

문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+둘째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전 순으로 출력한다. 문제 접근 방법 이번 문제는 들도 못한 사람의 명단과 보도 못한 사람의 명단에 둘 다 포함되어 있는..

병합 정렬(Merge Sort) - 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방법 - 부분 집합으로 분할(divide)하고, 각 부분 집합에 대해 정렬 작업을 완성(conquer)한 수에 정렬된 부분 집합들을 다시 결합(combine)하는 분할 정복(Divide And Conquer)기법 사용 - 종류 ㄴ 2-way 병합: 2개의 정렬된 자료의 집합을 결합하여 하나의 집합으로 만드는 병합 방법 ⑴ 분할(divide) : 입력 자료를 같은 크기의 부분집합 2개로 분할 ⑵ 정복(conquer) : 부분집합의 원소들을 정렬 : 부분집합의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법 적용 ⑶ 결합(combine) : 정렬된 부분집합들을 하나의 집합으로 통..

삽입 정렬(Insert Sort) - 정렬되어있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법 - 정렬할 자료를 두 개의 부분집합 S와 U로 가정 ㄴ 부분집합 S : 정렬된 앞부분의 원소들 ㄴ 부분집합 U : 아직 정렬되지 않은 나머지 원소들 ㄴ 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입 ㄴ 삽입 정렬을 반복하면서 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 감소하게 한다. ㄴ 부분집합 U가 공집합이 되면 삽입 정렬이 완성 - 수행 과정 정렬되지 않은 배열 L = {69, 10, 30, 2, 16, 8, 61, 22} 초기 상태 : 첫 번째 원소는 정렬되어있는 부분 집합 S로 생각하고 나..

퀵 정렬(Quick Sort) - 정렬할 전체 원소에 대해 정렬을 수행하지 않고, 기준 값을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬 ㄴ 왼쪽 부분 집합에는 기준 값보다 작은 원소들 / 오른쪽 부분 집합에는 기준 값보다 큰 원소들 ㄴ 기준 값 : 피봇(pivot) : 일반적으로 전체 원소 중 가운데 위치한 원소 선택 - 퀵 정렬은 다음의 두 가지 기본 작업을 반복 수행하여 완성 ㄴ 분할(divide) : 정렬할 자료들을 기준값을 중심으로 2개의 부분 집합으로 분할 ㄴ 정복(conquer) : 부분 집합의 원소들 중 기준값보다 작은 원소들은 왼쪽 부분 집합으로, 기준값보다 큰 원소들은 오른쪽 부분 집합으로 정렬, 부분 집합의 크기가 1 이하로 충분치 않으면 순환 호출을 이용하여 재분할..

버블 정렬(Bubble Sort) - 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식 ㄴ 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬 ㄴ 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물속에서 물 위로 올라오는 물방울 모양과 같다고 하여 버블(Bubble) 정렬이라고 함. - 수행 과정 정렬되지 않은 배열 L = {69, 30, 16, 22} 69 30 16 22 ① 69 30 16 22 ② 30 16 22 69 30 69 16 22 16 30 22 69 30 16 69 22 16 22 30 69 30 16 22 69 ③ 16 22 30 69 ④ 버블 정렬 완성 16 22 30 69 16 22 30 69..

선택 정렬(Selection Sort) - 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬 - 수행 방법 1. 전체 원소 중 가장 작은 원소를 찾아 선택하여 첫 번째 원소와 자리 교환 .... 2. n 번째로 작은 원소를 찾아 선택하여 n 번째 원소와 자리 교환 3. 위 과정 반복하며 정렬 완성 - 수행 과정 정렬되지 않은 배열 L = {69, 10, 30, 2, 8, 22} 69 10 30 2 8 22 ① 기준 : 첫 번째 자리 2 10 30 69 8 22 정렬된 원소 정렬되지 않은 원소 ② 기준 : 두 번째 자리 2 8 30 69 10 22 정렬된 원소 정렬되지 않은 원소 ③ 기준 : 세 번째 자리 2 8 10 69 30 22 정렬된 원소 정렬되지 않은 원소 ④ 기..

정렬(Sort) - 2개 이상의 자료를 작은 것부터 큰 순서(오름차순, Ascending)로 정렬 또는 큰 것부터 작은 것 순서(내림차순, Descending)로 재배열하는 것. - 키(key) : 자료를 정렬하는 데 사용하는 기준 값 정렬 방법의 분류 - 실행 방법에 따른 분류 ㄴ 비교식 정렬(Comparative Sort) : 비교하고자 하는 각 키 값들을 한 번에 두 개씩 비교하여 교환하여 정렬하는 방식 ㄴ 분산식 정렬(Distribute Sort) : 키 값을 기준으로 자료를 여러 개의 부분 집합으로 분해, 각 부분 집합을 정렬함으로써 전체를 정렬하는 방식 - 정렬 장소에 따른 분류 ㄴ 내부 정렬(Internal Sort) : 정렬할 자료를 메인 메모리에 올려 정렬 - 장) 정렬 속도 빠름 / 단..