BOJ 1920, 10816

2021-01-05

위 문제는 백준 사이트의 알고리즘 1920과 10816 문제에 관한 설명입니다.

1920번 문제

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때,

이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다.

다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다.

다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다.

다음 줄에는 M개의 수들이 주어지는데,

이 수들이 A안에 존재하는지 알아내면 된다.

모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

package 이분탐색;

import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ1920 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		int M = Integer.parseInt(br.readLine());
		Arrays.sort(array);
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			System.out.println(binarySearch(Integer.parseInt(st.nextToken()), array));
		}
	}

	private static int binarySearch(int key, int[] array) {
		int left = 0;
		int right = array.length - 1;
		int mid = 0;

		while (left <= right) {
			mid = (left + right) / 2;
			if (key == array[mid])
				return 1;
			else if (key < array[mid])
				right = mid - 1;
			else
				left = mid + 1;
		}
		return 0;
	}
}

이번 문제는 이분탐색 문제 였습니다.

이분탐색 또는 이진탐색 이란?

정렬되어 있는(이분 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때,

순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라

탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법입니다.

알고리즘은?

오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘
절반씩 줄여가며 찾기 때문에 모든 값을 순회해야 하는 일반적인 Search보다 빠르다.
중앙값을 찾는 값에 비교
- (중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색
- (중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색

이제 간단히 알아봤으니 하나씩 살펴봅니다.

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		int M = Integer.parseInt(br.readLine());
		Arrays.sort(array);
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			System.out.println(binarySearch(Integer.parseInt(st.nextToken()), array));
		}
	}

Main 함수 부분입니다.

N을 입력받고, N개의 정수를 array에 담습니다.

그리고 M을 입력받습니다.

이후 이분탐색을 하기 위해 정렬을 해줍니다.

정렬을 해주는 이유는 이분탐색은 중앙값을 기준으로

찾고자하는 key 값보다 큰지 작은지 판단함으로써 탐색범위를 줄입니다.

그렇기 때문에 입력받은 정수들이 있는 array를 정렬 시키고,

찾고자하는 key값들을 하나씩 이분탐색 메소드에 넣어줍니다.

	private static int binarySearch(int key, int[] array) {
		int left = 0;
		int right = array.length - 1;
		int mid = 0;

		while (left <= right) {
			mid = (left + right) / 2;
			if (key == array[mid])
				return 1;
			else if (key < array[mid])
				right = mid - 1;
			else
				left = mid + 1;
		}
		return 0;
	}

이분탐색 메소드의 부분입니다.

탐색을 하기에 앞서

left에는 탐색을 위해 제일 첫 부분(0)을 넣습니다.

right에는 탐색하고자 하는 배열의 제일 마지막 인덱스를 넣어줬습니다.

이제 while을 통해 반복시킬 것인데 그 조건은 아래와 같습니다.

left(탐색의 시작부분)가 right(탐색의 끝 부분)보다 크다면

탐색 범위가 끝이 났다는 뜻이기 때문에 “작거나 같다”로 설정합니다.

해당 조건에 맞다면 이분탐색을 위해 중앙값 mid를 계산합니다.

만약 찾고자하는 key값이 배열의 mid번째에 있다면

문제에서 원하는 것 처럼 1을 반환합니다.

만약 mid번째에 없다면 탐색을 마저해야하는데,

이때 2가지 케이스로 구분이 됩니다.

			else if (key < array[mid])
				right = mid - 1;
			else
				left = mid + 1;

key값보다 array[mid]가 크다면,

right(탐색의 끝부분)를 mid + 1로 해서 탐색범위를 좁혀줍니다.

key값보다 array[mid]가 작다면,

left(탐색의 시작부분)를 mid + 1로 해서 탐색범위를 좁혀줍니다.

이 과정을 반복했음에도 불구하고 key값을 발견하지 못하고 탐색이 끝난다면

while문 밖으로 나와 0을 반환합니다.

수 찾기

10816번 문제

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다.

상근이는 숫자 카드 N개를 가지고 있다.

정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가

몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.

둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다.

숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다.

넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며,

이 수는 공백으로 구분되어져 있다.

이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서,

각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

package 이분탐색;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ10816 {
	static int[] array;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine().trim());
		array = new int [N]; 
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N; i++) 
			array[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(array);
		
		int M = Integer.parseInt(br.readLine().trim());
		st = new StringTokenizer(br.readLine());
		int key, lower, upper;
		for (int i = 0; i < M; i++) {
			key = Integer.parseInt(st.nextToken());
			upper = upper_bound(key);
			lower = lower_bound(key);
			bw.append((upper - lower) + " ");
		}
		bw.flush();
		bw.close();
		br.close();
	}
	private static int upper_bound(int key) {
		int start = 0;
		int end = array.length-1;
		int mid;
		while(start < end) {
			mid = (start + end)/2;
			if(array[mid] > key)
				end = mid;
			else start = mid + 1;
		}
		if(array[end] == key) end++;
		return end;
	}
	private static int lower_bound(int key) {
		int start = 0;
		int end = array.length-1;
		int mid;
		while(start < end) {
			mid = (start + end)/2;
			if(array[mid] >= key)
				end = mid;
			else start = mid+1;
		}
		return end;
	}
	
}

