언어 L이 주어졌을 때, 해당 언어에 대한 푸시다운 오토마타(Pushdown Automata, PDA)를 구성하는 것이 목표입니다. 이 언어에서 1의 개수는 0의 개수와 2의 개수를 더한 값과 같아야 하며, 0과 2는 최소 한 번씩 나타나거나 문자열이 NULL(빈 문자열)일 수도 있습니다. 빈 문자열 역시 오토마타가 수용해야 합니다. 푸시다운 오토마타란? 푸시다운 오토마타(PDA)는 정규 문법을 위해 결정적 유한 오토마타(DFA)를 설계하는 방식과 유사하게, 문맥 자유 문법(context-free grammar)을 구현하는 기법

언어 L = {0n1m2m3n | m, n ≥ 0}가 주어졌을 때, 이 언어를 인식하는 푸시다운 오토마타(Pushdown Automata, PDA)를 구성하는 것이 과제입니다. 이 언어에서는 0의 개수와 3의 개수가 같아야 하고, 1의 개수와 2의 개수가 같아야 합니다. 또한 지수 m과 n은 0 이상이므로, 모든 숫자가 한 번 이상 나타나야 하는 것은 아니며 빈 문자열(NULL) 역시 유효한 문자열로서 오토마타에 의해 수용되어야 합니다.푸시다운 오토마타란 무엇인가?푸시다운 오토마타(PDA)는 정규 문법(regular grammar)

