IT 방랑기

구간합을 반복적으로 빠르게 계산하기 위해서 세그먼트 트리와 펜윅 트리를 이용한다. 세그먼트 트리와 펜윅 트리는 원래의 데이터 값을 저장하는 방법이 아니라, 이름에서 알 수 있듯 데이터를 구간별로 저장하는 형식을 가진다. 간단하게 말하여 부분합을 위하여 i번째까지의 데이터를 모두 합한 값을 유지하고 있다고 보면 된다. 세그먼트 트리는 리프노드에는 원래의 데이터를 그리고 그 부모 노드는 아래의 리프 노드들의 합을 저장하고 있다고 보면된다. 이러한 특징을 바탕으로 특정 구간의 값을 찾는 행위는 O(logN) 그리고 값을 변경 하는 행위 또한 O(lgN)만에 수행할 수 있다. 세그먼트 트리의 경우 필요 메모리량이 복잡하게 계산된다. Full binary tree의 경우 N이 2의 제곱꼴이면 2*N-1개의 노드가..

최소 신장 트리(MST, Minimum Spanning Tree)란? - 가중치가 있는 무향 그래프가 주어졌을 때 모든 노드를 연결하면서 간선의 가중치 합이 최소인 신장 트리를 뜻한다. 최소 신장 트리의 특징 1) 가중치의 합이 최소 2) N개의 노드에 대하여 N-1개의 간선으로 구성 3) 사이클이 존재하지 않아야 함 최소 신장 트리를 구하는 방법 그래프가 주어졌을 때 우리는 어떻게 최소 신장 트리를 찾을 수 있을까? 간단한 방법으로 가중치가 작은 간선을 선택할 수 있는지 확인하여 포함하는 Greedy 방식으로 MST를 구할 수 있다. * 가중치가 작은 순서대로 간선을 탐색하면서 Spanning Tree의 조건에 부합하는 간선만 선택 * 간선을 선택시에 사이클이 있는지 여부를 판단해서 해당 간선을 연결할..

트리 순회는 가장 기본적인 알고리즘인 DFS에 바탕을 두고 있다. DFS는 함수 스택을 이용한 재귀 호출로 구현하며, 스택이라는 특징을 바탕으로 트리를 순회할 수 있다. 트리 순회는 트리의 특성과 DFS를 묻는 가장 기초적인 내용이다. 트리 순회 방법으로는 전위 / 중위 / 후위 순회가 있으며, 이는 각각 부모와 좌, 우의 자식 노드가 있을 때, 어느 노드부터 출력할 것인가에 대한 방식이다. 전위 순회는 [부모 / 좌 / 우] 순서이며, 중위 순회는 [ 좌 / 부모 / 우 ] 그리고 후위 순회는 [ 좌 / 우 / 부모 ] 순서로 출력한다. 즉 부모(루트)의 출력 순서에 따라 나뉘게 된다. 이러한 순서를 출력하는 것은 DFS의 출력 위치에 따라서 간단하게 구현할 수 있다. DFS(X)는 루트 X에 대하여 ..

정렬 알고리즘을 이야기하다보면, 항상 비교되는 두가지가 퀵 소트와 머지 소트이다. 일반적인 상황에서 두 정렬의 복잡도는 O(nlogn)으로 표기한다. 두 정렬을 구태여 비교하는 이유는 분할 정복(divide and conquer) 패러다임을 이용하기 때문이다. 임의의 배열이 있을 때 반으로 쪼개어 가면서 각 원소를 순서대로 배치하는데, 퀵 소트는 분할 이전 그리고 머지 소트는 분할 이후에 이를 순서대로 배치한다. 좀 더 쉽게 그림으로 보자. 왼쪽 머지 소트는 배열을 1/2씩 나눠가면서 정렬이 되었을 때까지 계속해서 나누어간다. 만약 원소가 1개가 된다면 부분 배열은 정렬된 상태이므로 그 다음부터는 합쳐가면서 다시금 배열을 조립한다. 이 합치는 과정은 각 부분 배열의 길이와 같으므로 O(N)이 걸리게 된다..

IEEE754는 부동소수점을 표현하는 표준으로, 일반적으로 사용하는 C, C++, Java와 같은 프로그래밍 언어의 대부분이 이를 사용한다. 부동 소수점외에도 우리에겐 익숙하지 않은 고정 소수점 표현 방식도 있는데, 이는 특정 자릿수에 소수점이 있다고 가정하고 이를 정수로 표현하는 방식이다. 예를 들어 10^3 위치에 소수점이 있다고 생각한다면 12000과 120을 나타내는 고정 소수점은 각각 12.000과 0.120을 뜻하게 된다. 반면 부동소수점은 이 소수점의 위치를 고정하지 않고 지수부와 가수부의 값에 의하여 변동되므로, 더 큰 값이나 세밀한 값을 표현할 수 있게된다. IEEE754에서는 부동 소수점을 3가지로 구성하는데, 최상위 비트부터 부호비트, 지수비트, 가수비트이다. 32비트 단정도와 64비..

