지배 집합(Dominating Set)은 그래프 이론에서 잘 알려진 NP-난해(NP-Hard) 문제입니다. 그래프가 주어졌을 때, 그래프의 모든 정점이 이 집합에 직접 속하거나 집합에 속한 어떤 정점과 인접해 있도록 만드는 최소 크기의 정점 집합을 찾는 것이 목표입니다.아래는 지배 집합 문제를 해결하기 위한 C++ 프로그램입니다. 이 프로그램은 탐욕적(greedy) 기법을 활용하여 근사 해를 빠르게 구합니다.알고리즘시작 정점의 개수와 간선의 개수를 입력받고, 각 간선의 양 끝점도 함께 입력받습니다. dominant()

이 글에서는 그래프 이론의 유명한 문제인 4색 문제(Graph Coloring Problem)를 백트래킹(backtracking) 기법으로 해결하는 C++ 프로그램을 소개합니다. 4색 문제란 지도 위의 인접한 영역에 서로 다른 색을 칠할 때 최대 4가지 색만으로 충분하다는 정리에 기반한 문제로, 그래프의 모든 정점을 인접한 정점끼리는 서로 다른 색이 되도록 칠하는 것을 목표로 합니다.알고리즘이 알고리즘은 크게 세 가지 함수로 구성됩니다.1. issafe() 함수현재 정점 v에 특정 색상을 배정해도 안전한지 검사하는 함수입니다. 먼저

바이징(Vizing) 정리는 단순 그래프(simple graph)의 색 지수(chromatic index)가 항상 최대 차수(max degree) 또는 최대 차수 + 1 중 하나라는 것을 말합니다. 여기서 색 지수란 그래프의 변(edge)을 색칠할 때 필요한 최대 색의 개수를 의미합니다.이 글에서는 바이징 정리를 구현하는 C++ 프로그램을 소개하고, 알고리즘과 실행 예제를 함께 살펴봅니다.알고리즘시작 그래프의 정점 개수와 변 개수를 입력받는다. 각 변을 이루는 정점 쌍을 입력받는다. 함수 EdgeColor()

이 글에서는 트립(Treap) 자료구조를 C++로 구현하는 방법을 다룹니다. 트립은 기본적으로 무작위화된 이진 탐색 트리(Randomized Binary Search Tree)로, 이진 탐색 트리의 성질과 최대 힙(Max Heap)의 우선순위 성질을 동시에 만족하는 구조입니다. 여기서는 삽입(insert), 삭제(delete), 탐색(search) 세 가지 핵심 연산을 살펴보겠습니다.주요 함수 개요rotLeft() — 좌회전 함수트리를 먼저 회전한 뒤 새 루트를 설정합니다.rotRight() — 우회전 함수트리를 먼저 회전한 뒤 새

이 글에서는 12시간제(AM/PM)로 표현된 시간을 24시간제 형식으로 변환하는 C++ 프로그램을 다룹니다. 오전과 오후를 구분하는 조건 처리 방법과 함께, setw()와 setfill()을 활용해 시·분·초를 항상 두 자리로 출력하는 방법까지 살펴봅니다. 변환 알고리즘 12시간제를 24시간제로 바꿀 때의 핵심 규칙은 다음과 같습니다. 오후(pm)이고 시간이 12보다 작은 경우 → 시간에 12를 더합니다. (예: 오후 1시 → 13시) 오후(pm) 12시인 경우 → 정오이므로 12를 그대로 사용합니다. 오전(am)이고 시간이 12

C++를 활용하여 “Happy Birthday”라는 생일 축하 메시지를 출력하는 프로그램을 살펴보겠습니다. 이 프로그램의 흥미로운 핵심은, 최종적으로 출력할 문자보다 ASCII 코드상 1만큼 앞선 문자들로 구성된 문자열을 미리 선언해 두고, 실행 과정에서 각 문자를 하나씩 증가시켜 원하는 문구를 완성한다는 점입니다.알고리즘시작 원하는 출력 문자보다 하나 앞선 문자로 구성된 문자열 str1을 준비합니다. (예: ‘H’ → ‘G’) 이 문자열을 포인터 p에 할당합니다. *p가 NULL이 아닌 동안 반복하는 while 루

C++의 중첩 for 반복문을 활용하면 콘솔 화면에 다이아몬드(마름모) 모양의 별(*) 패턴을 손쉽게 출력할 수 있습니다. 이 글에서는 다이아몬드 모양을 출력하는 C++ 프로그램의 알고리즘, 예제 코드, 그리고 실제 실행 결과까지 단계별로 자세히 살펴보겠습니다. 알고리즘 시작 행의 개수 n, 즉 다이아몬드 모양의 크기를 입력받습니다. 변수 i, j를 선언하고 space를 초기화합니다. space를 n-1로 설정합니다. i가 1부터 n까지 외부 for 반복문을 실행합니다. 공백을 출력하는 내

