C 또는 C++에서는 함수가 여러 개의 값을 직접 반환할 수 없습니다. return 문은 기본적으로 하나의 값만 돌려줄 수 있기 때문인데요, 다행히 몇 가지 트릭을 활용하면 하나의 함수 호출만으로 두 개 이상의 결과를 얻을 수 있습니다.대표적인 방법은 주소 전달(Call By Address)과 참조 전달(Call By Reference)입니다. 두 방식 모두 호출자(caller) 쪽에 결과를 저장할 변수를 미리 준비해 두고, 함수가 해당 변수의 메모리 공간에 직접 값을 기록하는 원리로 동작합니다. 주소 전달은 포인터를, 참조 전달은

C++에서 반복문을 실행할 때마다 서로 다른 난수를 생성하는 방법을 알아보겠습니다. 이 글에서는 0부터 특정 값까지의 범위에서 난수를 생성하며, 예제 프로그램에서는 최댓값을 100으로 설정했습니다.srand() 함수로 난수 시드 설정하기매번 다른 난수를 얻으려면 srand() 함수를 사용해야 합니다. 이 함수는 C++ 표준 라이브러리에 포함되어 있으며, rand() 함수가 사용하는 의사 난수 생성기의 시작점(시드)을 초기화하는 역할을 합니다.srand() 함수의 선언 형태는 다음과 같습니다.void srand(unsigned int

C/C++에서 void main과 int main의 차이점C/C++ 프로그래밍을 하다 보면 int main()을 사용하기도 하고, 때로는 void main()을 사용하기도 합니다. 그렇다면 이 둘은 정확히 어떤 차이가 있을까요?main() 함수의 역할main() 함수는 다른 일반 함수들과 마찬가지로 인자를 받고 값을 반환할 수 있습니다. 다만 한 가지 기억해야 할 중요한 점은, 프로그램의 실행이 바로 이 main() 함수에서 시작된다는 사실입니다. 즉, 운영체제(OS)가 이 함수를 호출하며, main()이 반환하는 값은 운영체제에

이 글에서는 C/C++ 프로그래밍을 통해 로컬 시스템의 호스트 이름(Host Name)과 IP 주소를 손쉽게 조회하는 방법을 알아봅니다. 소켓 관련 표준 라이브러리 함수 몇 가지만 활용하면 별도의 외부 도구 없이도 자신의 컴퓨터 정보를 코드로 확인할 수 있습니다.핵심 함수 살펴보기IP 주소와 호스트 이름을 얻기 위해 사용되는 주요 함수는 다음과 같습니다. 각 함수는 서로 다른 역할을 담당합니다.번호함수 및 설명1gethostname()로컬 컴퓨터의 표준 호스트 이름을 조회합니다.2gethostbyname()호스트 데이터베이스에서 특

트리(tree)는 사이클(cycle)을 하나도 포함하지 않는 연결 그래프입니다. 따라서 무방향 그래프(undirected graph)가 트리인지 판별하려면 그래프 내부에 사이클이 존재하는지만 확인하면 됩니다. 이 글에서는 깊이 우선 탐색(DFS)으로 사이클을 검출하는 방식을 통해 무방향 그래프가 트리인지 확인하는 C++ 프로그램을 살펴봅니다.동작 원리DFS로 그래프를 순회하던 중 이미 방문한 정점을 다시 만났을 때, 그 정점이 현재 정점의 직전(부모) 정점이 아니라면 현재 정점으로 돌아오는 또 다른 경로가 존재한다는 의미이므로 사이

그래프(graph)는 사이클(cycle)을 하나도 포함하지 않을 때 트리(tree)라고 할 수 있습니다. 이번 글에서는 DFS(깊이 우선 탐색)을 활용하여 주어진 방향 그래프(directed graph)가 트리인지 아닌지 판별하는 C++ 프로그램을 소개합니다. 핵심 개념 방향 그래프가 트리이기 위해서는 그래프 안에 어떤 사이클도 존재해서는 안 됩니다. DFS로 그래프를 탐색하는 도중, 현재 재귀 스택에 들어 있는 정점을 다시 만나는 경우(백 엣지, back edge)가 발생하면 사이클이 있다는 뜻이며, 이러한 그래프는 트리가 될

이 글에서는 피드백 아크 집합(Feedback Arc Set)을 찾는 C++ 프로그램을 살펴봅니다. 피드백 아크 집합에 속한 간선들을 그래프에서 제거하면, 해당 그래프는 사이클이 없는 방향성 비순환 그래프(DAG, Directed Acyclic Graph)로 변환됩니다. 이는 위상 정렬 등 선형 확장(Linear Extension)을 구하기 위한 필수 과정입니다.핵심 개념방향 그래프에 사이클이 존재하면 위상 정렬을 수행할 수 없습니다. 따라서 최소한의 간선을 제거하여 사이클을 끊어야 하는데, 이때 제거 대상이 되는 간선들의 집합을

전이 폐쇄(Transitive Closure)란?방향 그래프(directed graph)가 주어졌을 때, 그래프의 모든 정점 쌍 (i, j)에 대해 정점 i에서 정점 j가 도달 가능한지(reachable)를 판별할 수 있습니다. 여기서 도달 가능하다는 것은 정점 i에서 시작하여 정점 j에 이르는 경로(path)가 적어도 하나 존재한다는 의미입니다. 이렇게 모든 정점 쌍의 도달 가능성을 행렬 형태로 나타낸 것을 전이 폐쇄(Transitive Closure)라고 합니다.주어진 그래프 G의 전이 폐쇄를 구하는 데 가장 널리 사용되는 기법

이분 그래프란?이분 그래프(bipartite graph)는 그래프의 모든 정점을 두 가지 색으로 색칠할 수 있는 그래프를 의미합니다. 좀 더 엄밀히 말하면, 정점 집합을 서로 겹치지 않는 두 집합으로 나누었을 때 모든 간선이 두 집합 사이에만 존재하고 같은 집합 내부에는 간선이 없는 그래프입니다. 즉, 인접한 정점끼리는 항상 다른 색을 갖게 됩니다.이 글에서는 2색 알고리즘과 백트래킹(backtracking) 기법을 활용하여 주어진 그래프가 이분 그래프인지 아닌지를 판별하는 C++ 프로그램을 소개합니다.함수 구성 및 의사 코드알고리

이분 그래프(Bipartite Graph)란 그래프의 모든 정점을 두 가지 색으로 칠할 수 있으면서, 서로 인접한 정점끼리는 항상 다른 색을 갖도록 만들 수 있는 그래프를 의미합니다. 다시 말해, 같은 색으로 칠해진 정점들은 하나의 집합을 이루며, 간선은 항상 서로 다른 집합 사이에만 존재합니다.이 글에서는 BFS(너비 우선 탐색)를 활용하여 주어진 그래프가 이분 그래프인지 여부를 판별하는 C++ 프로그램을 살펴보겠습니다.알고리즘 동작 원리BFS 기반 이분 그래프 판별은 그래프 색칠 문제(k=2인 경우)를 응용한 방식입니다. 핵심

이분 그래프(Bipartite Graph)는 그래프의 모든 정점을 두 가지 색으로 칠할 수 있어서, 어느 정점도 인접한 정점과 같은 색을 갖지 않는 그래프를 의미합니다. 다시 말해, 정점들을 두 개의 집합으로 나누었을 때 모든 간선이 서로 다른 집합에 속한 정점들을 연결하는 구조입니다. 이 글에서는 DFS(깊이 우선 탐색)를 이용해 주어진 그래프가 이분 그래프인지 판별하는 C++ 프로그램을 살펴보겠습니다. 이분 그래프 판별 원리 DFS로 그래프를 순회하면서 시작 정점을 한 가지 색으로 칠하고, 인접한 정점에는 항상 반대 색을 칠합

개요이 글에서는 C++를 사용하여 그래프 행렬(Graph Matrix)의 역행렬(Inverse)을 구하는 프로그램을 소개합니다. 역행렬은 행렬이 비특이(non-singular), 즉 행렬식(determinant)이 0이 아닌 경우에만 존재합니다. 역행렬을 구하는 방법은 여러 가지가 있지만, 여기서는 수반 행렬(adjoint matrix)과 행렬식을 이용하는 고전적인 방법을 다룹니다.알고리즘 단계시작 함수 INV()를 통해 행렬의 역행렬을 구한다: 1. 함수 DET()를 호출하여 행렬식을 계산한다. 2.

위상 정렬(Topological Sorting)은 방향성 비순환 그래프(DAG, Directed Acyclic Graph)의 정점들을 선형 순서로 배열하는 기법으로, 모든 방향 간선 u → v에 대해 정점 u가 반드시 정점 v보다 앞에 오도록 정렬합니다. 만약 그래프가 DAG가 아니라면, 즉 사이클이 존재한다면 해당 그래프에 대한 위상 정렬은 불가능합니다.함수 구성 및 의사코드이 프로그램은 깊이 우선 탐색(DFS)을 재귀적으로 적용하여 위상 정렬을 수행합니다. 핵심 원리는 다음과 같습니다. 어떤 정점에서 출발한 DFS가 더 이상 방

해밀턴 순환(Hamiltonian Cycle)은 해밀턴 경로(Hamiltonian Path)의 마지막 정점에서 첫 번째 정점으로 이동하는 간선이 그래프에 존재하는 경우를 말합니다. 즉, 무방향 그래프에서 그래프의 모든 정점을 정확히 한 번씩만 방문하고 다시 시작점으로 돌아오는 경로입니다.이 문제는 대표적인 NP-완전 문제 중 하나로, 일반적으로 백트래킹(Backtracking) 기법을 사용하여 해결합니다. 후보 정점을 하나씩 경로에 추가해 보고, 해답으로 이어지지 않으면 이전 단계로 되돌아가 다른 정점을 시도하는 방식입니다.함수 구

DFS(깊이 우선 탐색)를 활용하면 주어진 방향 그래프가 약하게 연결(weakly connected)되어 있는지 강하게 연결(strongly connected)되어 있는지 판별할 수 있습니다. 이 글에서는 해당 문제를 해결하는 C++ 프로그램을 예제 코드와 함께 소개합니다. 핵심 개념: 약한 연결 vs 강한 연결 강하게 연결된 그래프란 그래프 내 임의의 두 정점 사이에 양방향 경로가 모두 존재하는 그래프를 의미합니다. 반면 약하게 연결된 그래프는 모든 간선의 방향을 무시하고 무방향 그래프로 간주했을 때에만 연결 그래프가 되는 경우를

색도 지수(Chromatic Index)란 주어진 그래프의 변 색칠(edge coloring)에 필요한 최소한의 색 개수를 의미합니다. 즉, 그래프의 모든 변을 서로 인접한 변끼리는 서로 다른 색을 갖도록 칠할 때 필요한 최대 색의 수입니다. 이 글에서는 C++를 이용해 순환 그래프(Cyclic Graph)의 색도 지수를 찾는 방법을 알아보겠습니다. 알고리즘 순환 그래프의 색도 지수를 구하는 절차는 다음과 같습니다. 시작 정점의 개수 n과 변의 개수 e를 입력받습니다. e개의 각 변에 대해 두 정점 쌍을 edge[][

그래프 이론에서 단절점(Articulation Point)은 해당 정점과 그 정점에 연결된 간선들을 제거했을 때 그래프가 둘 이상의 조각으로 분리되는 정점을 의미합니다. 연결되지 않은 무방향 그래프에서는, 특정 정점을 제거했을 때 연결 요소(Connected Component)의 개수가 증가한다면 그 정점이 단절점이 됩니다.알고리즘단절점을 찾기 위해 깊이 우선 탐색(DFS)을 활용합니다. DFS 트리에서 정점 w가 단절점이 되는 조건은 다음 두 가지 중 하나를 만족하는 경우입니다.w가 DFS 트리의 루트이면서, 자식 노드를 두 개

이 글에서는 C++를 사용하여 주어진 그래프 위에서 두 노드(정점) 사이에 경로가 존재하는지 확인하는 방법을 다룹니다. 그래프 탐색 기법을 활용하면 시작 정점에서 목적지 정점으로 도달할 수 있는지, 즉 도달 가능성(reachability) 여부를 손쉽게 판별할 수 있습니다.알고리즘아래 알고리즘은 큐(queue)를 이용한 그래프 순회 방식으로, 시작 정점 s에서 목적지 정점 d까지 도달 가능한지 검사하는 isReach() 함수의 동작 과정입니다.Begin    function isReach() :

DAG(방향성 비순환 그래프, Directed Acyclic Graph)에서 SSSP(Single Source Shortest Path, 단일 출발점 최단 경로)를 구하는 C++ 프로그램을 소개합니다. 이 프로그램은 다익스트라(Dijkstra) 알고리즘을 사용해 그래프의 시작 노드(0번 노드)에서 다른 모든 노드까지의 최단 경로 길이를 계산하며, 어떤 노드를 경유해서 도달하는지와 함께 각 정점까지의 최소 비용을 출력합니다. 알고리즘 다익스트라 알고리즘은 아직 방문하지 않은 노드 중 현재까지의 거리가 가장 짧은 노드를 하나씩 선택하

이 프로그램은 그래프의 에지 연결성(Edge Connectivity), 즉 브리지(Bridge)를 찾는 방법을 다룹니다. 브리지란 그래프에서 해당 간선을 제거했을 때 그래프가 연결이 끊어지는(disconnected) 간선을 의미합니다. 무방향 그래프에서 브리지를 하나 제거하면 연결 요소(connected component)의 개수가 증가하게 됩니다.이 알고리즘은 DFS(깊이 우선 탐색)를 기반으로 하며, 각 정점의 발견 순서(disc)와 도달 가능한 가장 낮은 정점(low) 값을 이용해 브리지를 효율적으로 판별합니다.함수 및 의사코