감공사

Code

😢 0!은 1을 잊고 있었다. 0 팩토리얼은 1이다.

😊 간단한 재귀 문제다. 가장 중요한 건 0!을 처리해주는 것이다.
피보나치수열 재귀와 비슷하다. n이 1로 갈때까지 재귀를 실행해주고 return하며 1부터 input까지 값을 곱해간다.

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

Code

😢 이런 저런 패턴이 많이 보여서, 어떤 패턴으로 접근할 지 고민을 많이 했다.

😊 문제의 의도는 a-1층의 1호부터 b호까지 모두 더하라는 것이 아닐 것이다. 물론 더해도 된다. 하지만 시간이 오래 걸린다.

예를 들기 위해, 4층, 1-5호까지 있는 아파트를 표로 작성해봤다(참고로 층은 0부터 시작한다)
어떤 패턴이 있는지 잘 살펴보면, [a행, b열]에 있는 값은 [a행, b-1열] + [a-1행, b열]의 값으로 이루어져 있다.

또한, 가장 아래 행의 각 열은 1부터 b까지 1씩 순차적으로 증가하는 값을 가지며, 왼쪽의 첫 번째 열은 항상 1 값만 갖는다.

입력으로 a=2, b=3을 받았다고 가정해보자
[2, 2] == 4, [1, 3] == 6이라는 것을 알 수 있고, 이 값을 더하면 4+6=10. 곧, [2, 3]의 값이다.
이 패턴을 가지고 코드를 작성해보면 위의 코드가 나온다.

외부 for loop에서 배열을 항상 [1]부터 시작하도록 초기화해준다.
내부 for loop에서는 가장 아래 행이면 1씩 증가하도록 if 조건문을 걸어주고,
그 외 경우는 위의 [a행, b-1열] + [a-1행, b열] 패턴에 맞도록 값을 저장해준다.
그리고 마지막에 알고 싶은 층과 호수를 배열의 인덱스에 넣고 찾아주면 된다.

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

✨ 합병 정렬 또는 병합 정렬(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이 진행되는 전체 이미지

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)를 작성해보겠다.

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)

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)

Code

😢 이런저런 조건들을 떠올리다보니 산으로 갔던 문제
역시 조건 그대로 코드를 작성하기 보다는, 다른 시각으로 바라보는 조건이 핵심

😊 가장 최고의 조건을 걸어두고 하나씩 물러나며 최선의 조건을 찾아야한다.

최종 제출 답안)

bigMax 변수에 가장 큰 봉지인 BIG(5)으로 설탕 무게를 나눴을 때, 나오는 숫자를 저장한다.
그리고 bigMax가 음수로 떨어지지 않을 때까지 while loop을 열어준다.

임시로 만든 tempSugar 변수에는 앞에서 계산한 bigMax 무게만큼 SUGAR를 빼준다.
만약 tempSugar가 작은 봉지인 SMALL(3)으로 나눴을 때 나머지가 없다면 최선의 조건이기 때문에 출력하고 계산을 끝내준다.
하지만, 만약 조건에 맞지 않는다면 bigMax를 1만큼 빼준다.
그런 후 tempSugar의 크기를 5만큼 높여주고 다시 3으로 나눠본다.

이런식으로 계속 반복하며 다시 5씩 늘려보고 다시 3으로 나눠봤을 때 나머지가 0이라면 계산이 가능한 설탕 무게이고,
그렇지 않고 bigMax가 음수로 떨어진다면 그건 계산할 수 없는 설탕 무게이므로 -1을 출력한다.

다른 정답자들 중에 배울 수 있었던 답안)

😊 먼저, SMALL(3)의 개수를 담아두기 위한 bags 변수를 선언해준다. while loop을 무한으로 돌리면서,
설탕을 BIG(5)으로 나눴을 때 나머지가 0이라면 BIG으로 나눈 값과 bags를 합쳐 출력한다.
그리고 만약 SUGAR가 0이하로 떨어지면 -1을 출력해준다.
둘 다 해당되지 않으면 설탕을 SMALL(3)만큼 빼주고, bags를 1 증가시켜준다. (설탕을 3으로 나눈 것과 같은 의미)

즉, 이것도 역시 최고의 방법인 5를 우선으로 나눠주고, 그게 되지 않는다면 3을 하나씩 늘려가는 방법으로 해결했다.
이것도 굉장히 훌륭한 방법이라고 생각한다.

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