다이나믹 프로그래밍이번 포스트에서는 알고리즘 문제 풀이의 핵심 전략 중 하나인 다이나믹 프로그래밍 에 대해 자세히 알아보겠습니다. 아마 많은 분들이 한 번쯤 "DP 너무 어렵다", "점화식이 뭔지 모르겠다" 라고 느껴보셨을 겁니다. 저 역시 처음에는 같은 고민을 했고 그냥 외우기보다는 사고 과정을 이해하자고 마음먹으면서 조금씩 감을 잡게 됐습니다. 어려운 만큼, 최적화 문제를 푸는 데 매우 유용하기 때문에 다이나믹 프로그래밍에 대해 하나씩 파헤쳐 보기로 하겠습니다.다이나믹 프로그래밍(DP: Dynamic Programming) 이란?다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누고 작은 문제의 정답을 저장하여 재활용하는 알고리즘 기법입니다.쉽게 말하면, 한번 계산한 문제는 다시 풀지 않고 저장해서 쓰는..

이분탐색이번 포스트에서는 효율적인 탐색 기법 중 하나인 이분 탐색에 대해 자세히 알아보겠습니다.완전탐색보다 훨씬 빠르게 원하는 값을 찾을 수 있으며 알고리즘 문제에서 매우 자주 사용되는 필수 전략입니다.이분 탐색(Binary Search)이란?이분 탐색은 정렬된 배열에서 원하는 값을 빠르게 찾기 위해 탐색 범위를 절반씩 줄여나가는 방식의 알고리즘입니다.즉, 중간 값을 기준으로 절반씩 날리면서 탐색 범위를 좁혀나가는 방식입니다.시간복잡도는 O(log N)으로 빠르기 때문에 큰 데이터에서 유용하게 사용됩니다.동작 원리이분 탐색의 기본적인 흐름은 다음과 같습니다:배열이 오름차순(또는 내림차순)으로 정렬되어 있어야 한다.시작 인덱스(low)와 끝 인덱스(high)를 설정한다.중간 인덱스(mid)를 구한다.mid..

그리디 알고리즘이번 포스트에서는 문제 해결 전략 중 하나인 그리디 알고리즘에 대해 알아보겠습니다.가장 단순한 방법이지만 의외로 강력한 해법이 될 수 있는 접근 방식입니다.그리디 알고리즘(Greedy Algorithm)이란?문제를 해결할 때 현재 순간에 최선이라고 판단되는 선택을 반복하여 최종 해답에 도달하는 전략입니다."지금 이 순간 가장 최선의 선택을 하자" 라고 전략을 세워보는 겁니다.그리디 알고리즘은 지역적 최적해(Local Optimal Solution)를 찾아나가는 과정을 진행하면서, 최종적으로는 전역적 최적해(Global Optimal Solution)을 찾아나가는 방식을 목표로 합니다. 단, 항상 전역적 최적해를 보장할 수는 없습니다.적용 조건 (언제 사용할 수 있을까?)그리디 알고리즘이 항..

비트마스킹이번 포스트에서는 탐색 알고리즘과 자주 쓰이는 기법인 비트마스킹에 대해 알아보겠습니다.비트마스킹(Bitmasking) 이란?비트마스킹은 정수의 이진 표현을 이용해 상태를 표현하거나 조작하는 기법입니다.특히 방문 처리, 부분 집합 생성, 조합 문제 등에서 공간 효율성과 연산 속도를 높이는 데 유용합니다.예를 들어, 4개의 원소가 있을 때 0000부터 1111까지의 이진수를 통해 부분 집합을 표현할 수 있습니다.상태의미0000아무것도 선택하지 않음10102번, 4번 원소 선택1111모두 선택 우선, 비트마스킹에 대해 이해하려면 2진수 개념부터 이해가 필요하기 때문에 먼저 설명드리겠습니다.2진수(Binary)2진수는 2를 밑으로 하는 수 체계입니다.우리가 일상에서 사용하는 숫자는 10진수(Decima..

완전탐색과 백트래킹이번 포스트에서는 탐색 알고리즘 중 가장 기초적인 완전탐색과 백트래킹에 대해 알아보겠습니다.완전탐색(Brute Force) 이란?가능한 모든 경우의 수를 전부 시도해보는 탐색하는 알고리즘입니다.일명, Brute Force 또는 Exhaustive Key Search라고 불립니다.정답이 반드시 존재한다는 것이 보장된 상황에서 유용하며 직관적이고 구현이 간단합니다.하지만, 시간복잡도가 매우 높아질 수 있어 입력이 크면 시간 초과가 발생할 수 있습니다. 예시: 3개의 숫자 중 2개를 순서대로 뽑기#include #include using namespace std;vector arr = {1, 2, 3}; // 탐색할 숫자들vector visited(3, false); // 숫자 방문 여부..

트리 순회이번 포스트에서는 그래프 탐색 알고리즘 중 하나인 트리 순회에 대해서 알아보겠습니다.트리 순회(Tree Traversal)란?트리 구조에서 모든 노드를 특정한 순서로 한 번씩 방문하는 방법입니다.트리는 계층적 자료구조이므로 단순히 선형적으로 탐색하는 게 아니라 노드 간의 부모-자식 관계를 고려한 탐색 방식이 필요합니다.순회는 컴퓨터 구조, 파일 시스템 탐색, 수식 트리 평가 등 다양한 분야에서 활용됩니다.순회 방법으로는 전위 순회, 중위 순회, 후위 순회가 있습니다. ❓ 왜 여러가지 순회 방법이 존재하나요?트리는 방향성과 계층이 있는 구조이기 때문에 어떤 노드를 먼저 방문할지, 자식 노드를 언제 처리할지에 따라 의미가 달라지기 때문입니다.전위 순회(Preorder Traversal)자신(부모) ..