[BOJ] 1920번: 수 찾기

2022. 4. 19. 19:38· BOJ 백준/이분탐색
목차
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
728x90
반응형

https://www.acmicpc.net/problem/1920

 

1920번: 수 찾기

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들

www.acmicpc.net

문제

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을 출력한다.

 

풀이

📙이분 탐색(Binary Search)

탐색범위를 절반 씩 줄여나가면서 값을 찾는 알고리즘이다.

이분 탐색하기 위해 우선 입력받은 숫자 배열을 오름차순으로 정렬한다.

start는 배열의 첫 번째, end는 배열의 마지막, mid는 start와 end의 중간 index라 하자.

start가 end 위치를 넘어가기 전까지 반복문을 실행하여

배열의 mid번째 원소가 찾으려는 값과 같다면 탐색을 끝낸다.

만약 찾으려는 값이 배열의 mid 번째 원소보다 크다면 mid+1부터 end까지를 다시 탐색하고,

mid 번째 원소보다 작다면 start부터 mid-1 까지를 다시 탐색한다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int arr[100001] = {0,};

// 이분탐색
void search(int x) {
  int start = 0;
  int end = n-1;
  int mid;

  while(end >= start) {
    mid = (start+end)/2;
    if(arr[mid] == x) {
      cout << "1\n";
      return;
    }
    else if(arr[mid] > x) {
      end = mid-1;
    }
    else {
      start = mid+1;
    }
  }
  cout << "0\n";
  return;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int a, m, b;
  cin >> n;

  
  for(int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  sort(arr, arr+n);

  cin >> m;
  for(int i = 0; i < m; i++) {
    cin >> b;
    search(b);
  }
}

숫자를 입력받아 배열에 해당 인덱스 번호가 있을 경우 그 위치에 1을 넣어 그 숫자가 있는지 없는지 확인하려 했는데 입력받을 수 있는 수의 범위가 -231 ~ 231 이므로 배열을 선언할 수 없어 이 방법은 적합하지 않았다. 

 

결과

728x90
반응형

'BOJ 백준 > 이분탐색' 카테고리의 다른 글

[BOJ] 12015번: 가장 긴 증가하는 부분 수열  (0) 2023.08.22
[BOJ] 2565번: 전깃줄  (0) 2023.08.22
C++ Lower Bound & Upper Bound  (0) 2023.08.22
[BOJ] 2805번: 나무 자르기  (0) 2021.07.29
  1. 문제
  2. 입력
  3. 출력
  4. 풀이
  5. 코드
  6. 결과
'BOJ 백준/이분탐색' 카테고리의 다른 글
  • [BOJ] 12015번: 가장 긴 증가하는 부분 수열
  • [BOJ] 2565번: 전깃줄
  • C++ Lower Bound & Upper Bound
  • [BOJ] 2805번: 나무 자르기
코블리_vv
코블리_vv
코블리_vv
코딩 놀이터
코블리_vv
전체
오늘
어제
  • 분류 전체보기 (67)
    • CS 노트 (1)
    • 대외활동 (0)
      • 창업 동아리 (0)
    • AWS (0)
      • AWS Academy Cloud Architect.. (0)
      • AWS Lab (0)
    • 웹 개발 노트 (3)
      • 웹 프로젝트 (0)
      • 스프링 인 액션 (0)
      • 스프링 입문을 위한 자바 객체 지향의 원리와 이해 (0)
    • ORACLE (0)
    • TOPCIT (2)
      • M1 소프트웨어 개발 (2)
      • M2 데이터 이해와 활용 (0)
    • 캡스톤 (5)
    • BOJ 백준 (53)
      • 브루트포스 (1)
      • 정렬 (6)
      • 이분탐색 (5)
      • 맵 (2)
      • 다이나믹 프로그래밍 (11)
      • 수학 (5)
      • 그리디 (3)
      • 분할정복 (4)
      • DFS (3)
      • BFS (6)
      • 그래프 (4)
      • 자료구조 (1)
      • 백트래킹 (2)
    • 코딩 테스트 (0)
      • 코드트리 (0)
    • 대회 (0)
    • Spring Boot (3)
      • JPA (3)

블로그 메뉴

  • 홈
  • 태그
  • 알고리즘
  • BOJ 백준
  • 방명록

공지사항

인기 글

태그

  • 백준 n과m
  • backtrader
  • 시스템 트레이딩
  • 우선순위 큐
  • 다이나믹프로그래밍
  • 분할정복
  • 다이나믹 프로그래밍
  • 투자 전략
  • 너비우선탐색
  • BFS
  • dfs
  • 백준 토마토
  • 투자
  • 백트래킹
  • 파이썬 backtrader
  • binary search
  • 플로이드 와샬
  • 암호학
  • java
  • 재귀
  • 1676
  • 웹개발
  • 이분탐색
  • spring
  • dp
  • 스프링인액션
  • computer security
  • 그리디 알고리즘
  • 컴퓨터 보안
  • n과m

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
코블리_vv
[BOJ] 1920번: 수 찾기
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.