Yong's Tech Story

문제 풀이 (JAVA)

import java.util.*;
public class part6_8 {

	public static void main(String[] args) {
		// 이분검색
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		int M = input.nextInt();
		int [] arr = new int[N];
		for(int i=0; i<N; i++) {
			arr[i]=input.nextInt();
		}
		int answer = solution(arr,N,M);
		
		System.out.print(answer);
	}
	private static int solution(int [] a, int N, int K) {
		Arrays.sort(a); // 숫자 오름차순 정렬
		int result=0;
		int idx=0; // 탐색할 인덱스 변수 선언
		int lt = 0, rt=N-1; // 배열 투포인터 선언
		while(a[idx] != K) { // K일때까지 이분검색 
			idx=(lt+rt)/2; // 이분검색을 통한 배열의 중앙값 인덱스
			if(a[idx]==K) { // K일시 종료
				result=idx+1; 
				break;
			}
			if(a[idx] < K) { // 중앙값이 K보다 작다면
				lt = idx+1; // 오른쪽을 탐색해야 하므로 lt 포인터 재선언
			}else if(a[idx] > K) { // 중앙값이 K보다 크다면
				rt = idx-1;  // 왼쪽을 탐색해야 하므로 rt 포인터 재선언
			}
		}		
		return result;
	}
}

주요 핵심 포인트

1.  이분검색은 검색의 효율성을 높이기 위한 것으로 숫자가 오름차순으로 정렬되어 있을 때 중앙값을 반복 탐색하여 값을 찾는 알고리즘이다.

2. 중앙값< 찾을값 이라면 중앙값을 기준으로 오른쪽에 있으므로 왼쪽 포인터 증가,

    중앙값> 찾을값 이라면 중앙값을 기준으로 왼쪽에 있으므로 오른쪽 포인터 감소

개선해야할 사항

1.  이분탐색시 lt와 rt의 인덱스 설정하는 부분을 헷갈리지 말자. lt는 idx+1, rt는 idx-1 이다.

문제 풀이 (JAVA)

import java.util.*;
public class part6_3 {

	public static void main(String[] args) {
		// 삽입 정렬
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		
		int [] a = new int[N];
		for(int i=0; i<N; i++) {
			a[i]=input.nextInt();
		}
		int [] answer=solution(a,N);
		for(int i=0; i<N; i++) {
			System.out.print(answer[i]+" ");
		}
	}
	private static int [] solution(int [] a, int n) {
		int tmp=0;
		for(int i=1; i<n; i++) { // 1~N까지 반복
			for(int j=i; j>0; j--) { // i번째부터 1번째까지 반복
				if(a[j-1] > a[j]) { // 앞의 숫자가 크다면 스왑
					tmp = a[j-1];
					a[j-1] = a[j];
					a[j] = tmp;
				}
			}
		}
		return a;
	}
}

주요 핵심 포인트

1.  삽입정렬은 인덱스 1번째부터 0번과 비교한후 교환, 2번째부터 1번, 0번과 순차적 비교하여 값 교환 등 순차적으로 끝자리부터 앞쪽으로 밀고나가는 형식이다.

2. 따라서 1번째부터 반복하여 j를 i번째로 두어 반복 횟수를 감소시켰다.

개선해야할 사항

1.  삽입정렬은 1번째 인덱스부터 앞쪽으로 비교하여 밀고나가는 형식이다. 버블정렬과 혼돈되지 않도록 주의하자.

문제 풀이 (JAVA)

import java.util.*;
public class part6_2 {

	public static void main(String[] args) {
		// 버블 정렬
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		
		int [] a = new int[N];
		
		for(int i=0; i<N; i++) {
			a[i] = input.nextInt();
		}
		int [] answer = solution(a,N);
		for(int i=0; i<answer.length; i++) {
			System.out.print(answer[i]+" ");
		}
	}
	private static int [] solution(int [] a, int n) {
		int tmp=0;
		for(int i=n-1; i>0; i--) { // 반복횟수를 -1씩 줄인다.
			for(int j=0, k=1; j<i; j++, k++) { // i번 앞뒤를 비교한다.
				if(a[j] > a[k]) { // 앞의 값이 크다면 스왑
					tmp = a[j];
					a[j] = a[k];
					a[k] = tmp;
				}
			}
		}
		return a;
	}
}

주요 핵심 포인트

1. 버블정렬은 i번째와 j번째를 비교하는데 j=i+1번째로 인덱스 0 ,1 부터 비교하여 1,2 ... i+1, j+1 씩 증가하여 n까지 반복한다.

2. n번째 도달했을때 마지막 값은 정렬된 값으로 그 다음 값 n-1번째를 구하기 위하여 i는 -1 감소 시킨다.

3. 1~2를 반복하여 끝자리부터 구하는 것이 버블 정렬이다.

개선해야할 사항

1. 선택정렬은 0~N, 1~N , i+1~N 씩 반복하나 버블 정렬은 N~0, N-1~0 , 씩 반복하여 끝자리부터 구한다.

또한 두 개의 배열을 하나씩 비교하여 동시에 증가하여 다음 배열을 비교한다.

다른 정렬과의 차이에 헷갈리지 말자. 

문제 풀이 (JAVA)

import java.util.*;
public class part6_1 {

	public static void main(String[] args) {
		// 선택 정렬
		Scanner input = new Scanner(System.in);
		
		int N = input.nextInt();
		
		int [] intarr = new int[N];
		
		for(int i=0; i<N; i++) {
			intarr[i] = input.nextInt();
		}
		int [] arr = solution(intarr,N);
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
	private static int [] solution(int [] a, int n) {
		int min=0;
		int tmp=0;
		// 선택정렬은 앞부터 하나씩 비교하여 서로간의 위치를 바꾼다.(모든 경우 탐색)
		for(int i=0; i<n; i++){
			min=a[i]; // 최솟값 초기화
			for(int j=i+1; j<n; j++) {
				if(min > a[j]) {
					tmp = a[i]; // 앞의 값 임시 저장
					min = a[j]; // 최소는 비교하는 뒤의 값
					a[i] = a[j]; // 뒤의 값 을 앞에 값에 덮어쓰기
					a[j] = tmp; // 뒤의 값을 임시저장한 앞의값 추가
				}
			}
		}
		return a;
	}
}

주요 핵심 포인트

1. 선택 정렬은 i번째 인덱스부터 시작하여  i+1번째 다음 숫자부터 하나씩 비교하여 값이 더 작거나 크다면 값을 교체한다.

2. i번째 인덱스에서 모든 j번째 인덱스를 탐색하여 값을 구했을시 확정된 값은 비교하지 않고 다음 i+1번째부터 1을 반복한다.

개선해야할 사항

1. 확정된 숫자는 더이상 비교하지 않고 다음 배열을 반복해서 비교한다는 사실을 기억하자. 정렬은 종류가 여러가지라 헷갈릴수 있다.