본문 바로가기

이분탐색2

[BAEKJOON]1920 수 찾기 문제 요약 알고리즘 분류: 이분탐색, 해시 난이도: Silver4 문제내용: A 배열안에 존재 하는지 찾아라 사이트: 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 문제풀이 이번 문제는 풀이 방법 두 가지를 설명 할것이다. 하나는 이분 탐색이고 다른 하나는 해시(key-value)로 풀것이다. 문제의 내용 보면 일반적으로 완전 탬색 할 경우에는 O(N^2)만큼 연산 해야 한다. N의 최대 개수.. 2024. 1. 4.
[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열 이론1. LIS이란? LIS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알jih3508.tistory.com  LIS, 최장 증가 부분 수열은 나열된 배열이나 리스트에서 원소를 몇개 제외하고 오름차순또는 내림차순으로 가징 긴 수열을 말한다 예를 들어 {1, 5, 3, 6, 7, 9, 4, 2, .. 2022. 11. 2.

티스토리툴바