꾸준히 개발하기

기존 컴퓨터교육과 홈페이지 인수인계도 안되고 관리도 어렵고 아무도 안 쓰는 문제가 심각해서 새로운 홈페이지로 이전을 결심해서 열심히 제작중이다. 2019년 12월부터 제작하는 중인데 2020년 새해까지 이어지고 있다ㅠㅠ

원래는 프론트엔드로 리액트js 쓰고 백엔드로 aws 써서 처음부터 구현할 생각이었는데 너무 시간도 오래 걸리고 학과 홈페이지 느낌보다는 포트폴리오 홈페이지 같은 느낌이 될 것 같아서 학교 내에서 동일한 템플릿을 쓰는 학과를 찾아봤다. 학교 홈페이지 뒤져보니까 copyright SKKU 문구가 적혀있는 홈페이지가 많길래 학교 측에 연락을 했더니 skb 홈빌더라는 툴을 통해 쉽게 웹을 만들 수 있더라! 심지어 서버까지 학교 서버로 돼서 로그인도 학교 아이디로 되고 굉장히 편리헀다.... 

2019년 12월 한달동안 SKB 홈빌더로 컴퓨터교육과 홈페이지 만들고, 공지사항 연동하고(이건 도저히 어떻게 접근하는지 몰라서 정보통신팀에 연락했더니 하루 만에 뚝딱 해주셨다), 연혁 채워 넣고(이건 동기 언니가 CSS 코드를 하나하나 뜯어보며 열심히 수정했다... 멋진 언니 bb), 우리 과의 정보를 이것저것 채워 넣었다. 둘이서 낑낑대며 한 달 정도 붙잡고 있었더니 그래도 꽤 공식 홈페이지 같은 모습이 되어 기쁘다. 

하지만 아직 배포하기에는 아쉬운 점이 군데군데 있다. 현재 해결되지 않은 가장 큰 이슈는 모바일 환경이다. 모바일에서 반응형으로 사이즈가 조정되는 div class를 학교 측에서 안내를 받았는데 이게 정말로... 사이즈가 줄기만 한다 ㅠㅠ 비율도 안맞고 사진이 랜덤으로 잘려버린다. (ex. 인물 사진의 경우 얼굴이 잘려버리는 경우까지 있다)

홈빌더 CSS는 건드리기가 복잡하게 되어있던데 어쨌거나 홈페이지가 모바일에서도 깔끔하게 보여야 하니 이건 추후 CSS를 건드려봐야할 것 같다 ㅠㅠ

* 그리고 교수님 강의자료를 올릴 수 있는 홈페이지를 링크로 걸어두려고 하는데 이 홈페이지야말로 원래 목표대로 프론트엔드 React 백엔드 AWS, nodejs 써서 처음부터 제대로 구현할 듯하다! 열심히 기록해야지. 현재 열심히 노마드 코더님 강의 보면서 React로 이것저것 만들어보고 있다. 빠이팅.

* 그래도 꽤 공식 홈페이지 같이 생겨서 기분은 좋다! 얼른 대문 사진도 바꾸고 스케쥴도 연동하고... 바쁘구만

정렬 알고리즘이란 원소들을 일정한 순서대로 열거하는 알고리즘이다.

자세한 설명에 들어가기 앞서, 해당 내용은 Big-O Complexity에 대한 기본적인 이해가 필요하므로 해당 복잡도에 대한 이미지를 첨부한다. 

알고리즘의 비교

아래에서는 대중적으로 다루는, 시간복잡도가 O(n^2), O(nlogn)인 정렬만 다루려고 한다.

1. 선택 정렬

현재 위치에 들어갈 값을 찾아 정렬하는 방법이다. 현재 위치에 저장될 값의 크기가 작은지/큰지에 따라 최소 선택 정렬(Min-selection sort)와 최대 선택 정렬(Max-selection sort)로 구분할 수 있다.

기본 로직은 아래의 그림과 같다.

1. 정렬되지 않은 인덱스의 맨 앞에서부터 배열 전체 중 가장 작은 값을 찾는다.

2. 가장 작은 값을 찾으면 그 값을 현재 인덱스의 값과 바꿔준다.

3. 다음 인덱스에서 1,2의 과정을 반복해준다.

배열 안의 원소 개수가 N개라고 할때 배열이 어떻게 되어있든지 간에 전체 비교를 진행하므로 시간 복잡도는 O(n^2)이다,

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 현재 위치에서 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 정렬 방법이다. 

기본 로직은 아래의 그림과 같다.

1. 삽입 정렬은 두번째 인덱스부터 시작하며, 현재 인덱스는 별도의 변수에 저장한다. 비교 인덱스는 현재 인덱스 -1로 잡는다.

2. 별도로 저장해둔 삽입을 위한 변수와 비교 인덱스의 배열 값을 비교한다.

3. 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고, 비교 인덱스를 -1하여 비교를 반복한다.

4. 만약 삽입 변수가 더 크면, 비교 인덱스+1에 삽입 변수를 저장한다.

최악의 경우(역으로 정렬된 경우) 시간복잡도는 O(n^2)

배열이 이미 정렬되어 있는 경우 시간복잡도는 O(n)

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

3. 버블 정렬 (Bubble Sort)

