# 두 단어의 차이 알고리즘(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) 이며 중복된 값을 허용함에 유의한다. 이진 탐색 트리에서는 중복된 값을 허용하지 않았다. 히프 안에서 데이터들은 느슨한 정렬 상태를 유지한다. 즉, 큰 값이 상위 레벨이고 작은 값이 하위 레벨에 있다는 정도의 ..
- Total
- Today
- Yesterday