감공사

✨ 합병 정렬 또는 병합 정렬(Merge Sort)는 O(n log n) 비교 기반 정렬 알고리즘이다.
일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하여, 분할 정복 알고리즘의 하나이다.

Merge Sort는 Merge Sort(분할), Merge(병합) 2가지 function으로 나눠서 작성할 수 있다.
Merge를 구현하는 function을 먼저 작성해보겠다.

[ -30, 22] [ 0, 97 ]

위 left, right 배열에 들어있는 숫자를 오름차순으로 정렬해보자

🎈 Merge function을 실행하면 위와 같은 과정으로 정렬이 진행된다.

각 배열의 가장 첫 번째 값들을 비교하고, 작은 값을 먼저 넣어준다.
이렇게 Merge function은 간단하다. 양쪽 배열을 비교하고 작은 값을 먼저 넣어주면 된다.

아래 Pseudo Code와 이미지를 참고하여 코드를 작성해보자.

🧨 left, right 2개의 argument를 받고
둘 중 하나의 배열값이 모두 shift()될 때까지 while loop을 반복한다.
가장 첫 번째 index를 비교하고 작은 값을 results 배열에 넣어준다.
둘 중 하나의 배열은 1개의 값이 존재할 것이므로, return 부분에는 result, left, right를 모두 spread해준다.

이렇게 Merge Function을 먼저 작성해줄 수 있다.

다음은 Merge의 전 단계인 MergeSort Function을 작성해보자(각 배열 분할 기능)

[ 97, 0, 22, -30 ]

위의 배열을 length가 1을 가질 때까지 분할해보자.
이 기능은 끝이 정해져 있는 반복이므로, 재귀를 통해 해결할 수 있다.

🎈 Merge Sort function을 실행하면 위와 같은 과정으로 정렬이 진행된다.
처음에는 전체 배열의 반으로, 왼쪽에서 또 반으로, 오른쪽에서 또 반으로 반복하여 나눠진다.

아래 이미지를 보며 코드를 어떻게 작성할지 생각해보자.
참고로, Merge Sort는 Merge와 함께 사용할 수 있다.

🧨 먼저, Base Case로 arr.length가 1이 되면 그 값을 반환하도록 한다. 우리의 목표는 1개가 남기까지 분할하는 것이기 때문이다.
배열을 반으로 나누는 기능은, Array의 slice helper method를 이용하면 간편하다.
배열의 중앙 기준을 잡기 위해 center를 구해주고,
그 기준으로 slice(0, center), slice(center)를 진행해주면 left와 right를 구할 수 있다.
( Math.floor(), slice() 사용법은 JavaScript - helper Method 카테고리에서 확인 가능)

그리고 마지막으로, 이 나눠진 element를 merge function을 이용해서 병합해주면 된다.

Merge Sort와 Merge Function이 진행되는 전체 이미지

💪

Click! 👉 https://github.com/DasolPark/Dasol_JS_WorkoutTimer

JavaScript와 반응형 CSS를 사용하여 데스크톱 또는 모바일에서 사용할 수 있는 운동 도우미 타이머 어플리케이션입니다.

📌운동 종목과 종목의 세트를 상세히 작성할 수 있으며, ⏳각 세트별로 완료한 시간을 체크해줍니다.
💡운동 종목과 세트는 추가 또는 삭제가 가능하며, 운동을 완료하면 완료된 시간을 수정할 수 없습니다.

Date Object를 이용하여 현재 시간을 표시하도록 만들었으며, 브라우저 Local Storage에 닉네임을 저장할 수 있도록 했습니다.
스탑워치는 setTimeout()을 이용하여 시간이 계속 증가될 수 있도록 하였습니다.
또한, DOM을 이용하여 종목이나 세트 element가 추가되거나 삭제될 수 있도록 제작하였습니다.

Code

😢 배열에 건물 크기만큼 방 번호를 저장하고 인덱스는 찾아내는 반복문도 가능했지만, 패턴과 집단을 찾는게 핵심

😊 Solution 1)

