AVL 트리는 자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree)의 한 종류로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 항상 1 이하를 유지하도록 설계된 자료구조입니다. 이 균형 조건 덕분에 삽입·삭제·탐색 연산이 항상 O(log n)의 시간 복잡도를 보장받을 수 있습니다.AVL 트리의 동작 원리노드가 삽입되거나 삭제될 때 트리의 균형이 깨질 수 있습니다. 이때 AVL 트리는 각 노드의 균형인수(Balance Factor), 즉 왼쪽 서브트리 높이에서 오른쪽 서브트리 높이를

이 글에서는 스플레이 트리(Splay Tree)를 C++로 구현하는 방법을 다룹니다. 스플레이 트리는 자가 조정(self-adjusting) 이진 탐색 트리의 일종으로, 특정 노드에 접근할 때마다 해당 노드를 루트 위치로 끌어올리는 splay 연산을 수행합니다. 덕분에 자주 사용되는 데이터일수록 트리 상단에 가까워져 접근 속도가 빨라지며, 별도의 균형 정보를 저장할 필요 없이 분할 상환(amortized) 시간 복잡도 O(log n)을 보장합니다.클래스 설명SplayTree 클래스는 아래와 같은 핵심 함수들로 구성됩니다.Splay(

seekg()는 C++의 iostream 라이브러리에 포함된 함수로, 파일 내 임의의 위치로 자유롭게 이동(seek)할 수 있게 해줍니다. C++ 파일 처리에서 주로 입력 스트림으로부터 다음에 추출할 문자의 위치를 지정할 때 사용됩니다.문법istream& seekg(streamoff offset, ios_base::seekdir dir);istream& seekg(streampos position);각 매개변수의 의미는 다음과 같습니다.position: 스트림 버퍼에서의 새로운 위치입니다.offset: dir 매개변수

C++에서 예외 처리(Exception Handling)란 프로그램 실행 중에 발생하는 런타임 오류를 처리하는 메커니즘을 말합니다. 예외(Exception)는 프로그램이 실행되는 도중에 발생(throw)되는 이벤트로, C++의 모든 표준 예외는 std::exception 클래스를 기반으로 파생됩니다. 만약 예외를 적절히 처리하지 않으면, 프로그램은 예외 메시지를 출력한 뒤 비정상적으로 종료됩니다. C++ 표준에서는 <exception> 헤더를 통해 다양한 예외 클래스를 정의하고 있으며, 이를 프로그램 안에서 자유롭게 활

C++와 Java는 모두 예외 처리(Exception Handling) 메커니즘을 제공하지만, 두 언어 사이에는 몇 가지 중요한 차이점이 존재합니다. 이러한 차이를 이해하면 각 언어의 설계 철학과 실무 활용 방식을 더 깊이 파악할 수 있습니다.C++와 Java 예외 처리 비교표Java의 예외 처리C++의 예외 처리Throwable 클래스를 상속받은 객체만 던질 수 있습니다.모든 타입(int, 문자열, 객체 등)을 예외로 던질 수 있습니다.finally 블록이 존재하며, try-catch 블록 실행 후 리소스 정리 등을 위해 반드시

이 글에서는 C++을 사용하여 Set(집합)을 활용한 다익스트라(Dijkstra) 알고리즘을 구현하는 방법을 알아봅니다. 다익스트라 알고리즘은 주어진 시작 정점을 루트로 하는 최단 경로 트리(shortest path tree)를 생성하는 대표적인 최단 경로 알고리즘입니다.구현 과정에서는 두 개의 집합이 필요합니다. 하나는 최단 경로 트리에 이미 포함된 정점들을 관리하는 집합이고, 다른 하나는 아직 최단 경로 트리에 포함되지 않은 정점들을 관리하는 집합입니다. 매 단계마다 아직 포함되지 않은 집합에서 시작 정점으로부터의 거리가 가장

개요그래프 색칠(Graph Coloring)은 인접한 두 정점이 서로 같은 색을 갖지 않도록 그래프의 모든 정점에 색을 할당하는 고전적인 알고리즘 문제입니다. 이 글에서는 가장 널리 쓰이는 해결 방식인 탐욕(Greedy) 색칠 알고리즘을 C++로 구현하는 방법을 단계별로 살펴봅니다.탐욕 색칠은 정점을 순서대로 하나씩 처리하면서, 이미 색칠된 인접 정점들이 사용 중이지 않은 가장 작은 번호의 색을 배정하는 방식으로 동작합니다. 모든 경우에 최소 색상 수를 보장하지는 않지만, 구현이 간단하고 실행 속도가 빨라 실무에서 폭넓게 활용됩니다

두 정점 사이에서 동일한 간선(에지)을 공유하지 않는 경로, 즉 에지 분리 경로(edge-disjoint path)의 최대 개수를 구하는 것은 그래프 이론의 고전적인 문제입니다. 이 문제는 최대 유량(Max Flow) 문제와 밀접한 관련이 있으며, 모든 간선의 용량을 1이라고 생각하면 두 정점 간의 최대 유량 값이 곧 에지 분리 경로의 최대 수가 됩니다. 알고리즘 이 프로그램은 너비 우선 탐색(BFS)으로 증강 경로(augmenting path)를 찾는 포드-풀커슨(Ford-Fulkerson) 방식, 즉 에드몬즈-카프(Edmonds

이진 탐색 트리(Binary Search Tree, BST)는 정렬된 상태를 유지하는 이진 트리로, 모든 노드가 다음과 같은 성질을 만족해야 합니다.노드의 오른쪽 서브트리에는 부모 노드의 키보다 큰 키가 위치합니다.노드의 왼쪽 서브트리에는 부모 노드의 키보다 작은 키가 위치합니다.모든 키 값은 중복 없이 고유합니다.각 노드는 최대 두 개의 자식 노드만 가질 수 있습니다.이러한 구조 덕분에 BST는 탐색, 삽입, 삭제 연산을 평균적으로 O(log n)의 시간 복잡도로 빠르게 처리할 수 있습니다.클래스 설계 개요이 예제에서 구현하는 B

이 글에서는 포드-풀커슨(Ford-Fulkerson) 알고리즘을 활용하여 네트워크 플로우(Network Flow) 문제를 해결하는 C++ 프로그램을 소개합니다. 네트워크 플로우 문제는 시작점(source)에서 도착점(sink)까지 보낼 수 있는 최대 유량을 구하는 대표적인 그래프 알고리즘 문제로, 물류 운송, 통신망 설계 등 다양한 분야에 응용됩니다. 알고리즘 개요 전체 구현은 두 가지 핵심 함수로 구성됩니다. 시작 bfs(): 잔여 그래프(residual graph)에서 시작점 s부터 도착점 t까지의 경로가 존재하면

이 글에서는 그래프 이론의 대표적인 문제인 최대 유량(Maximum Flow)을 계산하기 위한 Edmonds-Karp 알고리즘을 C++로 구현하는 방법을 소개합니다. Edmonds-Karp 알고리즘은 Ford-Fulkerson 방법에 너비 우선 탐색(BFS)을 적용한 알고리즘으로, 시작 정점(소스)과 도착 정점(싱크) 사이의 최대 유량을 다항 시간 내에 효율적으로 구할 수 있습니다.알고리즘 개요Edmonds-Karp 알고리즘의 핵심 동작 과정은 다음과 같습니다.시작 edmondsKarp() 함수: 유량(flow

이 글에서는 First Fit Decreasing(FFD, 최초 적합 감소) 알고리즘을 사용하여 1차원 객체들을 M개의 Bin에 담을 때 필요한 최소 Bin 개수를 계산하는 C++ 프로그램을 소개합니다.First Fit Decreasing 알고리즘이란?Bin Packing 문제는 크기가 서로 다른 여러 객체를 정해진 용량의 Bin에 최대한 적게 나누어 담는 고전적인 최적화 문제입니다. First Fit Decreasing은 이를 해결하는 대표적인 근사 알고리즘으로, 다음과 같은 순서로 동작합니다.모든 객체를 크기가 큰 순서대로 내림

히스토그램(histogram)은 너비가 1인 여러 막대가 나란히 이어진 그래프로, 각 막대의 높이는 서로 다를 수 있습니다. 이 글에서는 스택(stack) 자료구조를 활용해 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 구하는 C++ 프로그램을 소개합니다. 스택 기반 접근 방식을 사용하면 모든 막대를 한 번씩만 처리하므로 O(n)의 시간 복잡도로 문제를 효율적으로 해결할 수 있습니다.getArea() 함수의 알고리즘스택을 이용한 핵심 아이디어는 각 막대를 그 막대의 높이를 유지하면서 좌우로 확장할 수 있는 가장 넓은 범위의

C++ 프로그래밍에서 std::string을 LPCSTR로 변환해야 하는 경우가 종종 있습니다. 이 글에서는 그 변환 방법을 자세히 알아보겠습니다.LPCSTR이란 무엇인가?LPCSTR은 Long Pointer to Constant STRing의 약자로, C 스타일 문자열(상수 문자 배열)에 대한 포인터를 의미합니다. 이는 마이크로소프트(Microsoft)가 Windows API에서 정의한 타입으로, 사용하려면 프로그램에 Windows.h 헤더 파일을 반드시 포함해야 합니다.변환 원리std::string을 LPCSTR처럼 사용할 수

이 글에서는 C++의 와이드 문자열(std::wstring)을 LPCWSTR로 변환하는 방법을 알아보겠습니다.LPCWSTR은 Long Pointer to Constant Wide STRing의 약자로, 말 그대로 와이드(wide) 문자로 구성된 상수 문자열에 대한 포인터를 의미합니다. 즉, 와이드 문자열을 와이드 문자 배열 형태로 변환하면 LPCWSTR을 얻을 수 있습니다.LPCWSTR은 마이크로소프트(Microsoft)가 정의한 타입이므로, 이를 사용하려면 프로그램에 Windows.h 헤더 파일을 반드시 포함해야 합니다.std::

이번 글에서는 C언어에서 string.h 헤더 파일과 반복문(루프)을 사용하지 않고 문자열의 길이를 구하는 방법을 알아보겠습니다.사실 문자열 길이를 구하는 문제는 string.h 없이도 아주 쉽게 해결할 수 있습니다. 일반적으로는 재귀 함수(recursive function)를 활용하면 되는데, 이번 예제에서는 재귀 대신 조금 다른 트릭을 사용해 보겠습니다.printf() 함수의 반환값 활용하기핵심 아이디어는 바로 printf() 함수의 반환값입니다. 많은 개발자들이 간과하는 사실인데, printf()는 화면에 출력한 문자의 개수를

개요 C 언어의 전처리기(preprocessor)는 본격적인 컴파일에 앞서 소스 코드를 먼저 처리하는 단계입니다. 이 전처리기에서 사용할 수 있는 특수 연산자 두 가지가 바로 문자열화 연산자(Stringize Operator)와 토큰 붙여넣기 연산자(Token Pasting Operator)입니다. 두 연산자 모두 매크로 정의 내부에서만 사용할 수 있으며, 매크로의 활용 범위를 크게 넓혀 주는 강력한 도구입니다. 문자열화 연산자(#) 문자열화 연산자는 전처리기에게 이 토큰을 문자열로 변환하라고 지시하는 연산자입니다. 매크로 정의에

이 글에서는 C++의 stringstream을 활용하여 10진수를 16진수 문자열로 변환하는 방법과, 반대로 16진수 문자열을 10진수로 변환하는 방법을 예제 코드와 함께 살펴봅니다.stringstream과 hex 조작자란?stringstream은 문자열 포맷팅, 파싱, 그리고 문자열을 숫자 값으로 변환하는 등 다양한 작업에 활용되는 C++의 강력한 기능입니다. hex는 입출력(IO) 조작자(manipulator)로, 입출력 스트림에 대한 참조를 매개변수로 받아 스트림을 조작한 후 조작된 스트림의 참조를 다시 반환합니다.그럼 먼저

이번 글에서는 C++의 문자열과 문자열 리터럴이 가진 또 다른 특성에 대해 알아보겠습니다. C++에서 두 문자열을 연결(concatenation)할 때는 몇 가지 중요한 규칙을 기억해야 합니다.문자열 연결의 기본 규칙x + y가 문자열 연결 표현식이라고 할 때, x와 y가 모두 string 타입이라면 그 결과는 문자열 x의 문자들 뒤에 문자열 y의 문자들이 이어진 새로운 복사본이 됩니다.피연산자 중 하나만 문자열 리터럴 또는 문자일 수 있으며, 둘 다 문자열 리터럴이어서는 안 됩니다. 만약 둘 다 리터럴이라면 연결이 이루어지지 않습

이번 글에서는 C++의 스택 해제(Stack Unwinding)가 무엇을 의미하는지 알아보겠습니다. 프로그램에서 함수를 호출하면 해당 함수의 주소 정보가 호출 스택(call stack)에 저장되고, 함수 실행이 끝나면 스택에서 주소가 꺼내지면서 이전에 중단된 지점부터 다시 작업을 이어가게 됩니다.스택 해제란?스택 해제는 런타임에 함수 호출 스택의 항목들을 제거하는 과정입니다. 이때 예외(exception)를 활용하면 스택의 요소들을 제거할 수 있습니다. 내부 함수에서 예외가 발생(throw)하면, 스택에 쌓여 있던 모든 항목이 제거