이 프로그램은 사용자가 입력한 정점(vertex)의 개수와 간선(edge)의 개수를 바탕으로 무작위(random) 무방향 그래프를 생성하고, 각 정점의 연결 상태를 출력합니다. 자기 루프(self-loop)와 중복 간선을 자동으로 걸러내므로, 유효한 단순 그래프가 만들어집니다.입력그래프를 구성할 정점의 개수와 간선의 개수를 순서대로 입력받습니다.출력생성된 그래프의 각 정점 번호와 해당 정점에 연결된 이웃 정점들의 목록을 출력합니다. 어떤 간선에도 연결되지 않은 정점은 고립 정점(isolated vertex)으로 표시됩니다.알고리즘B

유향 비순환 그래프(Directed Acyclic Graph, DAG)에서는 토폴로지 정렬(Topological Sort)을 사용하여 모든 정점을 선형 순서로 나열할 수 있습니다.다만 토폴로지 정렬은 오직 유향 비순환 그래프에서만 동작한다는 점에 유의해야 합니다. 또한 하나의 DAG에는 서로 다른 여러 개의 올바른 토폴로지 정렬 결과가 존재할 수 있습니다.이번 글에서는 토폴로지 정렬을 활용하여 그래프 내부에 사이클(cycle)이 존재하는지 판별하는 C++ 프로그램을 자세히 살펴보겠습니다.예시 개요그래프의 간선 정보를 인접 행렬 형태

위상 정렬(Topological Sort)이란?방향 비순환 그래프(Directed Acyclic Graph, DAG)에서는 위상 정렬을 이용해 모든 정점을 선형 순서로 나열할 수 있습니다. 위상 정렬은 선행 관계가 있는 작업들의 실행 순서를 결정할 때 유용하게 사용됩니다.단, 위상 정렬은 오직 방향 비순환 그래프(DAG)에만 적용할 수 있습니다. 그래프에 사이클이 존재하면 위상 정렬은 불가능합니다. 또한 하나의 DAG에는 두 가지 이상의 올바른 위상 정렬 결과가 존재할 수 있다는 점도 기억해야 합니다.다음 C++ 프로그램은 깊이 우

그래프 이론에서 정방향 에지(forward edge)란 깊이 우선 탐색(DFS)을 수행하는 도중, 어떤 노드가 자신의 자손(descendant) 노드를 가리키지만 트리 에지(tree edge)에는 해당하지 않는 간선을 의미합니다. 이번 글에서는 인접 행렬로 표현된 그래프에서 모든 정방향 에지를 찾아내는 C++ 프로그램을 살펴보겠습니다.이 프로그램은 DFS를 기반으로 동작하며, 탐색 과정에서 각 노드의 시작 시간(S_Time)과 종료 시간(L_Time)을 기록합니다. 이미 방문이 완료된 노드로 향하는 간선을 발견하면, 현재 노드의 시

스레드 이진 트리(Threaded Binary Tree)는 트리를 특정 순서대로 순회할 수 있도록 설계된 이진 트리입니다. 일반적인 이진 트리와 달리, 스택이나 재귀 호출 없이도 중위 순회(inorder traversal)를 더 빠르게 수행할 수 있다는 것이 가장 큰 장점입니다.스레드 이진 트리는 널(NULL) 포인터를 활용하는 방식에 따라 두 가지 유형으로 나뉩니다.스레드 이진 트리의 종류단일 스레드(Single Threaded)각 노드가 왼쪽 또는 오른쪽 한 방향으로만 스레드를 가지는 형태입니다. 즉, 모든 오른쪽 널 포인터가

이중성 변환(Duality Transformation)이란? 이중성 변환은 사영 기하학(projective geometry)에서 점과 직선을 서로 대응시키는 개념입니다. 평면 위의 한 점을 하나의 직선으로 바꾸거나, 반대로 하나의 직선을 한 점으로 바꿀 수 있으며, 이러한 상호 변환 관계를 통해 기하학적 문제를 새로운 관점에서 분석할 수 있습니다. 이 글에서는 선과 점의 이중성 변환을 구현한 C++ 프로그램을 소개합니다. 변환은 크게 두 가지 경우로 나눌 수 있습니다. 두 가지 변환 경우 경우 1: 점 (a, b)는 직선 y =

