Chapter 06. Sorting and Searching (정렬, 이분검색과 결정알고리즘)

자료구조와 알고리듬 With Java/[인프런] Algorithm

Chapter 06. Sorting and Searching (정렬, 이분검색과 결정알고리즘)

계란💕 2022. 4. 14. 16:07

1. 선택정렬

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i< n; ++i){
    	arr[i] = in.nextInt();
    }
    for(int x : T.solution(n, arr)){
		    System.out.print(x + " ");
    }
  }
  
  public int[] solution(int n, int[] arr){
  
    for(int i = 0; i < n-1; ++i){
    	int idx = i;
      	for(int j = i + 1; j < n; ++j){
        	if(arr[j] < arr[idx])	 idx = j;
         }
       	 	int tmp = arr[i];
     		arr[i] = arr[idx];
      		arr[idx] = tmp;
        }
  		return arr;
  } 
}

Note)

- idx에는 i번째부터 끝까지의 index가 저장된다.

2. Bubble sort (버블 소트)

<hide/>
import java.util.Scanner;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int []arr = new int[n]; 
      
    for(int i = 0; i < n; ++i){    
    	arr[i] = in.nextInt();
    }
    
    for(int x : T.solution(n, arr)){
    	    System.out.print(x + " ");
    }
    return ;
  }
  
  public int [] solution(int n , int[] arr){
 	 int[] answer = new int[n];
    	for(int i = 0; i < n; ++i ){
        	for(int j = i + 1; j < n; ++j){
            	if(arr[i] > arr[j]){
                	int tmp = arr[i];
                  	arr[i] = arr[j];
                  	arr[j] = tmp;
                }
            }
        }
	    answer = arr;
 	 	return answer;
  }
}

3. 삽입정렬

<hide/>

import java.util.Scanner;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n ; ++i){
    	arr[i] = in.nextInt();
    }
    for(int x : T.solution(n, arr)){
		 System.out.print(x + " ");
    }
    return ;
  }
  
  public int[] solution(int n, int[] arr){
  
  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]; 	// j번째 값을 뒤로 민다.
        else break;
        }
    	arr[j + 1] = tmp;	// j가 멈추고 나서 tmp를 넣는다.
 	 }
	return arr;
  } 
}

Note)

- arr[i] 보다 큰 모든 arr[j] 를 오른쪽으로 한 칸씩 이동한다.

- break를 꼭 넣는다.

- (j) for 문이 멈춘 뒤에 arr[j + 1] 에 tmp를 넣는다. ........ ???????

???????????

4. Least Recently Used (LRU) - 카카오 변형

<hide/>
import java.util.Scanner;
  
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    int s = in.nextInt();
    int n = in.nextInt();
    int []arr = new int[n];
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt();
    }
    for(int x : T.solution(s, n, arr)){
    	System.out.print(x + " ");	
    }
        return ;
  }
  
  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;
  }
}

Note)

5. 중복 확인

<hide/>
import java.util.*;
public class Main {
  
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int [] arr = new int[n];
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt();
    }
    System.out.println(T.solution(n, arr));
    return ;
  }
  
  	public char solution(int n, int[] arr){
    	Arrays.sort(arr);
    	for(int i = 0; i < n- 1; ++i){
            	if(arr[i] == arr[i+1] ) return 'D';
        }
    	return 'U';
    }
}

Note)

- 정렬로 하면 시간 복잡도: O(nlogn)

6. 장난 꾸러기

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int [] arr = new int[n];
    for(int i = 0 ; i < n; ++i){
    	arr[i] =  in.nextInt();
    }
    for(int i:  T.solution(n, arr) ){
    	System.out.print( i + " ");
    }
    return ;
  }
  
  public  ArrayList<Integer>  solution(int n, int [] arr){
  	
    ArrayList<Integer> answer = new ArrayList<>();
    int[]tmp = new int[n];
    
    for(int i = 0 ;i < n; ++i){
    	tmp[i] = arr[i];
    }
  	Arrays.sort(tmp);
  
    for(int i = 0; i < n; ++i){
         if(arr[i] != tmp[i])	answer.add(i + 1);
    }
 	return answer;
  }
}

Note)

- ArrayList를 이용한다.

