1. 선택 정렬
2. 버블 정렬
3. 삽입 정렬
4. 삽입 정렬 예제
5. 이분 검색, 결정 알고리즘
6. 이분 검색, 결정 알고리즘 예제
- 선택 정렬
1. 선택 정렬은 정렬 알고리즘 중 하나이다.
2. n(n-1)/2번, 즉 O(n^2)의 시간 복잡도를 가지므로 대규모 데이터에 대해 효율적이지 않다.
- 버블 정렬
1. 버블 정렬은 정렬 알고리즘 중 하나이다.
2. 시간 복잡도가 O(n^2)의 시간 복잡도를 가지므로 선택 정렬과 마찬가지로 대규모 데이터에 대해 효율적이지 않다.
for(int i=0; i<n-1; i++){
for(int j=0; j<n-i-1; j++){
if(arr[j]>arr[j+1]){
int tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
}
}
}
return arr;
}
1. 배열이 주어지면 맨앞에서부터 바로 뒤의 값과 비교하여 제일 큰 값을 제일 뒤로 보내는 방식이다.
2. 전체적으로 한 번 돌고 나면 가장 뒤에 가장 큰 수가 위치하게 된다.
3. 반복문을 통해 제일 큰 수를 차례대로 가장 뒤에 배치시키는 방법이다.
- 삽입 정렬
1. 선택 정렬은 효율적인 정렬 알고리즘 중 하나이다.
2. 삽입 정렬은 주로 작은 데이터 세트나 정렬된 부분이 이미 존재하는 상황에서 사용할 때 효과적이다.
3. 시간 복잡도는 평균적으로 O(n^2)이지만, 데이터가 이미 정렬되어 있는 경우에는 O(n)의 성능을 보인다.
for(int i=1; i<n; i++){
int tmp=arr[i], j;
for(j=i-1; j>=0; j--){
if(arr[j]>tmp) arr[j+1]=arr[j];
else break;
}
arr[j+1]=tmp;
}
return arr;1. 배열의 두번째 인덱스를 기준으로 잡는다.
2. 기준 인덱스보다 작은 인덱스 중 기준 인덱스보다 작은 값을 발견하게 되면 값을 변경한다.
3. 기준 인덱스의 앞쪽 인덱스들은 계속해서 정렬된 상태이며 기준 인덱스가 바뀔 때 마다 기준 인덱스 앞쪽의 인덱스에서 해당 인덱스보다 큰 수만 찾게 되면 바로 정렬이 완료된다.
- 삽입 정렬 문제 : Least Recently Used
설명
캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가
필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다.
철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따른다.
LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다.
캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다.
Image1.jpg
캐시의 크기가 주어지고, 캐시가 비어있는 상태에서 N개의 작업을 CPU가 차례로 처리한다면 N개의 작업을 처리한 후
캐시메모리의 상태를 가장 최근 사용된 작업부터 차례대로 출력하는 프로그램을 작성하세요.
입력
첫 번째 줄에 캐시의 크기인 S(3<=S<=10)와 작업의 개수 N(5<=N<=1,000)이 입력된다.
두 번째 줄에 N개의 작업번호가 처리순으로 주어진다. 작업번호는 1 ~100 이다.
출력
마지막 작업 후 캐시메모리의 상태를 가장 최근 사용된 작업부터 차례로 출력합니다.- 풀이 코드
import java.util.*;
class Main {
public int[] solution(int size, int n, int[] arr){
int[] cache=new int[size];
for(int x : arr){
int pos=-1;
for(int i=0; i<size; i++) if(x==cache[i]) pos=i;
if(pos==-1){
for(int i=size-1; i>=1; i--){
cache[i]=cache[i-1];
}
}
else{
for(int i=pos; i>=1; i--){
cache[i]=cache[i-1];
}
}
cache[0]=x;
}
return cache;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int s=kb.nextInt();
int n=kb.nextInt();
int[] arr=new int[n];
for(int i=0; i<n; i++) arr[i]=kb.nextInt();
for(int x : T.solution(s, n, arr)) System.out.print(x+" ");
}
}1. 주어진 배열 값에서 값을 하나씩 꺼내서 새롭게 생성한 배열에 값을 하나씩 넣는다.
2. 값을 넣을 때 배열에 존재하는 값인지 비교하여 2가지 경우를 구분한다.
2.1. 같은 값이 존재하지 않을 경우
2.1.1. 같은 값이 존재하지 않을 경우 배열을 그대로 하나씩 위치를 뒤로 밀고 제일 앞에 주어진 값을 저장한다.
2.2. 같은 값이 존재할 경우
2.2.1. 같은 값이 존재하게 되면, 해당 번호가 가장 앞으로 나오고 나머지는 순서를 유지하며 뒤로 밀려난다.
2.2.2. 값이 존재하게 되면 기존의 배열에서 위치가 변경되는 경우와 동일하기 때문에 배열 전체를 이동 시킬 필요없이, 해당 값이 존재하는 위치를 기준으로 앞부분을 뒤로 한칸씩 밀면 된다.
2.2.3. 마지막으로 주어진 숫자를 배열 가장 앞에 위치 시킨다.
- 이분 검색 및 결정 알고리즘
- 이분 검색
1. 이분 검색은 정렬된 배열 또는 리스트에서 특정 원소를 효율적으로 찾는 알고리즘이다.
2. 주어진 데이터의 중간 원소를 기준으로 검색 대상을 반으로 나누고, 찾고자 하는 원소와 중간 원소를 비교하여 검색 범위를 반으로 줄여가는 방식이다.
3. 시간 복잡도는 O(log n)으로 매우 효율적이지만 데이터가 정렬되어 있을때만 사용할 수 있다.
- 결정 알고리즘
1. 이분 검색 알고리즘을 사용할 때, 특정 원소를 찾을 때 조건을 판단하기 위해 함수를 정의하는 것을 뜻한다.
2. 결정 알고리즘을 통해 이분 검색 알고리즘의 조건을 풀어나갈 수 있다.
- 이분 검색, 결정 알고리즘 예제
9. 뮤직비디오(결정알고리즘)
설명
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.
순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는
1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.
고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.
입력
첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다.
다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다.
부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.
출력
첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.
예시 입력 1
9 3
1 2 3 4 5 6 7 8 9
예시 출력 1
17
힌트
설명 : 3개의 DVD용량이 17분짜리이면 (1, 2, 3, 4, 5) (6, 7), (8, 9) 이렇게 3개의 DVD로 녹음을 할 수 있다.
17분 용량보다 작은 용량으로는 3개의 DVD에 모든 영상을 녹화할 수 없다.
- 풀이 코드
import java.util.*;
class Main {
public int count(int[] arr, int capacity){
int cnt=1, sum=0;
for(int x : arr){
if(sum+x>capacity){
cnt++;
sum=x;
}
else sum+=x;
}
return cnt;
}
public int solution(int n, int m, int[] arr){
int answer=0;
int lt=Arrays.stream(arr).max().getAsInt();
int rt=Arrays.stream(arr).sum();
while(lt<=rt){
int mid=(lt+rt)/2;
if(count(arr, mid)<=m){
answer=mid;
rt=mid-1;
}
else lt=mid+1;
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
int m=kb.nextInt();
int[] arr=new int[n];
for(int i=0; i<n; i++) arr[i]=kb.nextInt();
System.out.println(T.solution(n, m, arr));
}
}
1. 이분 검색을 위한 범위를 지정한다.
2. 주어진 배열에서 재생 시간이 (1). 가장 최소일 때는 정렬된 배열에서 가장 큰 값이고, 재생 시간이 (2). 최대일 때는 모든 재생 목록의 시간을 더했을 때가 가장 큰 재생 시간이 된다.
3. 즉, 배열에서 가장 큰 값과 배열 전체를 더한 값을 범위로 이분 검색을 실시한다.
public int solution(int n, int m, int[] arr){
int answer=0;
int lt=Arrays.stream(arr).max().getAsInt();
int rt=Arrays.stream(arr).sum();
while(lt<=rt){
int mid=(lt+rt)/2;
if(count(arr, mid)<=m){
answer=mid;
rt=mid-1;
}
else lt=mid+1;
}
return answer;
}1. lt와 rt를 통해 좌우 기준을 정하고, 좌측 기준이 우측보다 커지지 않는동안 반복을 실시한다.
2. 주어진 범위를 반으로 나눈 다음, count(결정 알고리즘) 함수의 값의 범위에 어디에 위치하는에 따라 범위를 변경해 나간다.
3. count 함수는 결정 알고리즘으로 주어진 조건의 값을 찾아내기 위한 함수에 해당한다.
4. 결정 알고리즘의 결과에 따라, 이분 검색을 하기 위한 범위의 기준 값을 변경해 나간다.
5. 위 문제의 경우 주어진 count의 결과 값이 주어진 갯수보다 작을 경우 원하는 결과값이 둘로 나눈 범위 중 좌측에 존재하는기 때문에 범위를 좌측으로 새롭게 지정하고, count의 결과 값이 주어진 갯수보다 큰 경우 원하는 결과값이 둘로 나눈 범위 중 우측에 존재하기 때문에 새로운 범위를 우측으로 새롭게 지정한다. (이 기준은 문제에 따라 달라 질 수 있으므로 이 알고리즘을 짜는 것이 결정 알고리즘에서 가장 중요하고 어려운 일이다.)
public int count(int[] arr, int capacity){
int cnt=1, sum=0;
for(int x : arr){
if(sum+x>capacity){
cnt++;
sum=x;
}
else sum+=x;
}
return cnt;
}1. count 함수는 capacity 범위값을 지정 받고, 해당 DVD의 재생 시간을 계속 더해 나가면서 주어진 범위를 넘어나게 되면 DVD 한개를 늘려야하는 상황의 코드를 짠 것이다.
2. 주어진 배열의 갯수만큼 돌면서 주어진 용량보다 클 경우 새로운 DVD를 하나씩 생성해 나가면서 최종적으로 생성된 DVD 갯수를 반환한다.
3. lt(좌측) 기준이 rt(우측) 기준보다 작거나 같을 때 까지만 해당 알고리즘을 반복이 끝나는 시점의 값이 주어진 조건에서 제일 만족하는 결과값을 도출 할 수 있다.
10. 마구간 정하기(결정알고리즘)
설명
N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.
현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,
가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.
C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.
입력
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.
출력
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.
예시 입력 1
5 3
1 2 8 4 9
예시 출력 1
3- 풀이 코드
import java.util.Arrays;
import java.util.Scanner;
class Main {
public int count(int[] arr, int capacity) {
int cnt = 1;
int point = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] - point >= capacity) {
cnt++;
point = arr[i];
}
}
return cnt;
}
public int solution(int n, int m, int[] arr) {
int answer = 0;
Arrays.sort(arr);
int lt = 1;
int rt = arr[n - 1];
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (count(arr, mid) >= m) {
answer = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
return answer;
}
public static void main(String[] args) {
Main main = new Main();
Scanner kb = new Scanner(System.in);
int a = kb.nextInt();
int b = kb.nextInt();
int[] arr = new int[a];
for (int i = 0; i < a; i++) {
arr[i] = kb.nextInt();
}
System.out.println(main.solution(a, b, arr));
}
}1. 위 문제도 이전 문제와 마찬가지로 결정 알고리즘 함수를 잘 작성하는 것이 중요하다.
public int solution(int n, int m, int[] arr) {
int answer = 0;
Arrays.sort(arr);
int lt = 1;
int rt = arr[n - 1];
while (lt <= rt) {
int mid = (lt + rt) / 2;
if (count(arr, mid) >= m) {
answer = mid;
lt = mid + 1;
} else {
rt = mid - 1;
}
}
return answer;
}1. 마굿간의 거리가 최대가 되어야 하고, 주어진 마리수만큼 마굿간에 배치 되어야 한다.
2. 배치된 말 사이의 거리를 최대로 주어줘야 하기 때문에
if (count(arr, mid) >= m)주어진 말 마리수보다 크면 최대 거리가 짧아지기 주어진 값보다 큰 값이존재할 경우를 찾기 위해 이분으로 나눈 기준에서 우측 범위에서 값을 도출해낸다.
3. 만약 말의 수가 주어진 마리수보다 적으면 말 간의 거리가 너무 멀다는 뜻이기 때문에 이분 검색에 의해 나누어진 범위에서 좌측 부분을 탐색하게 된다.
else {
rt = mid - 1;
}
public int count(int[] arr, int capacity) {
int cnt = 1;
int point = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] - point >= capacity) {
cnt++;
point = arr[i];
}
}
return cnt;
}1. 위의 검색 알고리즘 함수는 말이 가장 좌측에 위치해 있을 때를 기준으로 다음 말이 올 수 있는 위치와의 거리를 비교해서 해당 거리가 넘어온 기준 값보다 크면 다음 말을 배치 할 수 있다.
2. 말을 배치 할 때마다. 말의 수를 한마리씩 늘리고, 거리를 측정할 기준이 되는 말의 위치를 변경한다.
* 이분 검색, 결정 알고리즘은 결국 주어진 문제를 통해 조건 결과를 도출해내는 검색 알고리즘 함수를 작성하는 것이 중요하다.
1. 여기서 중요한 것은 주어진 기준으로 이분 검색에 의해 (1) 최대 거리를 늘려야 하는지, (2) 최대 거리를 줄여야 하는지 잘 생각해서 코드를 작성하는 것이 중요해 보인다.
'Programming > CodingTest' 카테고리의 다른 글
| CodingTest - 정렬 (Comparable, compareTo, Collections.sort) (0) | 2023.12.12 |
|---|---|
| CodingTest - Recursive, Tree, Graph(DFS, BFS 기초) (0) | 2023.11.09 |
| CodingTest - HashMap, TreeSet (해쉬, 정렬지원 Set) (0) | 2023.11.01 |
| CodingTest - Two Pointers, Sliding Window (0) | 2023.10.19 |
| CodingTest - 퀵 정렬 (1) | 2023.10.17 |