일단, 입력 받은 W는 이용하지 않아도 되는 방법으로 풀었다.
N(번째 방문자)을 H(층 높이)로 계속 빼주고, N이 H보다 작거나 같을 때 반복을 끝내보자.
그러면 N번째 방문자의 호수와 층수를 동시에 구할 수 있다.

예를 들어 N=10, H=6이라고 할 때, N = N - H;를 반복해주면  한 번만 빼줘도 10 - 6 = 4가 된다.
첫 호수 집단의 6층은 꽉 찼고, 다음 호수 집단의 4층이라는 것을 알 수 있다. (6+4=10)
동시에 roomCnt++를 진행해주면 엘리베이터에서 얼마나 떨어져 있는 호수 집단인지 알 수 있다.
위의 뺄셈은 1번 진행되며, 호수 집단은 1부터 시작한다고 선언했을 때, roomCnt++;도 역시 1번 진행되므로
2값을 얻을 수 있고, 2는 엘리베이터 기준 2번째 호수 집단이라는 것을 알 수 있다.

결과적으로 6층 각 층 객실12개 기준 10번째 손님은 402호라는 정답을 도출해낼 수 있다.

Solution 2)

N/H를 해주면 몇 번째 호수 집단인지 알아낼 수 있으며,
N%H를 해주면 몇 층인지 알아낼 수 있다.

예를 들어, N=72, H=30이라고 할 때,

N/H=2.4
1번째, 2번째도 아니고 2번째를 넘어가는 집단이라는 뜻인데 즉, 그말은 3번째 호수 집단이라는 것이다.
즉, 정수가 나오지 않는 다면 Math.ceil()을 이용해 올림을 해주면 된다.

N%H=12
즉, 30층을 2번 지난 후 12번째 층이라는 뜻이다.

층이 증가되는 패턴 그리고 호수가 증가되는 패턴을 파악하면 이렇게 N과 H만으로도 문제를 해결할 수 있다.

Solution 3)

방 배정 우선순위로 배열에 방 번호를 저장하면 된다.
중첩 for loop을 사용하며, 외부 for loop에서는 호수를 내부 for loop에서는 층수를 뽑아내면 된다.
배열에 모든 경우의 수를 저장한 후 N(or N-1)번째 배열을 출력해주면 된다.

추가적으로, 정확한 정답을 위해서 호수가 10이하면 호수 앞에 '0'을 꼭 붙여줘야 한다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

✨ 선택 정렬(Selection Sort)은 정렬되지 않은 데이터들에 대해
가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.

[ 10, 0, 97, -30, 5 ]

위 배열에 들어있는 숫자를 오름차순으로 정렬해보자.

🎈선택 정렬 코드를 실행하면 위와 같은 과정으로 정렬이 진행된다.

가장 작은 값의 기준은 항상 맨 앞 index이다. 하지만, 정렬이 완료되는 순서도 가장 앞부터 완료된다.
이걸 고려했을 때, 가장 작은 값의 기준은 0, 1, 2, 3, ... 씩 증가한다고 생각하면 된다.

그렇게 나머지 오른쪽 값들과 반복 비교하여 가장 작은 값의 인덱스를 저장하고,
그 값이 첫 번째 기준값과 같은 것이 아니라면 서로 값을 교환해준다.

🧨 위의 코드처럼 중첩 for loop을 이용하고, indexOfMin을 외부 for loop이 진행될 때마다 새로 설정해준다.
그리고 내부 for loop에서 반복 비교해주고, 가장 작은 값의 index를 얻어낸다.
최종적으로 처음에 초기화한 i인덱스와 같지 않은 지 확인하고, 같지 않다면 서로 값을 교환해준다.

if( indexOfMin !== i ) 조건문이 들어간 이유는, indexOfMin보다 작은 값을 찾지 못 했을 때
indexOfMin은 여전히 i값을 가지고 있을 것이기 때문에 그런 상황을 대비해주는 것이다.

버블 정렬과 비교했을 때, 여전히 시간 복잡도는 O(n^2)지만 이렇게 다른 방법으로 접근할 수도 있다.

Code

😢 이해하고 식을 만들어 내는 것이 조금 힘들었다. 미끄러지는 부분을 정확히 이해해야 한다.