- tmp에 arr을 복사할 때, 깊은 복사를 한다.

- 배열을 복사해서 정렬 시킨 뒤에 값이 다를 때의 index만 answer에 담는다.

7. 좌표 정렬 (compare to)

<hide/>
import java.util.*;
// 좌표 저장하는 클래스 만들기

class Point implements Comparable<Point>{	
// comparable인터페이스를 구현하는 클래스
// Point라는 클래스의 객체를 정렬한다.
  
  public int x, y;
  Point(int x, int y){
  	this.x = x;
  	this.y = y;
  }
  
  @Override
  public int compareTo(Point o){
  	if(this.x == o.x) 	return  this.y - o.y;	// 오름차순
  	else return this.x - o.x;
  }
}

public class Main {
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    ArrayList<Point> arr = new ArrayList<>();
    
    for(int i = 0; i < n; ++i ){
    	int x = in.nextInt();
      	int y = in.nextInt();
      	arr.add(new Point(x, y));	// 객체 생성, 생성자를 호출한다.
    }
    Collections.sort(arr); 
    // 오버라이드한 compareTo를 기준으로 정렬된다.
    for(Point o : arr) System.out.println(o.x + " " + o.y);
    
  }
}

Note)

- if(this.x == o.x) return this.y - o.y; 이면 오름차순 , 반대로 빼면( o.y - this.y ) 내림차순이다. (암기!)

- compareTo()를 오버라이드한다.

8. 이분검색

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in=new Scanner(System.in);
    int n = in.nextInt();
    int m = in.nextInt();
   	int[] arr=  new int[n];
    
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt();
    }
    System.out.println(T.solution(n, m , arr));
    return ;
  }
  
 	public int solution(int n, int m, int[]arr){
    	int answer = 0;
    	Arrays.sort(arr);
    	int lt = 0, rt = n - 1;
      
        while(lt <= rt){	// 등호도 포함
      	int mid = (lt + rt) / 2;
        if (arr[mid] == m){
        	answer = mid + 1;
         	break;
        }
      	else if (arr[mid] > m) rt = mid  - 1;
        else lt = mid + 1;
      }
      return answer;
    }
}

Note)

- 이분검색은 일단 정렬이 되어 있어야한다.

- (index 번호) mid = ( lt + rt ) / 2

- index 에 1을 더해야 몇번째인지 알 수 있다. -> answer = mid + 1

9. 뮤직비디오 (결정 알고리즘 - 이분 검색을 이용한다.)

<hide/>
import java.util.*;
public class Main {
  public static void main(String[] args){
    Main T = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();	// n = 9
    int m = in.nextInt();	// m = 3
   	int [] arr = new int[n];	// 1 2 3 4 5 6 7 8 9 
    
    for(int i = 0; i < n; ++i){
    	arr[i] = in.nextInt();
    }
    System.out.println(T.solution(n, m, arr));
  }
  
