공용체(union)를 학습하기 전에 먼저 구조체에 대한 부분이 학습이 되어 있어야 한다. 구조체 포스팅에서 다뤘던 human 구조체를 기본으로 공용체를 설명하려 한다. 먼저 공용체가 등장한 기본 아이디어부터 살펴보도록 하자. human이라는 구조체를 남자와 여자로 구분하려 한다. 남자라면, 수염이 있는지 없는지 여부를 물을 수 있을 것이고 여자라면, 아이가 몇 명 있는지 등의 질문을 할 수 있을 것이다. 구분하는 방법은 다양하다. 주민번호 앞자리가 1인지 2인지에 따라 구분할 수도 있을 것이다. 그러나 항상 비교연산 등을 통해야 여부를 알 수 있으므로 이렇게 비교하는 건 불편하다. 더 쉽게 구분할 수 있는 방법은 없을까? 위의 아이디어로부터 등장한 개념이 바로 공용체(union)다. 공용체의 선언은 구조..
배열(Array)은 같은 타입의 데이터를 한 데 묶어 관리하게 해주는 자료구조라면, 구조체(Struct)는 서로 다른 타입의 데이터를 한 데 묶어 관리할 수 있게 해주는 자료구조다. 구조체(struct)는 다른 프로그래밍 언어에서 레코드(record)라고 불리기도 한다. 구조체의 예를 한 번 살펴보자. struct { char name[10]; int age; float salary; } person; 구조체 문법을 통해 3개의 항목(fields)를 가지는 변수(variable) person을 만들었다. 구조체가 있기 전에는 변수라 하면, int형 혹은 float형 등 단일 변수를 의미했지만 이제는 다양한 자료를 한 데 묶어 하나의 변수로 취급할 수 있게 됐다. 위 구조체 변수 person이 가지는 3개..
# CHAPTER 5 - 구조체, 문자 표시와 GDT / IDT 초기화 #1 부팅 정보 받기 (harib02a) 4일차까지의 bootpack.c 에서는 0xa0000 이라든가 320이나 200이라는 숫자를 직접 프로그램에 쓰고 있었는데, 본래 이 값들은 asmhead.nas 에서 가져와야 한다. 그렇지 않으면, 화면 모드를 바꿨을 때 실행이 잘 안 된다. 그렇다면 포인터를 사용해서 이 값을 가져와 보도록 해보자. 추가로, binfo는 'bootinfo'의 약어고 scm은 'screen'(화면)의 약어다. /************************************************* ** HaribMain (in harib02a / bootpack.c) **********************..
# 두 단어의 차이 알고리즘(Algorism)은 컴퓨터가 사용되기 훨씬 이전부터 사용되던 단어로, 숫자를 이용한 연산을 하는 것을 뜻한다. 이 단어의 정의와 파생된 역사가 궁금하다면 아래의 링크를 통해 자세히 살펴볼 수 있다. https://en.wikipedia.org/wiki/Algorism#References 우리가 흔히 사용하는 단어는 사실 Algorithm 이다. 알고리듬이라 발음해야 정확하지만, IT 분야에서 알고리즘 하면 Algorithm을 말하는 거구나 라고 생각하면 된다. 알고리듬(algorithm)은 알고리즘(algorism)으로부터 파생되었다. 알고리듬(algorithm)은 문제 자체의 의미를 파악하고, 해결에 필요한 중요한 실마리를 찾아 포기하지 않고 조금씩 단계적으로 풀어나가는 것..
# 2차원 배열 (TWO-DIMENSIONAL ARRAYS) 2차원 배열은 사실 일차원 배열이다. 단지, 배열의 요소가 1차원 배열로 이루어져 있을 뿐이다. 2차원 배열을 선언할 때 우리는 주로 int arr[3][5] 와 같이 선언한다. 하지만 우리는 실제로 길이가 3인 배열 x를 생성했을 뿐이고, x의 각 요소들이 길이가 5인 일차원 배열일 뿐이다. 아래 그림을 살펴보자. 이 그림은 2차원 배열의 메모리 구조를 보여주고 있다. 먼저, 회색으로 통째로 칠해진 블럭을 보면 3개의 포인터를 가질 수 있는 크기로 되어 있다. 그리고 그 포인터를 따라가면, 5개의 integer 변수를 포함할 수 있는 녹색블럭이 각 3개가 나온다. C 에서 arr[i][j] 를 찾아가는 과정은 이렇다. 첫째로, x[i] 포인터..
# 최단 경로 최단 경로(shortest path)문제는 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제다. 간선의 가중치는 경우에 따라 비용, 거리, 시간 등으로 해석될 수 있다. 아래의 그래프를 살펴보자. 정점 0에서 정점 3으로 가는 최단 경로는 ( 0, 4, 1, 2, 3 )이고 이 때의 비용(거리)은 3 + 2 + 4 + 2 = 11 이다. 정점 0에서 정점 3으로 가는 다른 경로가 얼마든지 존재하지만, 최소의 거리로 갈 수 있는 방법은 이 방법 뿐이다. 가중치는 가중치 인접 행렬이라고 불리는 2차원 배열에 저장된다. 가중치 인접 행렬은 기존의 인접행렬과 차이점이 있다. 기존의 인접 행렬에서는 간선이 없는 구간에는 행렬의 값을 0으로 했었다. 그러나 가..
# 멱집합 구하는 문제 문제) S가 n개의 원소로 된 집합일 때 S의 멱집합(powerset)은 모든 가능한 S의 부분집합이다. 즉, S = { a, b, c }이면 powerset(S) = { { }, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c } } 이다. powerset(S)를 구하는 순환 함수를 작성하라. # 풀이 비트 연산을 이용하는 문제다. 순환으로 구현해야 하는 만큼 순환별 규칙을 생각할 필요가 있었고, 값을 하나 증가시키는 걸 그 규칙으로 삼았다. 하나의 순환 안에서의 반복문이 비트연산의 핵심인데, 처음엔 이해가 어려워도 하나하나 손으로 써가면서 확인하면 그 규칙이 눈에 들어올 것이다. /********************..
# 히프의 개념 히프(heap)는 "더미"라는 뜻이다. 히프는 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 히프는 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 (작은) 이진 트리를 말한다. 즉 A가 B의 부모 노드라고 하고 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다고 하면, 다음과 같은 조건이 항상 성립하는 트리이다.$Key(A) >= Key(B)$ 히프는 완전 이진 트리(complete binary tree) 이며 중복된 값을 허용함에 유의한다. 이진 탐색 트리에서는 중복된 값을 허용하지 않았다. 히프 안에서 데이터들은 느슨한 정렬 상태를 유지한다. 즉, 큰 값이 상위 레벨이고 작은 값이 하위 레벨에 있다는 정도의 ..
# Kruskal의 MST 알고리즘 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 방법은 알고리즘 설계에 있어 중요한 기법 중 하나다. 결정을 해야 할 때, 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택하는 방법을 말한다. 순간 순간의 최선을 선택해 최종적인 해답에 도달하는 과정인 것이다. 당시에 최적이라고 생각했던 선택들을 모은다고 해서 최종적인 결과가 최적의 해답이라는 보장은 없다. 따라서 탐욕적인 방법은 항상 검증이 필요하다. 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건을 기초로 각 단계에서 사이클을 이..
# Prim의 MST 알고리즘 최소 비용 신장 트리(MST: minimum spanning tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리를 말한다. 최소 비용 신장 트리를 이용하면, 도로 건설이나 전기 회로설계, 통신 인프라 구축 등의 문제를 가장 효율적으로 처리할 수 있게 된다. Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법을 사용한다. 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다. Prim은 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 n - 1개의 간선을 가질 때까지 계속된다. // n개의 정점을 가지는 신장 트리의 간선은..
- Total
- Today
- Yesterday