😊 높이 V를 A-B로 나눠주는 방법이 가장 효율적이다.
하지만, 정상에 도착하면 미끄러지지 않기 때문에 B가 결국 한 번 더 계산식에 들어가는 셈이다.
따라서, 높이에V에 B를 빼주면 위 문제를 해결할 수 있다.
딱 떨어지지 않는 수가 나올 때는, 하루가 더 필요하다는 뜻이기 때문에 Math.ceil로 올림을 해주면 같은 효과를 볼 수 있다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

✨ 버블 정렬(bubble sort)은 서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내며 정렬하는 방식이다.

[ 97, 5, 10, 0, -30 ]

위의 배열에 들어있는 숫자를 오름차순으로 정렬해보자.

🎈버블 정렬 코드를 실행하면 위와 같은 과정으로 진행 된다.

이해하기 쉽게 하기 위해서, 예시 배열 숫자에는 가장 큰 수를 맨 앞에 그리고 가장 작은 수를 맨 뒤에 넣어보았다.

첫번째 사이클에서,
이웃한 데이터를 비교해가며 index를 하나씩 증가해 나가기 때문에 가장 큰 수(97)는 맨 뒤에 자리할 수밖에 없다.
첫 번째 index부터 '앞자리 > 뒷자리'기준으로 비교하기 때문이다. 97보다 큰 수가 없다면 앞의 비교문은 언제나 참이다.

하지만, 가장 작은 수는 맨 뒤에 있기 때문에 한 칸밖에 이동하지 못 한 것을 볼 수 있다.
이 내용을 볼 때, 가장 작은 수가 맨 앞에 위치하기 위해서는 배열의 크기만큼 반복문이 반복되어야 한다는 것을 알 수 있다.
또한, 이제 마지막 index는 비교 대상이 아니라는 것을 알 수 있다. 끝 index는 이미 정렬이 끝났다. 
따라서, 다음 비교 사이클에서는 index를 하나 줄여 비교를 진행해야 한다.

위의 과정이 반복되는 것이 버블 정렬이다. 이 내용을 토대로 코드를 작성해보겠다.

🧨위에 보이는 것처럼 for loop 중첩으로 버블 정렬을 해결할 수 있다.

앞서 말한 것처럼 외부 for loop에서는 배열의 길이만큼 반복해준다.
내부 for loop에서는 외부 for loop이 한 사이클 돌 때마다, 마지막 index는 정렬이 끝나므로
배열의 길이 - i 만큼을 범위로 지정해준다.
그리고 내부 for loop에서 if 조건문을 이용해 뒤에 숫자보다 앞의 숫자가 크면 교체(swap)해주면 된다.

지금까지 버블 정렬을 이용해서 숫자를 정렬하는 방법을 작성해봤다.
하지만, 버블 정렬은 O(n^2)만큼의 시간 복잡도(Runtime complexity)를 갖기 때문에 시간적으로 굉장히 안 좋은 방법이다. 
하지만, 코드를 구현하기에는 가장 쉬운 정렬 방법이다.

다음 글에서는 같은 시간 복잡도지만, 다른 정렬 방법인 선택 정렬(Selection Sort)를 작성해보겠다.

✨ 평소 DOM을 이용해 Event를 작성하곤 한다. 그 이벤트는 어떻게 관리될까? class를 이용해서 event library를 만들어보자.

1. Button을 click하면 'Hi there!'이라고 consol에서 출력되도록 작성해보자.
2. 브라우저(html file)를 열자마자 자동으로 button을 click하는 trigger를 발생시켜보자
3. button의 click event를 제거해보자

아래 HTML파일 script tag 부분에 작성하면 된다.

편의상 jQuery로 작성해보겠다.

.on으로 click event를 등록하고, .trigger로 click event를 자동 실행하고, .off로 click event를 제거하였다.

이 event들은 어떻게 관리될까? class를 이용해서 event를 관리하는 library를 작성해보자

class를 이용해 event library를 작성하면 위와 같이 작성할 수 있다.

생성자(constructor)를 이용해 object(map)을 선언해주고, on(), trigger(), off() method를 실행하며
각 event(key)마다 callback(value)을 넣어주면 된다.
또한, callback은 여러 개가 들어갈 수 있으므로 배열로 선언해주면 된다.

