1. Introduction c++ 강의를 마친 후, 파릇파릇한 신입생이 메일로 질문을 했다. 내용은 trivial한 내용이었는데, 다음과 같았다. c와 c++ 둘다 printf를 쓸 수 있더라, printf와 std::cout의 차이점이 무엇이냐. std::endl과 \n의 차이점이 무엇이냐. using namespace std를 쓰면 바로 cout, cin 이렇게 쓸 수 있는데, 책에서는 이렇게 쓰면 굉장히 위험하다고 한다. 왜 그런 것인가? 2. Answer 첫번째 질문은 어렵지 않게 답할 수 있다. 다음은 내가 학생에게 한 답변이다. 정확하게는 iostream에 printf와 std::cout이 모두 정의되어 있음. printf는 원칙적으로는 문자열 밖에 출력할 수 없음. 정수, 실수를 표현하려면..

1. Introduction 이중 선택 정렬은 한번의 루틴에서 최소값과 최대값을 같이 찾는 방식으로 정렬하는 선택정렬의 variation이다. 2. Approach 다음 코드는 파이썬에서 이중 선택 정렬을 구현한 것이다. def double_selection(arr, a , b): start = a end = b while start arr[max]: max = i arr[start], arr[min] = arr[min], arr[start] arr[end], arr[max] = arr[max], arr[end] start +..

1. Introduction 선택정렬은 각 루틴마다 최소(최대)값을 찾아 정렬하는 방식의 정렬 알고리즘이다. 버블 정렬과 그 variation들과 같은 $O(n^2)$알고리즘이지만, 저들과는 궤를 달리한다. 2. Approach 다음 이미지는 선택 정렬의 과정을 시각화 한것이다. 출처는 위키피디아. 다음 코드는 파이썬에서 구현한 선택정렬이다. def selection(arr, a, b): for i in range(a, b): min = i for j in range(i+1, b+1): if arr[j] < arr[min]: min = j arr[i], arr[min] = arr[min], arr[i] 3. Discussion 선택정렬은 stable한 정렬에 속하며 in-place한 알고리즘에 속한다. ..

1. Introduction 홀짝 정렬은 홀수부분과 짝수부분을 나눠서 정렬하는 버블 정렬의 variation이다. 칵테일 정렬과 같이 시간복잡도가 $O(n^2)$에 머물러 있지만 오리지널 버블 정렬보다 빠른 것으로 알려져 있다. 2. Approach 다음 이미지는 홀짝 정렬의 과정을 시각적으로 보여준다. 출처는 위키피디아. 다음 코드는 파이썬으로 구현된 홀짝 정렬이다. def odd_even(arr, a, b): isSorted = True while isSorted == True: isSorted = False for i in range (a, b, 2): if arr[i] > arr[i + 1]: arr[i], arr[i + 1]= arr[i + 1], arr[i] isSorted = True for..

1. Introduction 칵테일 정렬 (또는 칵테일-셰이커 정렬)은 버블 정렬의 Variation으로, 한번의 루틴마다 방향을 바꿔서 정렬하는 알고리즘이다. 버블 정렬에서 크게 바뀌지는 않았지만 일반적인 경우에서 버블 정렬보다 빠르다고 한다. 2. Approach 다음 이미지는 칵테일 정렬의 과정을 시각화한 것이다. 출처는 위키피디아. 양 끝을 왔다갔다 하면서 비교하는 인덱스가 배열의 중간으로 수렴하는 것을 볼 수 있다. 다음 코드는 칵테일 정렬의 파이썬 구현이다. def cocktail(arr, a, b): swapped = True while swapped == True: swapped = False for i in range (a, b): if arr[i] > arr[i + 1]: arr[i],..

1. Introduction 버블 정렬은 인접한 두 원소를 비교해가며 정렬하는 정렬 알고리즘이다. 구현이 매우 간단한 것으로 코딩을 처음 배우는 사람들이 주로 쓰는 알고리즘이지만, 성능이 매우 구리다. 같은 $O(n^2)$ 알고리즘 중에서도 독보적으로 느리다! 2. Approach 다음 이미지는 버블 정렬의 과정을 시각화 한 것이다. 출처는 위키피디아. 인접한 두 원소를 비교하는 과정을 정렬이 끝날 때까지 반복한다. 다행이도, 이 과정은 간단한 계산으로 $n(n-1) \over 2$안에 끝나는 것을 알 수 있다. 다음 코드는 파이썬에서 구현한 버블 정렬이다. def bubble(arr, a, b): for i in range(a, b): for j in range(a, b-i): if arr[j] > a..

1. Introduction 희소행렬은 행렬의 값이 대부분 0인 행렬을 의미한다. 원 핫 인코딩 또는 마켓의 장바구니 데이터가 대표적으로 희소행렬로 표현된다. 다음 그림은 희소행렬의 예시인데, 이 경우 자료를 그대로 저장하는 것은 너무나도 비효율적이다. 이 글에서는 희소행렬의 효율적인 저장법에 대해 알아본다. 1) 연결리스트로 구현 가장 쉬운 형태의 구현이다. 필자가 희소행렬을 맨 처음 배웠을 때 생각한 구현 방법이다. N x N 크기의 행렬이 N개의 리스트 포인터를 가진 벡터로 표현된다. 다만 액세스 속도가 똥임으로 사용할 이유가 없다. 2) Coordinate list (COO) 행렬의 모든 값을 (row, col, val)의 형태를 가진 리스트로 표현한다. 원래 형태에 비해서 접근하는 속도가 느리긴..

1. Introduction 원 핫 인코딩은 아래와 같이 데이터 벡터를 벡터의 각 값을 column labeling하고 해당 값을 1로 표시하는 방식의 행렬로 인코딩하는 방법이다. 당연히 해당 값 외의 다른 column에 대해서는 해당하지 않으므로 0으로 채워진다. 웃긴것은 N 크기의 벡터를 N x N의 크기의 행렬로 인코딩한다는 것이다. 혼란스러운가? 필자도 그렇다. 처음 배울때 이게 대체 뭐하는 짓인가 싶었다. 차원의 저주라는 말도 있듯, 사소한 차원 증가가 엄청난 시간적 손해를 가져올 수 있다. 근데 이걸 N배로 늘린다고?? 하지만 이 방식은 겉으로 느껴지는 시간, 공간적인 복잡도를 포기하는 대신의 또 다른 편의성을 가져다 준다. 이는 특히, 거대한 단어 집합을 표현할 때 특히 편한데, 사전 (pr..