언어 L이 주어졌을 때, 우리의 과제는 이 언어에 대한 푸시다운 오토마타(Pushdown Automata, PDA)를 구성하는 것입니다. 이 언어는 문자 a의 등장 횟수가 문자 b의 등장 횟수의 정확히 두 배이고, 문자 c의 등장 횟수가 문자 d의 등장 횟수의 정확히 네 배여야 함을 의미합니다. 또한 모든 문자의 최소 등장 횟수는 1회이지만, m과 n이 0일 수 있으므로 NULL(빈) 문자열 역시 유효하며, 이러한 문자열도 오토마타에 의해 받아들여져야 합니다.푸시다운 오토마타란 무엇인가?푸시다운 오토마타(PDA)는 정규 문법(reg

문제 개요 각 노드에 숫자 형태의 가중치가 부여된 이진 트리가 주어졌을 때, 노드의 가중치에 X(temp)를 더한 값이 피보나치 수가 되는 노드의 개수를 구하는 것이 이 글의 목표입니다. 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13…과 같이 n번째 항이 (n−1)번째 항과 (n−2)번째 항의 합으로 정의되는 수열입니다. 예를 들어 어떤 노드의 가중치가 12이고 temp가 1이라면 12+1=13은 피보나치 수이므로 이 노드는 개수에 포함됩니다. 예제 1 입력 temp = 1. 값을 입

k-진 트리(k-ary tree)의 전위 순회(preorder traversal) 결과가 배열 arr[]에 순서대로 주어집니다. 목표는 이 배열로부터 동일한 k-진 트리를 다시 구성하고, 그 트리의 후위 순회(postorder traversal) 결과를 출력하는 것입니다. 여기서 말하는 완전 k-진 트리(full k-ary tree)는 모든 노드가 자식을 하나도 갖지 않거나(0개) 정확히 k개의 자식을 갖는 트리를 의미합니다. 예제 입력 int arr[] = {2, 5, 1, 3, 6, 7, 2, 1}, int size = 8,

정수 값들과 변수 x가 주어졌을 때, 이 값들을 이용해 이진 트리를 구성한 뒤 두 노드 값의 합이 x와 같아지는 쌍(pair)의 개수를 찾는 것이 이 글의 목표입니다. 예시 입력 1 int x = 5일 때, 입력값으로 생성되는 이진 트리는 다음과 같습니다. 출력 Count of pairs in a binary tree whose sum is equal to a given value x are: 2 설명 주어진 정수 배열로 이진 트리를 구성한 후, 합이 5가 되는 노드 쌍이 존재하는지 확인합니다. 이때 만들어지는 쌍은 (2, 3)과

문제 개요 이진 트리의 중위 순회(inorder traversal) 결과가 담긴 배열 arr[]가 주어졌을 때, 이 배열로부터 특수 이진 트리(special binary tree)를 구성하는 것이 목표입니다. 여기서 특수 이진 트리란 루트 노드의 가중치(값)가 왼쪽 자식과 오른쪽 자식의 가중치보다 항상 큰 트리를 의미합니다. 예시 입력 1 int arr[] = {10, 20, 28, 40, 32, 31, 30} 출력 1 주어진 중위 순회로 구성되는 특수 이진 트리는 다음과 같습니다. 40 /

이진 트리가 입력으로 주어졌을 때, 그 트리 내부에서 서브트리(subtree) 형태로 존재하는 이진 탐색 트리(Binary Search Tree, BST)의 개수를 찾는 것이 목표입니다. BST란 왼쪽 자식 노드의 값이 루트보다 작고, 오른쪽 자식 노드의 값이 루트보다 큰 규칙을 만족하는 이진 트리를 말합니다.예제 1입력입력된 값들로 생성되는 트리는 아래와 같습니다.출력Count the Number of Binary Search Trees present in a Binary Tree are: 2설명정수 값 배열을 사용해 이진 트리를

C++에서 배열은 고정된 크기를 가지기 때문에 특정 요소를 삭제하려면 해당 요소를 찾은 후, 뒤에 있는 요소들을 한 칸씩 앞으로 이동시키는 작업이 필요합니다. 이 글에서는 두 번의 순회를 사용하는 기본적인 방법과 단 한 번의 순회로 처리하는 최적화된 방법을 소개하고, 코드 예제를 통해 두 방식의 차이를 살펴보겠습니다. 두 번의 순회(Two Traversals) 먼저 원본 배열과 검색하여 삭제할 요소를 정의합니다. int ele = 5; int arr = [1,2,3,4]; 이제 반복문을 사용해 배열을 처음부터 끝까지 탐색하며 주어

C++에서 주어진 인덱스 범위 [L–R]의 배열 요소 삭제하기배열에서 특정 인덱스 구간에 속한 여러 요소를 한 번에 삭제해야 하는 상황은 코딩 테스트나 실무 개발에서 자주 마주치게 됩니다. C++에는 이를 위한 별도의 내장 함수가 없지만, 두 개의 인덱스 변수를 활용한 반복문 하나만으로 O(n) 시간 안에 해결할 수 있습니다. 핵심 아이디어는 삭제 범위 밖에 있는 요소들만 앞쪽으로 당겨 덮어쓰는 것입니다.1단계: 원본 배열과 삭제 범위 정의먼저 원본 배열과 함께 삭제할 요소들의 배타적(exclusive) 범위 L, R을 정의하고,

C++를 이용해 이진 트리에서 값이 x와 일치하는 리프 노드(자식이 없는 노드)를 찾아 삭제하는 방법을 알아보겠습니다. 핵심 아이디어는 트리를 재귀적으로 순회하면서 조건에 맞는 리프 노드를 제거하고, 잘린 서브트리를 다시 부모 노드에 연결하는 것입니다.1. 트리 노드 구조체 정의먼저 노드의 데이터와 왼쪽·오른쪽 자식 노드를 가리킬 포인터를 포함하는 트리 노드 구조체를 정의합니다. 처음 생성되는 노드는 루트(root) 노드가 되고, 이후에 생성되는 노드들은 모두 자식 노드로 연결됩니다.struct Node { int data;

이진 트리에서 특정 값을 가진 리프(leaf) 노드를 삭제하는 것은 트리 자료구조를 다룰 때 자주 등장하는 기본 연산입니다. 이 글에서는 C++로 재귀 함수를 활용해 값이 k인 모든 리프 노드를 안전하게 제거하는 방법을 단계별로 살펴보겠습니다.1. 트리 노드 구조체 정의가장 먼저 데이터와 왼쪽·오른쪽 자식 노드를 저장하는 트리 노드를 나타내는 구조체를 정의합니다. 처음 생성되는 노드는 루트(root) 노드가 되고, 그 이후에 생성되는 노드들은 자식 노드가 됩니다.struct Node { int data; struct

연결 리스트 구조 정의 먼저 데이터(data)와 다음 노드를 가리키는 포인터(next)로 구성된 연결 리스트의 기본 구조를 정의하겠습니다. struct Node { int data; struct Node* next; }; 노드 생성 함수 만들기 다음으로 createNode(int data) 함수를 작성합니다. 이 함수는 int 타입의 데이터를 매개변수로 받아, 해당 값을 새로 생성한 노드에 할당한 후 그 노드를 반환합니다. 새 노드의 next 포인터는 NULL로 초기화됩니다. Node* createNode(int d

문제 소개 연결 리스트(Linked List)는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 자료구조입니다. 이 글에서는 리스트를 순회하면서 M개의 노드를 지난 직후, 이어지는 N개의 노드를 반복적으로 삭제하는 방법을 C++ 코드와 함께 단계별로 살펴보겠습니다. 1단계: 연결 리스트 구조 정의 먼저 데이터(int data)와 다음 노드를 가리키는 포인터(next)를 멤버로 가지는 노드 구조체를 정의합니다. struct Node {     int data;   &nbs

C++에서 동적으로 할당한 이진 트리를 해제할 때는 delete 키워드와 소멸자(destructor)를 활용하는 것이 가장 간단하고 확실한 방법입니다. 루트 노드에 대해 delete를 한 번만 호출하면, 소멸자가 재귀적으로 실행되면서 모든 자식 노드까지 순차적으로 메모리에서 해제됩니다.이진 트리 노드 클래스 정의먼저 int형 데이터와 왼쪽·오른쪽 자식 노드를 가리키는 포인터를 멤버로 갖는 클래스로 이진 트리를 정의합니다. leftChild와 rightChild는 btree_node 타입의 포인터이며, 여기서는 편의상 모든 멤버를 p

문제 소개이진 문자열(binary string)이 주어졌을 때, 01 또는 10 부분 문자열을 반복해서 삭제하여 문자열 전체에 더 이상 01이나 10이 존재하지 않도록 만들어야 합니다. 이 문제의 핵심은 수행할 수 있는 최대 삭제 횟수를 구하는 것입니다.핵심 아이디어01 또는 10을 한 번 삭제할 때마다 항상 0 하나와 1 하나가 동시에 제거됩니다. 따라서 가능한 최대 삭제 횟수는 문자열 안에서 더 적게 등장한 문자의 개수, 즉 min(0의 개수, 1의 개수)와 같습니다.예를 들어 0이 5개, 1이 6개 있는 문자열이라면 최대 5번

데믈로 수란 무엇인가?데믈로 수(Demlo number)는 11…1처럼 모든 자릿수가 1로 이루어진 수(10자리 미만)를 제곱했을 때 얻어지는 회문수입니다. 예를 들어 1111² = 1234321처럼, 결과가 1부터 차례대로 커졌다가 다시 작아지는 완벽한 대칭 구조를 가집니다.구현 아이디어실제로 큰 수의 곱셈을 수행할 필요 없이, 문자열 조작만으로 결과를 손쉽게 만들 수 있습니다. 알고리즘은 다음 두 단계로 구성됩니다.첫 번째 반복문에서 1부터 n까지 숫자를 차례대로 이어 붙입니다.두 번째 반복문에서 n−1부터 1까지 역순으로 이어

정7각형(heptagon)은 일곱 개의 변과 일곱 개의 꼭짓점을 가진 다각형입니다. 이 글에서는 한 변의 길이가 주어졌을 때, C++를 이용해 정7각형의 대각선 길이를 구하는 방법을 알아보겠습니다.대각선 길이 계산 공식정7각형의 한 변의 길이를 side라고 할 때, 대각선의 길이는 다음 공식으로 구할 수 있습니다.대각선 = 2 × side × sin(900/14)여기서 sin(900/14)의 값은 약 0.9입니다. 따라서 공식을 간단히 표현하면 다음과 같습니다.대각선 = 2 × side × 0.9 = 1.8 × sideC++ 구현

이진 트리에서 노드를 삭제할 때는 일반적으로 삭제하려는 노드의 값을 트리에서 가장 깊고 오른쪽에 있는 노드(마지막 노드)의 값으로 대체한 뒤, 해당 마지막 노드를 제거하는 방식을 사용합니다.트리 노드 구조체 정의먼저 데이터와 왼쪽·오른쪽 자식 노드를 담고 있는 트리 노드를 표현하는 구조체를 정의합니다. 처음 생성되는 노드라면 루트(root) 노드가 되고, 그렇지 않으면 자식 노드가 됩니다.struct Node { int data; struct Node *leftChild, *rightChild; };새 노드 생성 함수

이진 트리(binary tree)의 밀도(density)는 트리의 크기(size)를 높이(height)로 나누어 계산합니다.이진 트리 밀도 = 크기 / 높이여기서 크기는 트리에 포함된 전체 노드의 개수를 의미하고, 높이는 루트 노드에서 가장 깊은 리프 노드까지의 경로 길이를 의미합니다. 일반적으로 크기와 높이를 각각 구하려면 두 번의 순회가 필요하지만, 참조(reference)를 활용하면 한 번의 순회만으로 두 값을 동시에 얻을 수 있습니다.1. 트리 노드 구조체 정의먼저 데이터와 왼쪽·오른쪽 자식 노드를 담고 있는 트리 노드를 나