이 글에서는 C++에서 문자열의 일부(부분 문자열)를 다른 문자열로 교체하는 방법을 살펴봅니다. std::string 클래스가 제공하는 replace() 함수를 사용하면, 문자열에서 pos 위치부터 시작하여 len개의 문자에 해당하는 구간을 지정한 새로운 문자열로 손쉽게 대체할 수 있습니다.replace 함수의 기본 구조string& replace(size_t pos, size_t len, const string& str, size_t subpos, size_t sublen);주요 매개변수pos: 교체 작업이 시작되는

개요 이 글에서는 스택(Stack) 자료구조를 활용하여 괄호의 균형 여부를 확인하는 방법을 살펴봅니다. 단순히 여는 괄호와 닫는 괄호의 개수만 세는 것이 아니라, 각 괄호가 올바른 순서로 짝을 이루고 있는지까지 검사합니다. 예를 들어 표현식 [{}(){()}]는 올바른 반면, {[}]는 닫는 괄호의 순서가 어긋나므로 올바르지 않습니다. 입력: 괄호가 포함된 표현식 {()}[] 출력: 균형이 맞습니다(Balanced) 알고리즘 괄호 균형 검사는 다음과 같은 절차로 진행됩니다. 1단계: 괄호를 저장할 스택을 정의합니다. 2단계: 표현

이번 글에서는 스택(Stack) 자료구조를 활용하여 10진수를 2진수로 변환하는 C++ 프로그램을 살펴봅니다.10진수를 2진수로 변환하는 기본 원리는 숫자를 2로 계속 나누면서 나머지(remainder)를 구하는 것입니다. 이때 나머지는 구해진 순서의 역순, 즉 마지막에 구한 값부터 처음 값까지 거꾸로 읽어야 최종 2진수가 됩니다. 스택은 LIFO(Last In First Out, 후입선출) 구조이므로, 나머지를 차례대로 저장했다가 꺼내면 자동으로 역순으로 출력되기 때문에 이 문제에 가장 적합한 자료구조입니다.입력: 10진수 13

수학적 표현식을 컴퓨터로 계산하려면 일반적인 중위 표기법(infix) 대신 전위 표기법(prefix) 또는 후위 표기법(postfix) 형태로 변환해야 합니다. 중위 표기식을 후위 표기식으로 변환한 뒤에는 후위 표기식 평가 알고리즘을 적용하여 정확한 답을 구할 수 있습니다.이때 핵심적으로 사용되는 자료구조가 바로 스택(Stack)입니다.동작 원리후위 표기식을 왼쪽부터 한 문자씩 차례로 읽어 나가며 다음과 같이 처리합니다.피연산자(숫자)를 만나면: 해당 값을 스택에 push합니다.연산자를 만나면: 스택에서 두 개의 값을 pop하고,

이 글에서는 C++를 이용해 스택(Stack) 자료구조를 구현하는 방법을 단계별로 살펴봅니다. 스택은 요소들의 집합을 저장하는 추상 자료구조로, LIFO(Last In First Out), 즉 나중에 들어간 데이터가 가장 먼저 나온다는 원칙을 따릅니다.스택의 핵심 연산은 다음과 같습니다.Push(푸시) – 스택의 맨 위(top)에 새로운 데이터를 추가합니다.Pop(팝) – 스택의 맨 위에 있는 데이터를 제거합니다.Peek(픽) – 스택의 맨 위 데이터를 제거하지 않고 값만 확인합니다.동작 원리예를 들어 스택에 11, 22, 33,

그래프의 인접 리스트(Adjacency List) 표현은 연결 리스트(linked list)를 기반으로 하는 방식입니다. 이 표현법에서는 리스트들의 배열을 사용하며, 배열의 크기는 V입니다. 여기서 V는 그래프의 정점(vertex) 개수를 의미합니다. 다시 말해, 서로 다른 V개의 리스트를 저장할 수 있는 배열을 하나 만들어 두는 것입니다. 만약 어떤 리스트의 헤더가 정점 u라면, 해당 리스트에는 u에 인접한 모든 정점들이 담기게 됩니다.인접 리스트 표현의 복잡도무방향 그래프의 경우 O(V+2E), 방향 그래프의 경우 O(V+E)의

그래프의 인접 행렬이란? 그래프의 인접 행렬(Adjacency Matrix)은 V × V 크기의 정방행렬로, 여기서 V는 그래프 G의 정점(vertex) 개수를 의미합니다. 이 행렬에서는 행과 열 양쪽 축에 V개의 정점이 배치됩니다. 만약 그래프에 정점 i에서 정점 j로 향하는 간선이 존재한다면, 인접 행렬의 i번째 행과 j번째 열 위치에 1이 기록됩니다(가중치 그래프라면 해당 가중치 값처럼 0이 아닌 값이 저장됨). 반대로 간선이 존재하지 않으면 그 자리에는 0이 들어갑니다. 인접 행렬 표현의 복잡도 인접 행렬 표현은 생성 시

