소프트웨어학과 k군

1. 레드 - 블랙 트리 개요1.1 기원과 정의레드‑블랙 트리는 Leonidas J. Guibas와 Robert Sedgewick이 1978년에 제안한 self‑balancing 이진 탐색 트리 자료구조입니다.각 노드는 추가로 한 비트(“색상(color)”) 정보를 가지며, 이 색상은 red 또는 black 중 하나입니다.이 색상 비트는 삽입/삭제 시 균형을 유지하기 위한 제약 조건을 정의하는 데 사용됩니다.이론적으로 RBT는 삽입·삭제·탐색 모든 연산에서 최악 O(log n)의 시간 복잡도를 보장합니다.또한 2‑3‑4 트리(B‑트리의 특수형)와 구조적으로 대응 관계가 있어, 2‑3‑4 트리의 각 노드를 하나의 black 노드와 그에 연결된 red 자식 그룹으로 매핑할 수 있습니다.1.2 주요 제약조건(..

문제 설명이 문제에서는 이진 트리의 루트 노드와 정수 m이 주어졌을 때, 트리 내에서 m보다 작은 값을 가진 모든 노드를 출력하는 함수를 작성해야 합니다.문제 요구사항이진 트리의 모든 노드를 순회하여, 각 노드의 값이 m보다 작은 경우 해당 값을 출력합니다.문제 코드 설명1. 구조체 정의1.1 BTNode 구조체typedef struct _btnode { int item; // 노드가 담고 있는 정수 값 struct _btnode *left; // 왼쪽 자식 노드의 주소 struct _btnode *right; // 오른쪽 자식 노드의 주소} BTNode;item: 노드에 저장된 정수 값left: 왼쪽 서브트리(자식 노드)를 가리키는 포인터right: 오른쪽..

문제 설명이번 포스트에서는 재귀 함수를 활용하여 큐(Queue)의 원소들을 반전시키는 방법에 대해 알아보겠습니다. 이전에는 스택을 이용한 방법을 살펴보았지만, 이번에는 재귀 호출을 통해 큐의 순서를 뒤집는 방법을 중점적으로 다루겠습니다.정수형 큐가 주어졌을 때, 큐의 원소들을 반전시키는 함수 reverseQueue()를 구현하는 것이 목표입니다. 예를 들어, 큐에 저장된 원소가 (1, 2, 3, 4, 5)라면, 함수를 호출한 후 결과는 (5, 4, 3, 2, 1)이 되어야 합니다.문제 요구사항 입력: 정수형 큐 q​출력: 큐 q의 원소 순서를 반전시킨 상태​제약 조건:큐가 비어있을 경우, 아무 작업도 수행하지 않고 함수를 종료해야 합니다.​큐의 원소들은 정수형이며, 큐는 연결 리스트로 구현되어 있습니다...

문제 설명이번 포스트에서는 스택을 이용하여 큐의 원소들을 뒤집는 문제를 함께 해결해 보겠습니다.문제에서는 정수들이 저장된 큐(Queue)가 주어지고, 이 큐의 순서를 뒤집어야 합니다.예를 들어, 큐에 저장된 원소가 (1, 2, 3, 4, 5)라면, 함수를 호출한 후 결과는 (5, 4, 3, 2, 1)이 되어야 합니다.문제 해결을 위해 우리는 스택(Stack)을 활용하여, 큐에서 원소를 하나씩 꺼내 스택에 저장한 후, 스택에서 다시 꺼내 큐에 삽입하는 방식을 사용할 것입니다.이때, 큐와 스택은 모두 내부적으로 연결 리스트(LinkedList)를 사용하여 구현됩니다.문제 요구사항예외 처리: 만약 큐가 NULL이거나 비어있다면, 반전을 진행하지 않고 그대로 종료합니다.​반전 방식: 스택을 활용하여 큐의 요소들..

문제 설명이번 포스트에서는 두 개의 연결리스트를 번갈아 가며 병합하는 문제를 함께 해결해보겠습니다. 이 문제에서는 첫 번째 연결리스트(ll1)와 두 번째 연결리스트(ll2)가 주어졌을 때, ll1의 각 노드 뒤에 ll2의 노드를 순서대로 삽입하는 방식으로 병합합니다. 단, 삽입 가능한 위치가 있는 만큼만 두 번째 리스트의 노드를 병합하고, 나머지 노드는 그대로 남겨둡니다. 또한, 첫 번째 리스트보다 두 번째 리스트의 노드가 많을 경우 남은 노드는 그대로 두고, 반대로 첫 번째 리스트의 노드가 더 많다면 두 번째 리스트는 "empty" 상태가 됩니다.문제 요구사항예외 처리 :만약 첫 번째 리스트(ll1)나 두 번째 리스트(ll2)가 NULL이거나 ll1이 빈 리스트라면, 병합을 진행하지 않고 그대로 종료노..

문제 설명이번 포스트에서는 정렬된 연결 리스트(Sorted Linked List)에 새로운 정수 노드를 적절한 위치에 삽입하는 문제를 다룹니다.특히, 삽입 후에도 리스트는 오름차순 정렬 상태를 유지해야 하며, 이미 리스트에 존재하는 값은 중복 삽입되지 않도록 해야 합니다.문제 요구사항정렬 유지: 연결 리스트는 항상 오름차순으로 정렬되어 있어야 합니다.중복 방지: 이미 존재하는 정수는 삽입되지 않아야 합니다.삽입 연산: 새 정수 item을 정렬된 순서를 유지하며 삽입합니다.반환 값:삽입에 성공하면 삽입된 위치의 인덱스(index)를 반환합니다.삽입에 실패하면 (예: 중복된 값이거나 삽입 과정에 문제가 있을 경우) -1을 반환합니다.구현 방식: 이미 구현된 insertNode() 함수를 활용하여 실제 삽입 ..

그래프(Graph)그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료 구조입니다. 이게 무슨 말인지 솔직히 감이 잘 안오실겁니다. 그럼 그림으로 한 번 이해해볼까요?여기서 보시다 싶이 그래프는 2개의 구성요소로 존재합니다. 정점(Vertex/Node):  그래프의 개별 요소를 나타냅니다.e.g. 사람, 도시, 컴퓨터 등이 될 수 있습니다. 간선(Edge/Arc): 두 정점을 연결하는 선을 의미합니다. 이 간선은 정점 간의 관계나 연결성을 나타냅니다. 그래프의 종류방향성과 무방향성무방향 그래프(Undirected Graph):간선에 방향성이 없어, 두 정점 간의 연결이 쌍방향입니다.방향 그래프(Directed Graph)간선에 방향성이 있어, 한 정점에서 다른 정점으로의 일방적인 연결을 나타냅니..

우선 순위 큐(Priority Queue)란 큐는 FIFO(First In First Out) 구조로 먼저 들어온 순서대로 나가는 자료구조입니다. 우선 순위 큐는 들어온 순서에 상관 없이 우선순위가 높은 순서대로 나가는 추상 자료형(ADT)입니다. 흔히 힙(heap)을 우선 순위 큐라고 생각하시는데 우선 순위 큐는 연결 리스트나 배열 등 다양한 방식으로 구현할 수 있습니다. 하지만 힙(heap)으로 구현하는 것이 삽입과 삭제 연산에서 O(log n)의 시간 복잡도를 보장하여 효율적이기 때문에 많이 사용합니다. 힙(heap)사전적 의미로는 "더미, (아무렇게나) 쌓다" 입니다. 스택(stack)이랑 의미가 비슷해 보이지만 스택은 하나하나 차곡차곡 쌓는 거고 힙(heap) 아무렇게나 쌓습니다.  컴퓨터 용어..

스택(Stack)사전적 의미로는 "쌓아 올리다, 포개지다."입니다. 알고리즘에서도 스택 자료구조도 이 사전적 의미를 따라갑니다. 흔히 예시로 책상에 책을 쌓아둘 때 차곡차곡 쌓아가고, 책을 꺼낼 때는 맨 위(Top)에서부터 하나씩 꺼내서 읽는다.(중간에서 빼는 경우 없다고 가정합니다.)하지만 혹시 프링글스를 아시나요? 감자칩 이거 감자칩 먹을 때 생각하면 편한게 가장 마지막(위)에 있는 걸 먼저 먹지 않나요? 그거 생각하면 편하게 생각할 수 있스습니다. 그리고 감자칩이 아니더라도 다른 것들을 넣을 때 가장 처음에 넣은 것이 가장 마지막에 나오게 될 것입니다.(다른 것은 2개 이상)스택은 감자칩 구조이다.라고 생각하면 좀 더 이해가 편해지실 겁니다.  스택의 특징 스택은 그림에서 말했다 싶이 LIFO(La..

복잡도(Complexity)란?복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도복잡도는 크게 시간, 공간 복잡도로 나눌 수 있다. 시간 복잡도(Time Complexity)특정한 크기의 입력에 대해 알고리즘이 얼마나 시간이 얼마나 걸리는지를 의미알고리즘을 위해 필요한 연산의 횟수 시간 복잡도의 3가지 케이스최선의 경우(Best Case)빅 오메가 표기법 사용최선의 시나리오로 최소 시간이 걸림평균적인 경우(Average Case)빅 세타 표기법 사용평균 시간을 나타냄최악의 경우(Worst Case)빅 오 표기법 사용 최악의 시나리오로 최대 시간이 걸림알고리즘에서는 항상 최악의 상황을 고려해야 하기 때문에 최악의 경우로 알고리즘의 성능을 파악합니다.  빅오 표기법빅오 표기법표현O(1) 상수O(l..