매번 연속된 두개의 인덱스를 비교하여 정한 기준의 값을 뒤로 넘겨 정렬하는 방식이다.

기본 로직은 아래의 그림과 같다.

1. 두번째 인덱스부터 삽입정렬을 시작하여 현재 인덱스 값과 바로 이전의 인덱스값을 비교한다.

2. 만약 이전 인덱스가 더 크면 현재 인덱스와 바꿔준다.

3. 현재 인덱스가 더 크면 교환하지 않고 다음 두 연속된 배열값을 비교한다,

4. 이를 (전체 배열의 크기 - 현재까지 순환한 바퀴 수)만큼 반복한다.

배열의 구조가 어떻든 전체 비교를 진행하므로 시간복잡도는 O(n^2)

공간 복잡도는 하나의 배열에서만 진행하므로 O(n)

4. 합병 정렬 (Merge sort)

합병 정렬은 분할 정복(divide and conquer) 방식으로 설계된 방법이다.

* 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해나가는 방식이다.

** 분할은 배열의 크기가 1보다 작거나 같을 때까지 반복한다.

입력으로 하나의 배열을 받고, 이를 두 개의 배열로 계속 쪼개나간 뒤, 합치면서 정렬하여 최종적으로 하나의 정렬된 배열을 출력한다.

기본 로직은 다음과 같다. 

1. 현재 배열을 반으로 쪼갠다. (배열의 시작 위치와 종료 위치를 입력받아 둘을 더한 후 2로 나눈 뒤 그 위치를 기준으로 쪼갠다)

2. 분할한 배열의 크기가 0이나 1일때까지 반복한다.

** 합병은 두 개의 배열을 비교하여, 기준에 맞는 값을 다른 배열에 저장해 나간다.

기본 로직은 다음과 같다.

1. 두 배열 A,B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정한다.

2. i에는 배열 A의 시작 인덱스를 저장하고, j에는 B배열의 시작 주소를 저장한다.

3. A[i], B[j]를 비교한다. 오름차순의 경우 이 중 더 작은 값을 새 배열 C에 저장한다,

  A[i]가 더 큰 경우 A[i]의 값을 배열 C에 저장해주고 i++한다.

4. 이를 i/j가 둘 중 하나라도 각자 배열의 끝에 도달할 떄까지 반복한다.

5. 끝까지 저장을 못한 배열의 값을 순서대로 전부 C에 저장한다.

6. C배열을 원래 배열에 저장해준다.

이 정렬 알고리즘은 분할 과정과 합병 과정이 나뉘어진다.

합병 과정의 시간복잡도는 전체 배열의 길이에 비례하므로 O(n)

분할 과정의 시간복잡도는 O(logN)이다. 

( * 크기가 N인 배열 분할 시, 한번 분할하면 N/2, N/2 2개. 그 다음 분할시 N/4,N/4,N/4,N/4, 4개 이므로 로그함수) 

따라서 합병 정렬의 시간 복잡도는 O(NlogN)

공간복잡도는 두개의 배열을 사용하므로 O(2N)

5. 퀵 정렬 (Quick Sort)

퀵 정렬 역시 분할 정복을 이용하여 정렬을 수행한다.

기준이 되는 값 pivot을 하나 설정하는데, 이를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬한다. 이를 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된다.

기본 로직은 다음과 같다,

1. pivot으로 잡은 배열의 값 하나를 정한다. (보통 맨 앞/ 맨 뒤/ 중간 값/ 랜덤 값 중 하나)

2. 분할을 진행하기에 앞서, 비교를 진행하기 위해 가장 왼쪽 배열의 인덱스를 저장하는 left 변수, 가장 오른쪽 배열의 인덱스를 저장하는 right 변수를 생성한다,

3. right부터 비교를 진행한다. 비교한 배열 값이 pivot보다 크면 right를 하나 감소시키고 비교를 반복한다.

 * pivot보다 작은 값을 찾으면 반복을 중지한다.

4. 그 다음 left부터 비교를 진행한다. 비교한 배열 값이 pivot보다 작으면 leff를 하나 증가시키고 비교를 반복한다. 

* pivot보다 큰 값을 찾으면 반복을 중지한다.

5. left 인덱스 값과 right 인덱스 값을 바꿔준다,

6. 3~5 과정을 left<right일 때까지 반복

7. 위 과정이 끝나면 left값과 pivot 값을 바꿔준다,

8. 맨 왼쪽부터 left-1까지, left+1부터 맨 오른쪽까지 나눠 퀵 정렬을 반복한다.

퀵 정렬은 분할과 동시에 정렬을 진행한다,

퀵 정렬은 배열의 크기만큼 비교를 진행하며, 총 분할 깊이인 logN만큼 진행하므로, 시간복잡도는 O(NlogN)

다만 최악의 경우(배열이 이미 정렬되어 있는경우) 분할이 N만큼 일어나므로, 시간복잡도는 O(n^2)

-> 이를 방지하기 위에 중간값/랜덤값으로 pivot을 정하기도 함

최악의 경우 때문에 합병 정렬보다 느리다고 생각할 수 있지만, 이는 발생하기 쉽지 않은 경우이고 일반적으로 퀵 정렬이 합병 정렬보다 더 빠르다.