전체 글
-
동적 프로그래밍(Dynamic Programming, DP)문제 해결 기법 2025. 5. 29. 22:48
최적 부분 구조와 중복 계산을 해결하는 알고리즘의 핵심 기법#️⃣ 들어가며"최댓값", "최솟값", "최단 경로" 등을 구하고자 할 때, 단순히 가능한 모든 경우를 시도하면 계산량이 기하급수적으로 증가한다. 이러한 문제들 중 전체 문제가 부분 문제들의 최적 해를 조합한 결과라는 특징을 갖고 있다면 중복 계산을 줄이고 효율적으로 상태를 저장하는 기법, 즉 동적 프로그래밍(Dynamic Programming, DP)을 통해 시간 복잡도를 획기적으로 줄일 수 있다. 1️⃣ 동적 프로그래밍(Dynamic Programming, DP)📌 정의동적 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누고, 작은 문제의 정답을 저장해서 재활용함으로써 전체 문제의 정답을 효율적으로 구하..
-
최소극대화(MiniMax)문제 해결 기법 2025. 5. 24. 00:58
최적의 수를 선택하는 게임 AI의 핵심 전략#️⃣ 들어가며체스, 틱택토, 오목과 같은 턴제 전략 게임에서는 플레이어가 선택할 수 있는 모든 경우를 고려하여 최적의 수를 두는 것이 중요하다. 이러한 결정 과정을 효율적으로 수행하기 위해 사용하는 알고리즘이 바로 최소극대화(Minimax) 알고리즘이다. 최소극대화(Minimax)는 상대가 최선을 다할 것이라고 가정하고, 그 상황에서도 내가 최선을 선택할 수 있도록 해주는 전략으로, 인공지능 분야에서도 기본이 되는 핵심 알고리즘 중 하나이다. 1️⃣ 최소극대화 (Minimax)📌 정의최소극대화(Minimax)는 두 명의 플레이어가 번갈아 가며 게임을 진행할 때, 각 플레이어가 자신의 이득을 최대화(maximize)하려 하고, 상대의 이득은 최소화(minim..
-
슬라이딩 윈도우(Sliding Window)와 투 포인터(Two Pointer)문제 해결 기법 2025. 5. 18. 03:38
선형 탐색에서 시간 복잡도를 비약적으로 줄이는 두 가지 핵심 기법#️⃣ 들어가며배열이나 문자열의 연속된 구간에서 특정 조건을 만족하는 부분을 찾을 때 단순 브루트 포스 방식으로 풀 경우 시간 복잡도가 $O(N^{2})$가 되어 시간 초과가 발생한다. 이러한 문제를 선형 시간 $O(N)$에 해결할 수 있도록 도와주는 대표적인 기법이 슬라이딩 윈도우(Sliding Window)와 투 포인터(Two Pointer)이다. 1️⃣ 슬라이딩 윈도우 (Sliding Window)📌 정의슬라이딩 윈도우(Sliding Window)는 일정한 크기의 윈도우(구간)을 유지하면서 기존에 구한 결과를 재활용하여 새로운 값을 포함하고, 오래된 값을 제거하며 계산을 빠르게 갱신하는 기법이다. 🔨 구현 예제// 배열에서 연속..
-
누적합(Prefix Sum)과 차이 배열(Difference Array)문제 해결 기법 2025. 5. 13. 02:30
구간을 빠르게 읽고, 빠르게 업데이트하는 두 가지 핵심 기법#️⃣ 들어가며코딩 테스트를 풀다 보면 다음과 같은 요구를 자주 만난다.배열에서 특정 구간의 합을 빠르게 구하라배열의 특정 구간에 여러 번 더해라 해당 문제를 브루트 포스 방식으로 풀 경우 시간 초과가 발생하는 경우가 대다수이다. 전체 배열의 크기를 $N$, 주어진 쿼리의 수가 $M$이라고 할 경우, $O(N \times M)$의 시간이 걸리고, $N$과 $M$은 당연히 매우 큰 숫자가 주어지기 때문이다. 이럴 때 필요한 게 누적합(Prefix Sum)과 차이 배열(Difference Array)다. 1️⃣ 누적합 (Prefix Sum)📌 정의누적합(Prefix Sum)은 배열이나 행렬과 같은 자료구조에서, 특정 범위의 합을 빠르게 계산하기 ..
-
OOP Design Pattern - Behavioral Pattern 1프로그래밍 언어 2024. 10. 14. 22:28
Chain of ResponsibilityChain-of-Responsibility PatternA behavioral design pattern consisting of a source of command objects and a series of processing objectsEach processing object contains logic that defines the types of command objects that it can handleThe rest are passed to the next processing object in the chainA mechanism exists for adding new processing objects to the end of this chainVar..
-
SynchronizationCS/OS 2024. 4. 21. 23:03
Race Condition Synchronization Solve problem causing by accessing to shared resources. Without synchronization, it lead to incorrect results, called race condition. A way to coordinate threads (or processes) that use shared resources or their execution for correctness. Goal of synchronization is ensuring correct operation of cooperating threads. Race Condition The result by threads accessing sha..
-
ThreadsCS/OS 2024. 4. 17. 15:44
Terminologies Concurrency (동시성 / 병행성) : the ability of two or more threads to execute in interleaving (overlapping) time periods and proceed at same time. Parallelism (병렬성) : the ability of two or more threads to execute in overlapping at same time. Porcess (Task) : the unit of resource ownership A compound entity (a set of threads + a collection of resource) Thread (Lightweight process) : The u..
-
Hitbox Controller Refactoring 및 Hitbox Debug Tool게임 클라이언트 개발/MakeDNF 2024. 4. 17. 00:48
이번 글에선 Hitbox Controller 클래스와 Hitbox 클래스를 리펙토링 한 내용과 플레이 모드 진입 시 설정된 Hitbox가 정상적으로 작동하는지 Scene에서 확인할 수 있는 Debugging 툴에 대해 작성하고자 한다. 너의 역할은? 히트 박스의 범위 및 충돌 로직이 작성되어 있는 Hitbox 클래스와 이를 관리하는 HitboxController 클래스를 통해 2.5D 좌표계에서의 충돌 시스템을 구현했었다. Hitbox 클래스에서 HitboxType, Size, Offset, Pivot 멤버 변수를 통해 히트 박스의 범위를 minHitboxPos, maxHitboxPos로 계산하고, AABB 충돌 알고리즘을 구현한 멤버 함수를 통해 히트 박스의 충돌 검사 로직을 수행했다. HitboxCo..