개발일지

시간 복잡도　지난 포스팅에서 디스조인트-셋 자료구조를 사용하면 시간 복잡도가 O(Ea(V))로 줄어들며, 정점이 많은 그래프에서 큰 성능 차이가 발생한다고 하였다. 이는 디스조인트-셋 데이터 구조에 특정 휴리스틱을 적용했다는 것을 의미하는데, 여기서 휴리스틱(heuristics)이란 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 신속하게 사용하는 어림짐작의 기술, 즉 항상 최적의 해를 보장하진 않지만 신속하게 답을 구할 수 있는 접근 방식이다. 이 휴리스틱은 Union by rank와 Path compression이다. 　Union by rank는 두 트리를 합칠 때 더 작은 랭크(rank)의 트리를 더 큰 랭크의 트리 아래에 두는 방법이고, Path compression은 find 연산을 수행할 ..

최소 신장 트리 문제그리디 알고리즘 요구 조건　앞 절에서 모든 문제에 그리디 방식을 적용할 수 있는 것은 아니라고 했다. 즉, 최적 부분 구조(optimal substructure)와 그리디 선택(greedy choice)이라는 두 가지 속성을 모두 갖는 문제만 그리디 접근 방식으로 최적의 솔루션을 구할 수 있다.  　최적 부분 구조는 큰 문제의 최적해가 부분 문제의 최적의 해답들로 구성될 수 있는 구조를 의미한다. 그리디 선택 속성은 현재의 선택이 미래의 선택에 영향을 미치지 않고, 각 단계에서 최적의 선택을 하면 전체적으로 최적의 해답을 얻을 수 있는 것을 의미한다. 　이러한 특성에 대해 이해하기 위해 크루스칼 최소 신장 트리 알고리즘에 대해 알아보도록 하자.개요　최소 신장 트리(Minimum Spa..

컴퓨터 구조 개요 왜 공부해야 할까? 컴퓨터 구조는 기본적으로 컴퓨터 시스템의 디자인과 기능을 다룬다. 이는 하드웨어와 소프트웨어가 어떻게 통합되어 작동하는지, 그리고 컴퓨터가 어떻게 정보를 처리하고 저장하는지에 대한 근본적인 이해를 제공한다. 언뜻 생각해 보면 알 수 없는 컴퓨터 부품과 케이블, 복잡한 회로와 같은 이미지가 떠올라 프로그램 개발과는 큰 관련이 없어 보인다. 하지만, 컴퓨터 구조는 실력 있는 개발자가 되려면 반드시 알아야 할 기본적인 지식이다. 그 이유는 다음과 같다. 문제 해결: 컴퓨터 내부를 분석하고 문제를 해결하는 능력을 기르게 해줌 성능, 용량, 비용: 자신이 작성한 코드를 성능, 용량, 비용의 관점에서 분석할 수 있는 능력을 기르게 해 줌. 즉, 컴퓨터 구조를 이해하고 있다면 문..

배낭 문제개요　배낭 문제(knapsack problem)는 조합 최적화의 한 부분으로, 최적화 이론 및 적용을 이해하는데 근본적인 문제다. 즉, 이 문제는 제한된 무게(또는 부피)의 배낭에 가장 가치 있는 물품들을 적절히 담는 방법을 찾는 것이다. 여기서 물건들은 각각 특정한 무게와 가치를 갖는다.본문 　배낭 문제는 주로 0-1 배낭 문제와 분할 가능 배낭 문제 두 가지 유형으로 분류된다. 일반 배낭 문제라고도 불리는 0-1 배낭 문제는 각각의 아이템이 배낭에 포함되거나 포함되지 않는 두 가지 상태만을 갖는다. 따라서, 아이템을 쪼개서 담는 것이 불가능하다. 이 문제는 NP-완전 문제로 분류되어, 이를 다항 시간 내에 결정적으로 풀 수 있는 알고리즘이 알려져 있지 않다.   　반면, 분할 가능 배낭 문제..

그리디 알고리즘개요　그리디(greedy) 알고리즘은 매 시점에서 가장 이상적인 선택을 지향하는 알고리즘이다. 이 방법론은 지역(local)적으로 최적화된 해답들을 도출하면서, 그 해답들로부터 전역(global)적인 최적해를 구축하는 전략을 채택한다. 그리디 알고리즘은 각 선택의 순간마다 최적의 결정을 내리지만, 이 일련의 결정들이 꼭 최적의 결과를 보장하는 것은 아니다. 그러나 특정 문제에 대해서는 이 알고리즘이 실제로 최적의 결과를 보장하기도 하고, 복잡하고 시간 소모적인 문제를 효과적으로 근사해결하는 데에 종종 활용되기 때문에 그 가치는 높다고 할 수 있다. 　이러한 그리디 알고리즘의 단순하고 직관적인 접근법은 그것의 한계를 동시에 내포하고 있다. 즉, 그리디 특성을 지닌 문제에 대해서만 그리디 알고..

맵리듀스개요　지금까지 우리가 다룬 분할 정복은 주로 알고리즘 설계 패러다임으로 간주했다. 이번엔 이 방식을 일반 컴퓨팅 환경을 초월한 고성능 컴퓨터에 적용하는 방법에 대해 논의하려고 한다. 이러한 확장의 핵심에는 컴퓨터 클러스터(Cluster)라는 개념이 있다. 컴퓨팅 클러스터, 즉 복수의 컴퓨터를 네트워크로 연결하여 단일 시스템처럼 작동하게 하는 방식으로, 이를 통해 더 복잡하고 규모가 큰 문제를 효과적으로 해결할 수 있다. 　하지만, 단순히 컴퓨팅 리소스를 확장하는 것만으로 대규모 데이터 처리에 필요한 세밀함과 효율성을 보장하긴 어렵다. 이러한 관점에서 맵리듀스(MapReduce)는 대용량 데이터를 효과적으로 처리할 수 있는 프로그래밍 모델이다. 맵리듀스는 컴퓨팅 클러스터를 활용해 거대한 양의 데이터..

선형 시간 선택개요　선형 시간 선택(Linear time selection)은 데이터 관리의 효율성을 극대화하기 위해 컴퓨터 과학에서 도입된 알고리즘이다. 이 알고리즘은 평균적으로 선형 시간 복잡도 O(n)을 통해, 정렬되지 않은 데이터 집합에서 k번 째로 작거나 큰 요소를 신속하게 식별할 수 있다.대규모 데이터 셋에서 중요한 순위를 차지하는 값을 파악해야 하는 경우, 예를 들어 데이터의 중앙값을 추출하는 등의 상황에서, 선형 시간 선택 알고리즘이 매우 효율적이라 할 수 있다.특징　선형 시간 선택의 두드러진 특징 중 하나는 그 성능이다. 평균적인 시간 복잡도가 O(n)인 선형 시간 선택은 대량의 데이터를 처리하는 데 있어 매우 효율적이다. 또한, 이 알고리즘은 전체 데이터 집합을 미리 정렬할 필요가 없이..

퀵 정렬개요　퀵(quick) 정렬은 주요한 연산의 평균 실행 시간을 최적화하는 것을 목표로 삼는 정렬 방법이다. 병렬 정합이 큰 규모의 데이터 세트에 대한 정렬에 초점을 맞춘 것과는 대조적으로, 퀵 정렬은 분할 정복 전략을 통해 입력 배열을 작은 서브 배열로 분해하고, 각각의 서브 배열을 독립적으로 정렬한 다음, 이들을 다시 결합하여 전체적으로 정렬된 배열을 생성하는 방식을 사용한다. 이러한 접근법에서 퀵 정렬의 핵심 연산은 바로 분할이다.본문　퀵 정렬은 다음과 같은 단계로 수행된다.분할(Divide): 배열에서 특정 원소를 피벗으로 선택하고, 이를 기준으로 입력 배열을 두 개의 부분 배열로 나눈다.정복(Conquer): 피벗을 제외한 두 부분을 재귀적으로 퀵 정렬한다.결합(Combine): 재귀적으로 ..

분할 정복개요　분할 정복(divide-and-conquer)은 복잡하고 해결하기 어려운 문제를 작은 부분 문제로 나눠서 해결하는 방법론이다. 이 접근법의 핵심은 큰 문제를 둘 이상의 하위 문제로 분할하고, 이러한 각각의 하위 문제를 독립적으로 해결한 후, 그 결과를 결합하여 원래 문제의 해법을 도출하는 것이다. 이 기법은 복잡한 문제를 간소화함으로써 알고리즘의 효율성을 증대시키는 데에 중요한 역할을 한다. 　주어진 문제를 분할 정복 방식으로 해결하려면 다음과 같은 세 단계가 필요하다.분할(divide): 주어진 문제를 동일한 방식으로 해결할 수 있는 여러 서브 문제로 나눔정복(conquer): 각 서브 문제에 대한 해답을 구함결합(combine): 각 서브 문제의 해답을 결합하여 전체 문제에 대한 해답을..

알고리즘 및 이진 탐색알고리즘　알고리즘(Algorithm)이란 주어진 문제를 해결하기 위한 일련의 명령들의 순서와 절차를 의미한다. 다시 말해, 문제를 정의하는 데 필요한 입력을 받아, 일련의 변환 과정을 거쳐 결과를 출력한다는 점에서 함수와 유사한 개념이다. 이러한 알고리즘은 문제를 효율적으로 해결하기 위해 설계되며, 이를 위해 다양한 최적화 기법이 사용된다. 　알고리즘의 효율성은 해당 알고리즘의 동작과 수행에 필요한 명령 수에 따라 결정된다. 예를 들어 소수를 판별하는 알고리즘을 짰다고 가정하자.  // 소수 판별 알고리즘1bool isPrime1(int n){ for (int i = 2; i 　두 개의 소수 판별 알고리즘 중 어떤 게 효율적일까? 먼저 첫 번째 함수는 2부터 n까지 모든 수를 ..