  public int count(int[] arr, int capacity){	// capacity: DVD 한 장의 용량
  		
  	int cnt = 1, sum = 0;	// cnt: DVD 장 수
    for(int x : arr){
    	if( sum + x > capacity ){
        	cnt++;		
            // x 전까지 누적했을 때는 capacity보다 작은 걸 만족했기 때문에 플러스한다.
          	// cnt를 1부터 시작하기 때문에 나중에 플러스
            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();	
    // 노래 곡 중의 최대값
    // 배열의 stream을 얻는다.
  	// iterator와 같다.
    
    int rt  = Arrays.stream(arr).sum();	// 배열의 모든 값을 더한다.
    
    while(lt <= rt){
    	int mid = (lt + rt) / 2;	// mid = DVD 한 장의 용량
    	if(count(arr, mid) <= m){  	// 문제의 3보다 작거나 같아야 한다. (두 장이면 세장으로는 당연히 가능)
        	answer = mid;	// 일단은 저장해두고 좁혀나간다.
          	rt = mid - 1;	
        }else lt = mid + 1;	// 더 큰쪽에서 찾는다.
    }
    return answer;
  }
}

Note)

- 좁혀 나가서 마지막에 남은 값이 답이 된다.

- stream은 의미 있는 값을 찾는데 필요한 메서드를 제공한다.

- stream이라는 반복자를 이용한다.

- max()는 stream의 메서드, 반환형이 int가 아닌 optional int로 반환된다.

-> 따라서 getAsint() 를 통해 int형으로 바꿀 수 있다.

-> 가장 큰 9를 한 장에 담는 경우, 즉 9를 lt로 잡는다.

- sum()은 기본형 int로 반환되므로 max()처럼 int로 바꿀 필요없다.

-> 한 장에 1 ~ 9까지 다 담는 경우, 즉 45를 rt로 잡는다.

- (9 + 45) / 2 = 27일 때, CD 두 장만으로도 충분한다. (m = 3과 다름)

-> answer 에 27을 저장해두고 더 좋은 답이 있는지 확인한다.

-> 따라서, mid는 27보다 작은 값으로 적용한다. => mid = 27 - 1 = 26이 된다.

-> rt = 27 - 1

- (9 + 26) / 2 = 17일 때, CD 세 장이 필요하다.

-> answer = 17이 새로 저장된다.

-> rt = 17 - 1 = 16

- (9 + 16) / 2 = 12 일 때, DVD 5장 이상 필요하다.

-> lt = 12 - 1 = 11

- (11 + 16) / 2 = 13 일 때 5장은 필요하다.

-> lt = 13 - 1 - 12

... 반복한다.

?????????

10. 마구간 정하기 (결정 알고리즘)

<hide/>
import java.util.*; 
public class Main {
 	
  public int count(int [] arr, int dist){	// 유효함수 (mid로 정해도 되겠는지)
 	int cnt = 1;	// 배치한 말의 마리 수
  	int ep = arr[0];	// end position
    for(int i = 1; i < arr.length; ++i){	
        // 첫번째는 배치 했으므로 1부터
      	if(arr[i] - ep >= dist){	// 그래야 다음 말을 넣을 수 있다.
        	cnt++;	// 말 한 마리 늘린다.
          	ep = arr[i];
        }
     }
 	return cnt;
 	}
  
  public static void main(String[] args){
   	Main T = new Main();
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();	// 마구간 개수
    int c = in.nextInt();	// 말 마리 수
    int [] arr = new int[n];// 마구간 좌표
   	for(int i = 0; i < n ; ++i){
    	arr[i] = in.nextInt();
    }
    System.out.println(T.solution(n, c, arr));
  }
  
  public int solution(int n, int c,  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) >= c){	// 유효한지 판단
        	answer = mid;	// 유효하므로 answer에 저장한다.
          	lt = mid + 1;	// 큰 쪽으로 가야한다.
        }else rt = mid - 1;		// 작은 쪽으로 가야한다.
    }
 	return answer;
  }
}

Note)

- 가장 가까운 두 말의 최대 거리

- n: 마구간 좌표, c: 말 수

- lt, rt를 정해서

- 유효 함수 count()

- ep(end position): 바로 전에 말을 배치한 마구간

- arr[i] - ep >= mid

-> mid보다 크거나 같아야 다음 말을 배치할 수 있다.

-> mid보다 크거나 같은 마구간에 다음 말을 배치

- 유효함수 만드는 요령리 가장 중요하다.

저작자표시

'자료구조와 알고리듬 With Java > [인프런] Algorithm' 카테고리의 다른 글

Chapter 08. DFS, BFS 활용 (0)	2022.04.18
Chapter 07. Recursive, Tree, Graph (DFS, BFS 기초) (0)	2022.04.15
Chapter 05. Stack, Queue (자료구조) (0)	2022.04.13
Chapter 04. HashMap, TreeSet (해쉬, 정렬지원 Set) (0)	2022.04.12
Chapter 03. Two pointers, Sliding window (0)	2022.04.12

현재글Chapter 06. Sorting and Searching (정렬, 이분검색과 결정알고리즘)

Backend Developer lan4250@naver.com https://github.com/goraneee

제로베이스 백엔드, BFS, Java, 코드업, 데이터베이스, dp, JPA, 프로그래머스, GIT, 스프링, SQL, 백준, mysql, 자바, DB, Stack, dfs, 제로베이스 스쿨, Queue, 알고리즘,

Today :
Yesterday :

계란 블로그