# 두 단어의 차이 알고리즘(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개의 정점을 가지는 신장 트리의 간선은..
# 피보나치 수열 문제 Fibonacci 수열은 다음과 같이 정의된다.$f_0 = 0, f_1 = 1 그리고 f_i = f_{i - 1} + f_{i - 2}(i > 1 일 때)$ $f_i$를 계산하는 C함수로 순환 함수와 반복 함수를 모두 작성하라. # 구현 // 반복버전에서 반복계수가 2부터 시작해서 n까지 간다는 것만 주의하면 된다. 반복계수가 2인 까닭은 2개의 초기값을 설정해줬기 때문에 0과 1을 지나쳐 2부터 시작되는 것이다. /************************************************* **Fibonacci iterative & recursive ver *************************************************/ #include in..
# 팩토리얼 문제 문제) 팩토리얼 (=계승) 함수 n!은 $n\le1$일 때 n * (n - 1)! 의 값을 가진다. n!을 계산하는 C프로그램을 순환과 반복버전으로 구현하라. # 구현 // 순환함수는 다들 쉽게 작성하시리라 믿고, 반복버전 코드를 배워가시면 좋을 것 같습니다. /************************************************* ** Factorial recursive ver & iterative ver *************************************************/ #include int recur_fac(int n); int iter_fac(int n); void main() { int n; int output1, output2; wh..
# 비둘기집 원칙 문제 문제) 비둘기집 원칙이란 함수 f가 n개의 상이한 입력에 대해 n개보다 작은 상이한 출력이 나온다면 $a\neq$ $b$ 이고 $f(a) = f(b)$인 두 개의 입력 a, b가 존재한다는 것이다. 이와 같이 입력값이 상이하면서 함수값이 같은 a,b를 찾는 C프로그램을 작성하라. # 풀이 이 문제는 한 가지 함수를 미리 정해두고 프로그램을 작성한다. 그 후 함수 내에 같은 y값이 나오는 x값들이 있는지 확인하는 프로그램을 작성하면 된다. /************************************************* ** 비둘기집 원칙 프로그램 *************************************************/ #include #include //..
- Total
- Today
- Yesterday