여러 객체가 주어졌을 때, 객체를 둘러싸는 껍질을 만드는 문제다. 적용되는 가장 직관적인 현상은 고무줄이다. 몇 개의 못을 박아두고 못을 전부 안쪽으로 감싸도록 고무줄을 걸어주면 고무줄이 만든 도형이 볼록껍질이 된다. 1. 문제상황 볼록껍질을 만드는 문제상황을 아래 그림을 예시로 생각해 보자. 평면상에 10개의 좌표가 주어져있고 이 점들을 감싸는 최소 면적의 볼록 다각형을 구성하는 점을 특정하는 것이 이 문제의 해가 된다. 해를 구할 수 있는 방법은 모든 점을 방문하며 확인해보는 방법도 있겠으나, 가장 널리 알려진 것은 O(NlogN)의 시간복잡도를 가진 그라함 스캔(Graham's scan)이다. 2. CCW(Counter Clock Wise) 알고리즘 그라함 스캔 알고리즘을 수행하기 위해서는 두 점으..

경우의 수를 나타낼 수 있는 다양한 방법이 있다. 비트마스크는 원소를 선택하는 경우와 선택하지 않는 경우 둘로 나뉘는 문제에 유용하게 활용할 수 있는 방법이다. 1. 비트마스크 마스크는 두 값을 합쳐 and, or, nor등의 연산을 수행하는 것으로, 이를 비트 연산에 적용한 것이 비트마스트다. 비트는 컴퓨터 연산의 최소 단위이므로 연산 과정에 다른 변환이 불필요하기 때문에 매우 빠른 속도를 갖는다는 장점이 있다. 비트마스크를 적용할 수 있는 문제라면 수행 시간, 메모리 면에서 큰 이점이 있다. 2. 비트 연산자 and, or, xor, nor, nand 연산자는 두 개의 비트를 입력으로 받아 하나의 비트를 출력으로 내놓는다. 두 비트에 대해 각 연산자 별 출력은 다음과 같다. a b and or xor..

트리(Tree) 자료구조는 데이터간 위계가 있어 다양한 처리가 가능하다. 세그먼트 트리는 약간의 메모리를 할애해 구간의 값을 따로 관리하여 빠르게 구간 해를 얻도록 하는 트리이다. 세그먼트 트리는 데이터 전체 구간을 반복적으로 이분해 정복하여 구간에서 원하는 값을 저장해 빠르게 얻도록 한다. 원하는 값이라고 한다면 "구간의 합, 곱", "구간 내 최대, 최소 값" 등이 가능하고 분할 정복으로 구간의 해를 얻을 수 있는 문제라면 세그먼트 트리를 적용할 수 있다. 세그먼트 트리는 데이터 접근에서 정확도가 요구되기 때문에 처음에는 구현하기가 매우 까다롭다.(진짜 개고생했다.) 우선 이 글에서는 새로운 데이터를 추가하지 않는 조건에서 세그먼트 트리를 만들고 원하는 구간 해를 출력하는 쿼리를 구현해본다. 1. 트..

1. 행렬의 곱셈행렬의 곱셈은 단순히 곱셈보다 압도적으로 많은 연산을 필요로 한다. 행렬의 규모가 커질수록 그 정도는 더 심화된다. 행렬의 곱셈은 아래와 같은 규칙을 따른다.2*2 크기의 정사각행렬 두 개를 곱할 때 필요한 연산은 덧셈 4회, 곱셈 8회이다. 3*3 정사각행렬은 덧셈 18회, 곱셈 27회가 필요하다. 연산 횟수로 보았을 때 n*n크기의 정사각행렬의 곱셈은 O(n3)의 시간복잡도를 갖는다. 지수시간이 아닌게 어디겠냐만 이걸 더 줄이는 알고리즘이 여럿 존재한다. 행렬의 곱셈은 공학분야에서 폭넓게 활용되기 때문에 효율적인 연산 방법을 찾는 연구가 꾸준히 진행되고 있다. 최근에는 구글 딥마인드의 알파제로가 새로운 행렬 곱셈 알고리즘을 발견하기도 했다. 아무튼 다양한 방법 중 깡 삼차시간 연산 방..

분할 정복으로 정렬을 완성해가는 알고리즘이다. 알고리즘은 분할, 병합의 두 단계를 재귀 호출하는 것으로 완성되어 꽤 단순하게 구현할 수 있다. 그 유명한 폰 노이만 박사가 만든 알고리즘이다. 1. 병합 정렬(Merge sort)의 개념 원리는 앞서 말한 분할 정복(Divide and Conquer)이다. 문제 전체를 부분으로 쪼개서 하위 문제의 해를 찾아 상위 문제의 해를 얻는 방식으로 정렬에 적용하면 전체 길이의 배열을 절반, 다시 절반, 반복하여 나눌 수 없는 상태의 크기로 만들고 정렬이 끝난 부분들을 합쳐 정렬을 점차적으로 완성해나간다. 이 일을 진행할 때 코드에서 구현해야 하는 것은 두 가지다. 먼저 "분할"하는 것이고 분할된 것을 바르게 "병합"하는 것이다. 언제 분할하며 언제 병합하는지도 중요..

n크기의 배열 arr이 주어지고 k번째 항목까지의 합을 구하는 코드는 아래와 같이 간단히 구현할 수 있다. sum = 0 for i in range(1, k+1): sum += arr[i] print(sum) i번째 항목까지의 합을 구하는 코드는 1부터 k번째까지의 항목을 탐색하며 한 번씩 합 연산을 실시하므로 시간 복잡도가 O(N)이다. 나쁘지 않은데? 그런데 배열 길이가 106, 테스트 케이스가 103개가 된다면 어떨까. 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicp..

해시 함수는 말 그대로 입력을 변환하는 함수다. 목적은 임의의 데이터를 정해진 크기의 데이터로 바꾸는 것이다. 어떤 크기의 값을 넣어도 정해진 크기로 바뀌니 데이터 관리에 유리한 면이 있다. 하지만 정보의 크기를 한정하는 함수이기 때문에 정보 손실은 불가피하고 이것 때문에 이 함수는 단방향 함수다. 해시 함수인 결과(해시 값)만을 가지고 원래 값이 무엇이었는지는 확실히 알 수 없다. 본문에서는 자료구조로서의 해시 함수를 다룬다. 1. 키(Key)와 해시(Hash) 키는 해시 함수에 입력되는 기존 값을, 해시는 그 결과 값을 말한다. 이름(3글자)을 키로 받아 각 글자의 획수로 바꿔보자. 이 방법으로 이름이 거의 대부분 3자리의 숫자로 반환된다. 이 과정에서 이름은 키, 반환된 3자리 숫자는 해시이다. 수..

배낭 문제는 정해진 비용 내에서 최적의 가치를 갖는 해를 찾는 문제다. 처음 이 문제를 접하는 사람들 대부분이 그리디로 접근하지만 그리디 알고리즘만으로는 해결할 수 없는 배낭 문제도 있다. 배낭 문제는 크게 두 유형으로 분류되는데 먼저 그리디 알고리즘을 적용할 수 있는 분할 가능한 배낭 문제와 그리디 알고리즘으로는 해결하기 어려운 0-1 배낭 문제가 있다. 1. 분할 가능한 배낭 문제 분할 가능한 배낭 문제는 말 그대로 가치와 비용을 분할해 가져올 수 있다. 예를 들어 10kg의 제한을 두고 배낭을 싸는데 5kg에 75의 가치를 가진 A와 4kg에 120의 가치를 가진 B, 7kg에 140의 가치를 가진 C가 있다고 해보자. 여기서 A, B, C 모두 원하는 만큼 쪼개서 가져갈 수 있는 물건이라고 가정하..