정렬과 더블어 따라오는 탐색 중 바이너리 서치에 대하여 설명하고, 이를 구현한 코드를 포스팅한다. 탐색은 요구에 맞는 데이터를 찾는 과정으로, 실무나 프로젝트 또는 알고리즘 문제를 풀어본 사람들은 잘 알겠지만 가장 빈번하게 일어난다. 따라서 이러한 탐색에 필요한 시간 복잡도를 줄이므로써, 더욱 효율적인 프로그램을 작성할 수 있게 한다. 일반적으로 전체 탐색을 통하여 검색을 하는 경우 N개의 데이터에 대하여 O(N)의 시간 복잡도를 가진다. 하지만 정렬된 데이터에 대하여 키에 대한 값을 탐색하는 경우, 이를 O(lgN)으로 줄일 수 있으며, 사실상 lgN은 상수에 근접하므로 O(N) 탐색에 비하여 더욱 효율적이고 같은 시간내 다양한 작업을 할 수 있다. 바이너리 서치는 정렬된 데이터에서 탐색하는 크기를 반..

4. 설치 방법 사실상 설치방법이라고 뭐 있을까? 다운로드 링크는 아래와 같다. 소스포지 다운로드 링크 autoset 다운로드 페이지 한가지 고려해야 할 점은, 다운로드 속도가 너무 느리다는 것이다. 일단 한 10분은 생각해야한다. 자신 운영체제에 적합한 것을 다운로드 받자. 설치과정은 아래의 그림과 같이 하면된다. 언제나 설치는 그랬듯, default값으로 하면서 다음만 계속 누른다. 4. 실행 방법 실행 방법은 진짜 apmsetup과 동일하다. 일단 autoset 매니저라는 프로그램(apmsetup monitor와 동일한 기능)을 실행하면, 아래와 같이 프로그램이 켜진다. 이대로 웹서버와 mysql을 실행하면, 아래와 같이 동작한다. 웹 서버 포트 : 80 웹 서버 파일 : C:\AutoSet9\pu..

1. 들어가면서 집에서 컴퓨터로 웹호스팅을 하거나, 아니면 개발중인 웹 테스트를 위한 서버 구축을 위해서 apmsetup을 사용하는 사람들이 꽤나 많을 것으로 생각된다. apm_setup도 매우 편리한 프로그램이기는 하나, 언제부터인가 업데이트가 종료되었고 심지어 홈페이지도 안나온다. 물론 포털사이트에서 검색하면 설치 프로그램을 받을 수는 있으나, 이마저 구하기 번거로운게 사실이다. 2. 대체제 Autoset 그래서 하고싶은 말이 뭐야? 라고 묻는다면, Autoset이라는 비슷한 프로그램이 존재한다는 것을 알리는 것이다. 만약 apm_setup을 너무 오랜 기간 써와서, 적응이 안될까 걱정된다.는 말은 던져버리자. 심지어 인터페이스마저도 비슷하고, 동일한 phpMyAdmin등을 제공한다. 어느 프로그램이..

시간 복잡도 계산, Master's theorem / 마스터 정리 1. 시간 복잡도 시간 복잡도란? 특정한 프로그램의 실제 동작 시간이 아닌, 입력 데이터의 크기 n에 대하여 기본적 연산의 횟수를 측정하는 것을 의미한다. 시간 복잡도를 표현하는 방법은 총 3가지가 있다. 최선 평균 최악 간단한 정리는 아래의 포스팅을 읽어보자. [알고리즘] 시간 복잡도, 점근적 분석법 그리고 표기법 2. 시간 복잡도 계산 시간 복잡도 함수 `T(n)`은 일반적으로 재귀 형태의 수식으로 주어지는데, `n=1`까지 모든 항을 구해서 그 합을 구하면 그 값이 시간복잡도가 된다. 예를 들어 가장 간단한 시간 복잡도 함수를 보면, `T(n) = T(n-1) + n` 이 `T(n)` 함수는 1회 실행에 n번의 기본 연산을 수행하며,..

1. 시간 복잡도 시간 복잡도 (Time complexity)는 컴퓨터 공학에서 사용되는 알고리즘을 입력의 크기에 관계해서 나타내는 방법이다. 왜 절대 시간을 쓰지 않을까? 절대시간은 사실 컴퓨터 환경 의존성이 심하다. 예를 들어, A 알고리즘은 B 컴퓨터에서 1초동안 100개의 입력을 처리할 수 있지만, C 컴퓨터에서는 10개만 해결할 수 있다면, 이 알고리즘에 대한 절대적 평가가 힘들 수 있다. 따라서 절대 시간이 아닌, 입력의 크기 n에 따라서 알고리즘 동작까지 필요한 시간을 n에 대한 수식으로 나타내는 것이다. 2. Basic Operation 시간 복잡도를 나타낼 때, 측정하는 단위이다. "기본연산"이라고도 하며, 입력의 크기에 비례해서 나타내는 경향을 보인다. 예를 들어 아래의 코드를 실행한다..