본문 바로가기

이분탐색4

[Leetcode] 1760. Minimum Limit of Balls in a Bag 문제 요약알고리즘 분류: 이분탐색, 이진 탐색난이도: Medium문제내용:가방마다 공이 들어 있고, 우리는 특정 횟수만큼 가방을 나눌 수 있습니다.한 가방을 두 개로 나눌 때 각 가방에는 반드시 1개 이상 공이 있어야 한다.작업을 수행한 후 가능한 최소 패널티를 반환하세요.사이트 주소: https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag/문제풀이 이번 문제에는 이분탐색을 활용한 문제이다. 관련 내용은 밑에 글에서 확인 해보면 된다.https://jih3508.tistory.com/288 [알고리즘 이론] 이진 탐색(Binary Search)이진 탐색(Binary Search) 완벽 정리 🔍안녕하세요! 오늘은 프로그래밍에서 가장 기본적이면서도.. 2025. 6. 13.
[알고리즘 이론] 이진 탐색(Binary Search) 이진 탐색(Binary Search) 완벽 정리 🔍안녕하세요! 오늘은 프로그래밍에서 가장 기본적이면서도 중요한 알고리즘 중 하나인 **이진 탐색(Binary Search)**에 대해 알아보겠습니다. 이진 탐색은 "이분 탐색"이라고도 불리며, 코딩 테스트에서도 자주 출제되는 핵심 알고리즘입니다.🤔 이진 탐색이 뭔가요?이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾는 방법입니다.예를 들어 사전에서 단어를 찾을 때를 생각해보세요. 'S'로 시작하는 단어를 찾는다면, 처음부터 한 페이지씩 넘기지 않고 대략 중간쯤을 펼쳐서 확인한 다음, 그보다 앞쪽인지 뒤쪽인지 판단해서 범위를 좁혀나가죠? 바로 그 원리입니다!⚡ 왜 이진 탐색을 써야 할까요?속도 비교일반적인 순차 탐색 vs 이진 탐색을 비교해보겠습니다:📊.. 2025. 6. 13.
[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.

티스토리툴바