이분 탐색(Binary Search)은 코딩 테스트에서 많이 등장하는 알고리즘 중 하나이다.탐색 알고리즘 중 가장 기본적인 알고리즘으로, 특정 값을 빠르게 찾는 로직이다.오늘은 이분 탐색에 대해 정리해보도록 하겠다. 이분 탐색이란? 이분 탐색(Binary Search): 정렬된 배열에서 탐색 범위를 절반씩 줄여나가면서 특정 값을 찾는 알고리즘 이분 탐색 알고리즘의 중요한 포인트는 정렬된 배열이 필요하다는 점이다.왜냐하면 이분 탐색은 데이터가 정렬되었다는 가정 하에 동작하기 때문이다. 그렇다면 이분 탐색의 알고리즘이 어떻게 동작하는지 살펴보도록 하자.   이분 탐색의 원리 이분 탐색을 하기 위해서는 left, right, mid 3개의 위치값이 필요하다.이분 탐색의 알고리즘은 다음과 같이 동작한다. ① 초..

그리디 알고리즘은 각 단계에서 그 순간이 최선이라고 생각하며 선택하는 방식이다.겉보기엔 간단하고 직관적이지만 항상 최적의 해를 보장하지는 않는다.이번 포스터에선 그리디 알고리즘의 개념과 특징, 그리고 예시를 통해 알아보도록 하겠다.  그리디 알고리즘이란 무엇인가 그리디(Greedy): 문제를 해결할 때 각 단계에서 가장 최선이라고 생각되는 선택을 함으로써 전체 해를 구하는 방식  그리디를 사용하는 이유 그리디 알고리즘을 사용하면 많은 이점이 있습니다.완전 탐색이 아닌, 최적의 해를 구하는 성질에 의한 경우만 탐색하면 되기 때문입니다.  구현이 간단하고 빠름그리디 알고리즘은 성질에 따라 로직을 구현하면 되기 때문에 다른 알고리즘보다 구현하기 쉽다.  계산 속도가 빠름전체 경우가 아닌, 이미 성질에 의해 정..

비트마스크는 주어진 문제를 효율적으로 해결하기 위한 강력한 도구로, 특히 상태를 간단하게 표현하거나 부분 집합을 다룰 때 유용하다. 코딩 테스트에서는 메모리와 연산 시간을 절약할 수 있어 많이 활용되며, 비트 연산의 기본 개념만 이해해도 문제 해결에 큰 도움이 된다. 이번 글에서는 비트마스크의 기본 원리와 활용 예제를 통해 그 응용법을 살펴보겠다.  비트마스크(Bitmask)란? 비트 마스크: 비트 연산을 사용하여 데이터를 효율적으로 처리하는 기법 보통 상태를 표현하거나 조작할 때 유용하며, 특히 메모리를 절약하고 빠른 계산을 필요로 하는 상황에 유용하다. 이진수의 각 비트를 이용하여 여러 상태를 표현한다. 그래서 int형 value 하나로 32개의 Boolean 상태를 표현할 수 있다.이러한 구조를 통..

완전 탐색과 백트래킹은 코딩 테스트에서 중요한 탐색 기법으로, 문제에서 가능한 모든 경우의 수를 고려하여 최적의 해답을 찾는 데 사용된다. 오늘은 완전 탐색과 백트래킹이 어떤 개념인지 알아보도록 하겠다. 완전 탐색 (Brute Force)  완전 탐색(Brute Force)은 모든 가능한 경우를 무식하게 하나하나 다 확인하는 방식으로 문제를 해결한다. 가능한 모든 조합, 모든 배열 등을 전부 시도해본 뒤 조건에 맞는 결과를 찾는다.따라서 완전 탐색은 가장 단순한 방법이지만, 시간 복잡도가 클 수 있으니 입력의 크기를 잘 확인해야 한다. 간단한 문제로 확인해보겠다.   백준 2309번: 일곱 난쟁이https://www.acmicpc.net/problem/2309 ✅ 코드 확인더보기#include #incl..

순열과 조합은 코딩 테스트에서 자주 등장하는 개념으로, 데이터를 나열하거나 선택하는 문제를 해결하는 데 필수적이다.  이러한 개념을 이해하고 활용하면 효율적인 알고리즘 설계와 문제 해결에 큰 도움이 된다. 오늘은 순열과 조합에 대해 개념과 코드에 대해 알아보도록 하겠다. 순열(permutation) 순열(permutation): 여러 개의 요소를 특정 순서에 따라 배열하는 경우의 수  예를 들어, 3개의 숫자 1, 2, 3을 모두 사용해 순열을 구하는 경우 P(3, 3) = 3! = 6이 되어 6가지 경우의 수가 나온다.- (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) 시간 복잡도는 얼마일까?O(n!)이다. n개의 요소가 있다면 첫 번..