개발일지

그래프 컬러링개요　그래프 컬러링(graph coloring) 문제는 주어진 그래프에서 서로 인접한 정점끼리 같은 색을 갖지 않도록 모든 정점에 색상을 지정하는 것이다. 이때 에지의 가중치는 사용하지 않는다. 컬러링의 주요 종류는 다음과 같다. 정점 컬러링: 가장 기본적인 형태의 그래프 컬러링. 인접한 정점들은 다른 색깔을 가져야 한다는 규칙을 따름.에지 컬러링: 각 에지를 색칠하는 데 중점을 두며, 어떤 두 에지도 같은 색깔을 가질 수 없음. 이 규칙은 에지가 공유하는 정점에도 적용됨.착색수(chromatic number): 그래프를 적절히 색칠하는 데 필요한 최소 색깔 수 (NP-완전 문제) 　그래프 컬러링은 택시 예약 스케줄 작성, 스도쿠 퍼즐 풀기, 시험 시간표 작성 등을 그래프로 모델링한 후 컬러..

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

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

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