토이프로젝트 필요성 팀프로젝트에서 아쉬운 점을 돌이켜본 후, 아무래도 팀플젝은 내가 맡은 부분이 한정되어 있기에 해보고 싶었던 것을 하고 실력을 향상시키기 위해서는 기존 프로젝트 개선과는 별도로 간단한 프로젝트나마 혼자서 해보는 것이 낫겠다고 판단했다. 그러나 sqld 준비, 레주메 만들기, 면접 준비 등 취업 준비를 병행해야 하기 때문에 너무 많은 시간을 뺏겨서는 안된다. 따라서 간단한 to do list에 기능을 추가하는 토이프로젝트로 진행할 예정이다. 프로젝트 목표 - 실생활에서 사용할 수 있는 todo 웹 어플리케이션을 만든다. - Javascript를 공부하고 활용해본다. - 최대한 지난 팀프로젝트에서 사용해보지 못했거나 서툴렀던 기술을 활용하여 실력을 키운다. - 테스트 코드를 작성해본다. -..
선택 정렬: 인덱스 0부터 시작하여 차례대로 뒤의 숫자들과 하나하나 비교해 가장 작은 수가 나오면 교체하여 앞으로 오도록 하는 방법 (추가적인 코딩으로 안정 정렬 가능) 삽입 정렬: 요소를 하나씩 꺼내서 요소 앞에 있는 것들과 비교하며 알맞은 위치에 삽입하는 방법 (이미 정렬된 경우에 유용, O(n)) 셀 정렬: 삽입 정렬을 약간 변형한 정렬. 일정한 너비만큼 떨어진 요소를 가져와서 그 둘을 대소비교한 후 바꾸는 방법 (일정 너비만큼 모두 바꾸면 1round) 간격의 크기를 점점 줄이며 정렬하다 간격 크기가 1이 되면 삽입 정렬. 간격의 크기가 셸 정렬의 평균 시간 복잡도에 영향을 줌 합병 정렬: 요소가 하나만 남을 때가지 리스트를 쪼개고, 다시 합치는 과정에서 대소를 비교하여 정렬하는 방법 퀵 정렬: ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 기수 정렬(radix sort) 기수 정렬(Radix)은 자릿수 등 기준에 따라 숫자를 분류하여 정렬하는 방법이다. 데이터의 각 자릿수를 낮은 자리수에서부터 자리수를 올려 점점 올라가면서 정렬을 수행한다. 예를 들어 아래의 숫자를 기수 정렬 하면 다음과 같은 과정을 거친다. 위의 과정을 십의자리, 백의자리, 천의자리까지 모두 마치면 다음과 같이 기수 정렬이 완료된다. 중복 숫자의 순서를 보장하는 안정 정렬이고, out-of-place 정렬이다. 기수 정렬은 이론적으로는 O(dn)의 시간 복잡도를 갖는 빠른 방법이라고 생각할 수 있다. 위와 같이 4자리 숫자를 일의 자리의 숫자, 십의 자리의 숫자, 백의 자리의 숫자, 천의 자리의 숫자에 따라 분류하여..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 퀵 정렬 (quick sort) 정렬 알고리즘 중 하나인 퀵 정렬은 중심점 - 피벗(Pivot Point)을 임의로 고른 후 이 중심점보다 작은 수를 한 쪽으로 분류하고 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법이다. 매우 빠른 수행 속도를 가지는 정렬 방식이다. 퀵 정렬은 in-place 정렬로 추가로 메모리 공간을 필요로하지 않으며 중복 숫자의 순서를 보장할 수 없는 불안정 정렬이다. 퀵 정렬 과정(순서) 1) 피벗(pivot)을 선택한다. (주로 리스트의 중간에 있는 숫자 혹은 마지막에 있는 숫자 - 중간 값일 확률이 높음) 2) 마지막 요소와 피벗의 위치를 바꿔 피벗을 리스트의 가장 끝으로 보낸다. 3) 2개의 카운터를 사용하여 리스트의 ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 합병 정렬 (Merge sort) 합병 정렬은 요소가 하나만 남을 때가지 리스트를 쪼개고, 다시 합치는 과정에서 대소를 비교하여 정렬하는 방법이다. 비교해야할 요소가 n이 있으면 그 중 반을 비교하면 되기 때문에 합병 정렬의 평균적인 시간 복잡도는 O(n logn)이다. 합병 정렬은 리스트를 쪼개어서 다른 공간에 저장한 뒤에 다시 merge 하므로 out-of-place 정렬이며, 중복된 숫자가 정렬 이전에 놓여있던 순서를 유지한 상태로 정렬되는 안정 정렬이다. 합병 정렬 코드 구현 합병 정렬에서는 배열의 요소를 직접 건드리는 것이 아닌 배열의 index를 다룬다. int[] array, temp;// temp배열: array의 임시 복사본 publ..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 셸 정렬 (Shell sort) 삽입 정렬을 약간 변형한 정렬. 일정한 너비만큼 떨어진 요소를 가져와서 그 둘을 대소비교한 후 바꾸는 방법이다. (일정 너비만큼 모두 바꾸면 1round) 간격의 크기를 점점 줄이며 정렬하다 간격 크기가 1이 되면 삽입 정렬을 한다. 요소의 이동 횟수를 줄이는 데 의의가 있다. 즉, 거의 정렬된 상태로 만들어 삽입 정렬을 하는 경우 시간 복잡도가 크게 줄어드는 것을 활용하는 방식이다. 셸 정렬은 리스트 안에서 순서만 바꾸기 때문에 in-place 정렬이며, 중복된 숫자의 순서가 보장되지 않는 불안정 정렬이다. 셸 정렬의 평균적인 시간 복잡도는 사용하는 간격의 크기에 따라 바뀌는데, O(n^5/4) 혹은 O(n^3/2)..
아래 내용은 부스트코스 강의를 들으며 정리한 것입니다. 삽입 정렬 (Insert sort) 삽입 정렬은 요소를 하나씩 꺼내서 요소 앞에 있는 것들과 비교하며 교체하는 방법이다. 자료구조를 그대로 두고 안에서 순서만 바꾸기 때문에 in-place 정렬이며 중복된 숫자가 정렬 이전에 놓여있던 순서를 유지한 상태로 정렬되는 안정 정렬이다. 선택 정렬의 시간 복잡도는 (n-1) + (n-2) + (n-3) ... 이므로 역시 Worst와 Average 모두 O(n^2)이다. 그러나 이미 순서에 맞게 정렬되어 있는 Best case에서는, 숫자를 꺼내어 앞 숫자와 한 번씩만 비교하면 되기 때문에 O(n)이다. 선택 정렬이 사용되는 경우는 주로 잘 정렬되어 있는 데이터베이스 혹은 딕셔너리에 잘 정렬된 몇 개의 요소..