on()은 이벤트 등록을 위한 기능이므로, 해당 event가 있다면 push, 없다면 새로 key를 등록해준다.

trigger()는 이벤트를 실행시켜주므로, for...of를 이용해 obj안에 등록되어 있는 해당 event를 ()를 통해 실행시켜준다.

off()는 이벤트를 제거해주므로, delete를 이용해 obj안에 등록되어 있는 해당 event를 제거해주면 된다.

우리는 평소 사용 방법만 알면 event를 쉽게 등록하고 사용하거나 제거할 수 있다.
하지만, 우리 눈에 보이지 않는 event는 어떻게 관리되는 지 위의 내용을 통해 조금이나마 이해할 수 있다.

추가) Vanilla JavaScript로 작성했을 때,

Code

😢 어떻게 빠르게 해당 집단을 찾아낼 것인지, 해당 집안에서 정답을 어떻게 도출할 것인지가 핵심

😊 2번째 제출코드를 먼저 보면 이해하기 편하다.

다음 표는 지그재그 순서로 진행하는 분수를 더 보기 편하게 정리한 것이다.

분모는 짝수일 때, 오름차순으로(1 2 3 4 5...) 숫자가 진행되는 것을 알 수 있고,
분자는 짝수일 때, 내림차순으로(5 4 3 2 ...) 숫자가 진행되는 것을 알 수 있다. 홀수는 그 반대다.

패턴을 파악했으니, 어떻게 답을 찾아낼 지 생각해보자.

먼저, 최대로 입력받을 수 있는 수의 크기는 10,000,000이므로 배열이나 테이블로 만드는 건 시간 초과가 날 것이다.
따라서, 찾고자하는 X번을 포함하고 있는 그룹을 찾고, 그 그룹 안에서 X번째 분모/분자 값을 찾아내야 한다.

1/1부터 시작한다고 생각할 때, 해당 그룹의 분수 개수는 1부터 1씩 증가한다.
그룹 개수가 증가할 때마다 입력 받은 X에서 그룹을 빼주면 해당 그룹에 도달했을 때, X는 0 또는 음수가 된다.
위 과정을 while문에서 진행해주면 된다.

여기서 중요한 것은 groupCounter가 곧 해당 그룹의 분수 개수라는 것이다. 이 것을 기억하고 다음 단계로 넘어가보자.

이제 if (group % 2 === 0)을 이용해서 짝수일때, 분모 출력을 groupCounter + X 로 해주면
해당 그룹의 끝 기준으로 자신의 순번을 찾는다.(12345 처럼 오름차순 기준이기 때문)
그리고 분자는 1 + (-X) 를 해주면 역시 그룹의 끝 기준으로 자신의 순번을 찾는다.( 54321처럼 내림차순이기 때문)

예를 들어 11번째 분수를 찾아보자.

while(X > 0){} 코드를 통해 groupCounter는 5, X는 -4라는 것을 알아낼 수 있다.
그룹은 5번째이므로 홀수이기 때문에, 분모는 내림차순, 분자는 오름차순이다.
분모 그룹은 54321
분자 그룹은 12345
이며 분모는 1+ -(-4) = 5이므로, 5번째 그룹의 1번째 수이며,
분자는 5 + (-4) = 1이므로, 역시 5번째 그룹의 1번째 수다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

Q. 주어진 Node가 이진 탐색 트리(Binary Search Tree)로서 유효한지 확인하는 function을 작성하라.
(left node는 node.data보다 작으며, right node는 node.data보다 크다는 것을 명심)

🎈 현재 node의 왼쪽 node는 현재 node보다 작으며, 오른쪽 node는 현재 node보다 큰 것이 BST다.

해당 node를 기준으로 작은가? 큰가?를 파악해주면 된다.
그러기 위해서는 기준을 잡아줄 max 또는 min을 설정해주면 비교하기가 더욱 쉬워 진다.

🧨 function의 argument로 min, max를 넣어주면 편할 것이고,
max보다 크거나, min보다 작으면 false를 반환해줄 조건문이 있어야할 것이다.
또한, 트리를 탐색하며 검색하므로 재귀를 써주면 효율적일 것이다.
라는 생각을 하면서 문제 풀이를 시작해주면 된다.