이 글에서는 주어진 세 개의 점이 한 직선 위에 있는지(일직선상에 있는지) 판별하는 C++ 프로그램을 소개합니다.판별 원리는 간단합니다. 세 점으로 삼각형을 만들었을 때 그 넓이가 0이라면, 세 점은 모두 한 직선 위에 있는 것입니다. 반대로 넓이가 0이 아니라면 세 점은 일직선상에 있지 않습니다.세 점 (x1, y1), (x2, y2), (x3, y3)으로 만들 수 있는 삼각형의 넓이는 다음 공식으로 구합니다.넓이 = 0.5 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))알고리즘 0

N-퀸(N-Queen) 문제는 체스판 위에 N개의 퀸을 배치하되, 어떤 퀸도 다른 퀸을 공격할 수 없도록 만드는 배치를 찾는 고전적인 알고리즘 문제입니다. 체스의 퀸은 가로, 세로, 대각선 어느 방향으로든 이동하며 공격할 수 있습니다. 따라서 모든 퀸은 서로 다른 행, 서로 다른 열, 그리고 서로 다른 대각선 위에 위치해야 합니다. 이 글에서는 0과 1로 이루어진 이진 행렬을 사용해 퀸의 위치를 표현하며, 가장 대표적인 사례인 8-퀸(8 Queens) 문제를 C++로 해결하는 방법을 단계별로 살펴봅니다. 문제 정의 입력 체스

이 글에서는 하나의 원본 문자열 안에서 특정 패턴(부분 문자열)이 몇 번, 어느 위치에 나타나는지 반복적으로 검색하는 C++ 프로그램을 다룹니다. 이러한 문자열 탐색 기법은 텍스트 편집기의 찾기 기능이나 대용량 문서 분석 등 다양한 곳에서 활용됩니다.알고리즘가장 기본적인 방법인 브루트 포스(Brute Force) 방식을 사용합니다. 원본 문자열의 각 위치에서 시작하여 패턴과 한 글자씩 비교하며 일치 여부를 확인합니다.시작 원본 문자열(org)과 검색할 패턴(patt)을 입력받는다. org_len = 원본 문자열의 길이

유한 오토마타 기반 문자열 검색이란?유한 개수의 상태를 가지는 오토마타를 유한 오토마타(Finite Automaton)라고 합니다. 여기서 소개하는 C++ 프로그램은 유한 오토마타를 이용해 문자열 검색을 수행합니다. 길이가 T인 텍스트 text[0 … T-1]과 길이가 P인 패턴 p[0 … P-1]이 주어졌을 때, 텍스트 안에서 패턴이 등장하는 모든 위치(인덱스)를 찾아 출력하는 것이 목표입니다.이 방식은 검색에 앞서 패턴에 대한 전이 테이블(Transition Table)을 미리 구성해 둡니다. 덕분에 실제 검색 단계에서는 텍스트

두 문자열 간의 레벤슈타인 거리(Levenshtein Distance)란 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 횟수를 의미합니다. 여기서 편집 연산은 다음 세 가지를 포함합니다.삽입(Insertion): 새로운 문자 하나를 추가삭제(Deletion): 기존 문자 하나를 제거치환(Substitution): 기존 문자 하나를 다른 문자로 교체예시: cat과 mat 사이의 레벤슈타인 거리는 1입니다. 첫 글자 c를 m으로 치환하는 연산 한 번만 수행하면 두 문자열이 같아지기 때문입니다.cat → mat (c를 m으로

카이사르 암호(Caesar Cipher)는 단일 문자 치환 암호(mono-alphabetic cipher)의 한 종류로, 평문(plaintext)의 각 알파벳을 다른 알파벳으로 치환하여 암호문(ciphertext)을 만드는 방식입니다. 치환 암호 기법 중에서도 가장 단순한 형태에 해당합니다. 이 암호 시스템은 흔히 시프트 암호(Shift Cipher)라고도 불립니다. 핵심 원리는 각 알파벳을 0부터 25 사이의 고정된 값만큼 이동(shift)시킨 다른 알파벳으로 바꾸는 것입니다. 이 방식에서는 송신자와 수신자가 사전에 알파벳을 이동

플레이페어 암호(Playfair Cipher)는 단순 치환 암호처럼 문자 하나씩 암호화하는 것이 아니라, 두 글자씩 쌍(pair)으로 묶어 암호화하는 방식입니다.플레이페어 암호에서는 가장 먼저 키 테이블(key table)을 생성합니다. 키 테이블은 평문을 암호화할 때 열쇠 역할을 하는 5×5 크기의 알파벳 격자입니다. 테이블에 들어가는 25개의 알파벳은 모두 고유해야 하며, 26개가 아닌 25개만 필요하기 때문에 일반적으로 알파벳 중 하나(J)는 표에서 제외됩니다. 따라서 평문에 J가 포함된 경우에는 I로 대체하여 처리합니다.송신