볼록 껍질(Convex Hull)이란?볼록 껍질(Convex Hull)은 주어진 모든 데이터 점들을 포함할 수 있는 가장 작은 닫힌 영역을 의미합니다. 쉽게 말해, 평면 위에 흩어져 있는 점들을 고무줄로 감쌌을 때 고무줄이 만드는 외곽선이라고 생각하면 이해하기 쉽습니다.그레이엄 스캔(Grahams Scan) 알고리즘은 이러한 볼록 껍질의 꼭짓점(경계점)을 효율적으로 찾아내는 대표적인 기하학 알고리즘입니다.그레이엄 스캔 알고리즘의 동작 원리그레이엄 스캔은 다음과 같은 단계로 진행됩니다.시작점 선택: 가장 아래에 있는 점(y 좌표가 가

Jarvis March(자비스 행진) 알고리즘은 주어진 점(point) 집합으로부터 볼록 껍질(convex hull)의 꼭짓점을 찾아내는 대표적인 계산 기하학 알고리즘입니다.이 알고리즘은 데이터 집합에서 가장 왼쪽에 있는 점에서 출발하여, 반시계 방향으로 회전하면서 볼록 껍질에 속하는 점들을 하나씩 선택해 나갑니다. 현재 점을 기준으로 나머지 점들의 방향(orientation)을 검사하고, 그중 가장 바깥쪽 각도를 이루는 점을 다음 후보로 채택합니다. 모든 점을 돌아 다음 점이 다시 시작점이 되는 순간 알고리즘을 종료합니다.입력:

최장 증가 부분 수열(LIS)이란?최장 증가 부분 수열(Longest Increasing Subsequence, LIS)은 주어진 수열에서 원소들의 순서를 유지하면서, 각 원소가 바로 앞 원소보다 항상 크도록 뽑아낸 부분 수열 중 가장 긴 것을 의미합니다.이번 글에서는 정수들의 집합이 주어졌을 때, 최장 증가 부분 수열의 길이를 구하는 방법을 살펴보겠습니다.입력: 정수 집합 {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15} 출력: 최장 증가 부분 수열의 길이 → 6 해당 부분 수열은

C++에서 함수에 객체를 전달하는 방식은 크게 값 전달(Pass by Value), 참조 전달(Pass by Reference), 포인터 전달(Pass by Pointer) 세 가지로 나뉘며, 여기에 const를 조합한 변형들이 있습니다. 클래스 X의 객체를 함수 fun에 전달한다고 가정하고, 각 방식의 동작 원리와 차이점을 코드 예제와 함께 살펴보겠습니다.1. 값으로 전달 (Pass by Value)객체를 값으로 전달하면 함수 스코프 안에 해당 객체의 얕은 복사본(shallow copy)이 새로 생성됩니다. 따라서 함수 내부에서

C++ 프로그램의 main 함수에서 자주 보이는 int argc와 char *argv[]는 각각 다음과 같은 의미를 가집니다.argc: argument count(인자 개수)의 줄임말로, 프로그램에 전달된 인자의 총 개수를 나타냅니다.argv: argument values(인자 값)의 줄임말로, 전달된 인자들을 문자열 배열 형태로 저장합니다.이 두 변수는 프로그램이 실행을 시작할 때 main 함수로 자동으로 전달됩니다. 프로그램을 실행할 때 명령줄(command line)을 통해 인자를 함께 넘겨줄 수 있는데, 예를 들어 다음과 같

C++에서는 형 변환(casting)을 수행하는 방법이 여러 가지 있습니다. 각 캐스트 연산자는 용도와 안전성이 다르기 때문에, 상황에 맞는 올바른 캐스트를 선택하는 것이 중요합니다. 이 글에서는 static_cast, dynamic_cast, 그리고 C 스타일 캐스트(일반 캐스트)의 차이점을 살펴보고, 추가로 사용할 수 있는 const_cast와 reinterpret_cast까지 함께 정리해 드립니다.1. static_cast — 일반적인 타입 변환static_cast는 컴파일 시점에 검사되는 일반적인 형 변환에 사용됩니다. 암시

C 언어와 C++ 언어에서 구조체를 선언하고 사용하는 방식에는 미묘하지만 중요한 차이가 있습니다. 이 글에서는 struct와 typedef struct의 차이점을 C와 C++ 관점에서 각각 살펴보겠습니다. C 언어에서의 차이점 기본적으로 struct 키워드는 구조체(structure)를 정의하는 데 사용됩니다. 하지만 C 언어에서는 정의한 구조체를 실제로 사용할 때마다 struct 키워드를 반복해서 붙여야 한다는 번거로움이 있습니다. struct Point { int x; int y; }; struct Point

데이터 은닉(Data Hiding)은 객체 지향 프로그래밍(OOP)의 핵심 기능 중 하나로, 프로그램의 함수가 클래스 타입의 내부 표현에 직접 접근하는 것을 막아줍니다. 이러한 접근 제한은 클래스 본문 안에서 public, private, protected라는 접근 지정자(access modifier) 섹션을 통해 지정할 수 있습니다.특별히 접근 지정자를 명시하지 않으면, 클래스 멤버와 클래스 자체의 기본 접근 수준은 private으로 설정됩니다.예제 코드class Base { public: // public 멤버는

C++에서 증감 연산자 ++는 접두사(전위, prefix) 형태와 접미사(후위, postfix) 형태로 사용할 수 있으며, 두 버전 사이에는 중요한 동작상의 차이가 있습니다.전위 연산자(++i): 먼저 i의 값을 1 증가시킨 후, 표현식의 결과값은 증가된 새로운 값이 됩니다. 즉, 값을 먼저 증가시키고 그 결과를 표현식에 반환합니다.후위 연산자(i++): i의 값은 결국 1 증가하지만, 표현식의 결과값은 증가하기 전의 원래 값입니다. 즉, 기존 값을 먼저 표현식에 할당한 뒤 변수를 증가시킵니다.코드 예제를 통해 좀 더 자세히 이해해

이분 그래프(bipartite graph)는 두 가지 색만 사용해 모든 정점을 채색할 수 있는 그래프를 말합니다. 즉, 같은 집합에 속한 정점들은 서로 동일한 색으로 칠해지며, 인접한 정점끼리는 항상 다른 색을 갖게 됩니다. 이 프로그램에서는 이분 그래프를 입력으로 받아 BFS(너비 우선 탐색) 방식으로 각 정점에 색을 입히고, 그 결과를 출력합니다. 이분 그래프의 개념 이분 그래프는 정점들을 두 개의 집합으로 나누었을 때, 모든 간선이 서로 다른 집합에 속한 정점 사이에만 존재하는 그래프입니다. 대표적인 예로 트리(tree)는 항

무방향 그래프 G의 선 그래프(Line Graph) L(G)는 원본 그래프 G의 에지(간선)들 사이의 인접 관계를 표현하는 또 다른 그래프입니다. 즉, 원본 그래프의 각 에지가 선 그래프에서는 하나의 정점이 되며, 두 에지가 원본 그래프에서 정점을 공유할 때 선 그래프에서 서로 연결됩니다.이 글에서는 입력으로 주어진 그래프의 선 그래프를 생성한 뒤, 해당 선 그래프에 대해 에지 컬러링(Edge Coloring)을 수행하는 C++ 프로그램을 살펴봅니다.알고리즘시작 정점의 개수 n과 에지의 개수 e를 입력받는다. 그래프의

DAG(Directed Acyclic Graph, 방향 비순환 그래프)는 간선에 방향이 존재하면서도 사이클(cycle)을 형성하지 않는 그래프를 의미합니다. 즉, 모든 간선은 한 방향으로만 진행되며, 어떤 정점에서 출발해도 다시 자기 자신으로 돌아오는 경로가 존재하지 않습니다. 이 글에서는 주어진 그래프가 DAG인지 판별하는 C++ 프로그램을 소개합니다.알고리즘핵심 아이디어는 다음과 같습니다. 인접 리스트를 순회하면서 나가는 간선(outgoing edge)이 없는 정점을 찾고, 해당 정점을 발견할 때마다 카운트를 증가시킵니다. 전체

이 글에서는 C++를 이용해 그래프 구조 스택(Graph Structured Stack)을 구현하는 방법을 소개합니다. 그래프 구조 스택은 여러 개의 분기 경로가 존재하거나 서로 다른 경로가 한 노드로 합쳐질 수 있도록 일반 스택을 확장한 자료구조로, GLR 파싱 등 컴파일러 이론과 자연어 처리 분야에서 널리 활용됩니다. 그래프 구조 스택의 동작 원리 주어진 그래프를 인접 행렬로 표현한 뒤, 시작 노드(source)에서 깊이 우선 탐색과 유사한 방식으로 탐색을 진행합니다. 각 노드를 방문할 때마다 스택에 push하고, 부모 노드 정