🔮 argument로 min과 max에 default null을 설정해주고 시작하자.

우선, 17-23번째 코드가 가장 먼저 떠올리기 쉽다.
root부터 탐색을 시작할 때, 왼쪽 노드가 있고 && 왼쪽 노드 값이 지금 노드의 값보다 크지 않으면 true다.
만약 커서 false를 return받으면, false를 계속 반환하여 처음 재귀를 호출한 조건문에 가서 끝낸다.
더 이상 탐색할 이유가 없기 때문이다.
만약 false 조건에 걸리지 않으면 이렇게 BST를 끝까지 내려가며 validate이 재귀로 작동한다.
이와 마찬가지로 오른쪽 노드도 생각해주면 된다.

재귀로 실행되며 max와 min을 확인하는 조건문을 살펴보자(9-15번째 코드)
왼쪽 노드는 무조건 상위 노드보다 크면 안되며, 오른쪽 노드는 무조건 상위 노드보다 작으면 안된다고 반복해왔다.
따라서, 왼쪽 노드를 검사할 때는 상위 노드를 max로 잡고, max보다 크면 false를 return해주면 된다.
또한, 오른쪽은 상위 기준으로 min보다 작으면 false를 return해준다.

예외 사항이 있다. 위 그림을 통해 예외 사항을 살펴보자.
왼쪽에 노드가 있으며 상위 노드보다 작거나, 오른쪽에 노드가 있으며 상위 노드보다 크지만
애초에 들어와서는 안 될 값을 체크해줘야 한다. '15'를 보자.
이 경우, -1노드의 오른쪽에 있으며 -1보다 큰 값을 갖고 있다. BST의 정의에 따르면 위치가 맞긴 하다.

하지만, 애초에 '10'노드를 기준으로 오른쪽에 삽입되었어야 할 노드다.
이런 경우는 17-23번째 코드에서 작성한 validate 재귀로 해결된다.

왼쪽 노드를 검사할 때, max는 상위 노드 기준으로 입력되지만,
오른쪽 노드를 검사할 때는 max는 '-1'기준 상위 노드 값(0)이 유지되며,
min값은 '15'로 노드가 위치하면서 그 상위 노드 값인 '-1'이 들어가기 때문이다.
따라서 '15'는 max(0)보다는 크지만, min(-1)보다는 작기 때문에 false를 return한다.
이렇게 유효성 검사를 마무리해 줄 수 있다.

이렇게 반복해서 false를 확인해주고, false가 하나도 발생하지 않는다면 올바른 BST이므로 true를 반환해주면 된다.

📌 if(max && node.data >) 이런식으로 'max가 있을 때'로 전제하여 코드를 작성해주면 안 된다.
만약 -1값이 들어오면 -1은 false이기 때문에 해당 조건문을 실행하지 않기 때문이다.
또한, ture or false값을 최종적으로 받아야하기 때문에 return이 필요한 곳에 return은 잘 넣어주는 게 중요하다.

👏 이해하기 상당히 어려운 알고리즘이다. 계속 디버깅을 하면서 값의 이동과 재귀의 흐름을 파악해주는게 이해의 지름길이다!

Code

😢 보자마자 위에서 표시해 놓은 부분들이 눈에 띄었다.
각 범위를 한 바퀴 돌고 다음 범위로 넘어가는 부분인데, 각 수를 계산해보니 6, 12, 18, 24로 등차수열을 이루고 있었다.
그래서 등차수열을 이용해서 푸는 문제인가? 하고 계산식을 넣으려고 하다가 시간을 좀 낭비했다.

😊 패턴을 찾았다면 프로그래밍적으로 단순하게 작성해 나가면 된다.
최소 거리는 1부터 시작할 것이고, 범위도 1부터 시작한다. 
증가하는 범위는 1,(2~)7, (8~)19, (20~)37...이므로 '기존 범위+(count된)최소 거리*6' 이다.
while loop을 이용해 범위가 입력 받은 N보다 작을 때까지 반복해주면 된다.

Full Code (https://github.com/DasolPark/Algorithm_JavaScript/tree/master/Baekjoon)