소프트웨어학과 k군

[자료구조] 이진트리(Binary Tree) 작은 수 출력(printSmaller Values) 구현(C언어)

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

[자료구조] 이진트리(Binary Tree) 홀수 합(sumOfOddNodes) 구현(C언어)

문제 설명이번 포스트에서는 이진 트리(Binary Tree)에 저장된 정수들 중 홀수 값만을 골라 합산하는 문제를 해결해보겠습니다.문제에서는 정수 값을 저장하는 이진 트리의 루트 노드를 입력받아, 트리 내에 존재하는 모든 홀수 노드의 값을 더한 합계를 반환하는 재귀 함수를 구현합니다.문제 요구사항예외 처리:만약 입력된 이진 트리의 루트 노드(root)가 NULL이면, 함수는 예외 처리 후 0을 반환합니다.노드 합산 방식:재귀 함수 호출을 통해 이진 트리의 모든 노드를 탐색합니다.현재 노드의 값이 홀수이면 그 값을 결과 변수 sum에 더합니다.현재 노드의 왼쪽 서브트리와 오른쪽 서브트리를 재귀적으로 탐색하여, 반환된 합계를 현재 노드의 값과 함께 누적합니다.문제 코드 설명1. 구조체 정의1.1 BTNode..

[C 언어] 동적 메모리 할당(malloc, calloc, realloc)를 모르는 당신! 정~~~말 불쌍해!

C 언어에서 동적 메모리 할당은 프로그램 실행 중에 필요한 만큼의 메모리를 할당받아 사용하는 중요한 기능입니다. 동적 메모리 할당을 통해 배열과 같은 데이터 구조의 크기를 실행 시간에 결정할 수 있으며, 메모리의 효율적인 사용이 가능해집니다. 이때 할당되는 메모리는 Heap 영역에 위치하며, 대표적으로 사용하는 함수는 malloc, calloc, realloc입니다.1. 메모리 구조와 Heap 영역C 프로그램은 일반적으로 다음과 같은 메모리 영역으로 구성됨코드 영역(Code Segment): 실행할 명령어들이 저장됨데이터 영역(Data Segment): 전역 변수 및 static 변수 등이 저장됨BSS 영역: 초기화되지 않은 전역 변수 및 static 변수들이 저장됨Stack 영역: 함수 호출 시 생성되..

[CSAPP] 3-8 배열의 할당과 접근

컴퓨터 시스템에서 배열은 단순히 여러 데이터를 나열하는 자료구조를 넘어, 메모리 할당과 주소 계산의 기본 원리를 보여줍니다. 이번 포스팅에서는 C 언어에서 배열이 메모리에 어떻게 배치되고 접근되는지, 포인터 산술과 어셈블리 수준의 주소 계산까지 상세히 분석합니다.1. 배열의 기본 원리1.1. 연속적 메모리 할당 C 언어에서 배열 선언은 연속된 메모리 블록을 할당받습니다.T A[N];선언 시, 배열의 시작 주소를 xA라 하고 요소의 크기를 L이라 하면, 각 요소는 다음 주소에 저장됩니다.A[0]: xAA[1]: xA + LA[2]: xA + 2L…A[i]: xA + L * i이와 같이, *A[i] ≡ (A + i)라는 표현은 “기준 주소 + i×요소 크기”를 역참조하여 값을 얻는 방식임을 보여줍니다.1.2..

[자료구조] 스택과 큐(Stack and Queue) 재귀(Recursion)를 이용한 큐 뒤집기(Queue Reverse) 구현(C 언어)

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

[자료구조] 스택과 큐(Stack and Queue) 스택을 이용한 큐 뒤집기(Queue Reverse) 구현(C언어)

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

C언어의 포인터는 C언어의 핵심입니다. 포인터를 제대로 이해하면 메모리 관리, 함수 인자 전달 등 다양한 고급 기법을 활용할 수 있습니다. 이번 포스팅에서는 포인터의 기본 개념, 선언 및 사용법, 배열과의 관계, 포인터 연산, 그리고 함수와 포인터에 대해 설명합니다. 1. 포인터포인터의 기본 개념포인터는 메모리 상의 "주소"를 저장하는 변수e.g. 친구에게 집 주소를 알려주어 직접 방문하도록 하는 것처럼, 포인터는 변수(데이터)가 저장된 메모리 주소를 가리킵니다. 포인터를 통해 직접 메모리에 접근할 수 있으므로, 변수의 값을 간접적으로 읽거나 수정할 수 있습니다.예시 코드int num = 10; // 정수형 변수 num 선언 및 초기화int *p = # // p는 num의 주..

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

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

컴퓨터 프로그램은 여러 작업을 하나의 함수(프로시저)로 묶어 필요할 때마다 호출합니다.하지만 단순히 함수를 호출하는 것만이 아니라, 함수가 호출될 때마다 스택 프레임(활성화 레코드)이 생성되어 함수의 인자, 반환 주소, 지역 변수 등이 저장되고, 함수 실행이 끝나면 원래의 상태로 복귀하게 됩니다.이 글에서는 C와 어셈블리어 예시를 통해 프로시저 호출의 내부 동작, 스택 프레임 구성, 그리고 함수 호출과 반환 과정에 대해 자세히 알아보겠습니다. 또한, 프로시저라는 개념이 추상화(abstraction)의 한 형태임을 이해하기 위해, 추상화의 개념과 수학적 함수로서의 관점을 함께 살펴보겠습니다.1. 추상화와 프로시저추상화 추상화는 복잡한 시스템을 간단하게 만들어, 사용자가 필요한 핵심 기능만을 이용할 수 있도..