이번 문제도 이분탐색 문제 였습니다.

이분탐색을 기본적으로 알고 있어야하는 문제였습니다.

왜냐하면 이번 문제를 풀기 위해서 Upper Bound, Lower Bound를 사용했기 때문입니다.

Upper Bound(상계), Lower Bound(하계)

Upper Bound와 Lower Bound는 이진탐색을 활용한 알고리즘입니다.

이진탐색이 데이터내 특정 값을 정확히 찾고, 못 찾았을 때 -1 등을 반환하는 이진탐색과는 달리,

UpperBound와 LowerBound는 이진탐색 알고리즘에서 약간 변형된 것으로

중복된 자료가 있을때 유용하게 탐색할 수 있는 알고리즘으로

Lower bound는 데이터내 특정 K값 보다 같거나 큰값이 처음 나오는 위치를 리턴해주고,

Upper bound 는 K값 보다 처음으로 큰 값이 나오는 위치를 리턴해주는 알고리즘입니다.

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine().trim());
		array = new int [N]; 
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < N; i++) 
			array[i] = Integer.parseInt(st.nextToken());
		
		Arrays.sort(array);
		
		int M = Integer.parseInt(br.readLine().trim());
		st = new StringTokenizer(br.readLine());
		int key, lower, upper;
		for (int i = 0; i < M; i++) {
			key = Integer.parseInt(st.nextToken());
			upper = upper_bound(key);
			lower = lower_bound(key);
			bw.append((upper - lower) + " ");
		}
		bw.flush();
		bw.close();
		br.close();
	}

메인함수에서 각각의 입력값들을 받고,

정렬하고 하는 과정은 이분탐색의 형태와 동일했습니다.

이제 우리가 원하는 Key 값을 upper_bound 메소드와, lower_bound 메소드에 넣어봅시다.

	private static int upper_bound(int key) {
		int start = 0;
		int end = array.length-1;
		int mid;
		while(start < end) {
			mid = (start + end)/2;
			if(array[mid] > key)
				end = mid;
			else start = mid + 1;
		}
		if(array[end] == key) end++;
		return end;
	}
	private static int lower_bound(int key) {
		int start = 0;
		int end = array.length-1;
		int mid;
		while(start < end) {
			mid = (start + end)/2;
			if(array[mid] >= key)
				end = mid;
			else start = mid+1;
		}
		return end;
	}

코드가 서로 크게 차이는 없습니다만,

다른 부분은

Lower bound 는 같거나 큰값,

Upper bound 는 큰 값을 구하므로,

if조건문에서 조금의 차이가 있습니다.

결과적으로 반환이 된다면,

	bw.append((upper - lower) + " ");

upper에서 lower의 값을 뺏을 때 해당 값을 얼마나 가지고 있는가를 알 수 있습니다.

숫자 카드2

« 네트워크 - Software Defined Networking 네트워크 - Software Defined Networking(2) »