감공사

Code

😢 이렇게 쉬울 거라고 생각하지 못 했던 문제

😊 x, y는 현재 나의 위치이며 w, h는 직사각형의 오른쪽 위 꼭짓점, 0,0은 왼쪽 아래 꼭짓점이다.

위 표을 좌표계라고 생각해보자. 그리고 벗어날 수 있는 모든 경우의 수를 배열에 저장해보자.
좌표 0,0 기준으로 직사각형을 벗어나려면 x, y값 그 자체로 움직여야 벗어날 수 있으므로 [x, y]를 배열에 우선 넣는다.(x-0, y-0)
좌표 w, h 기준으로 직사각형을 벗어나려면 w-x, h-y만큼 움직여야 벗어날 수 있다. 따라서, [w-x, h-y]를 추가적으로 배열에 넣는다.

결과적으로 [ x, y, w-x, h-y ] 총 4개의 경우의 수를 구할 수 있다(직사각형을 벗어날 수 있는 이동 값)
최종적으로 Math.min.apply(null, 배열)넣어서 최소값을 구하고 출력해주면 된다.

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

Code

😢 역시 에라토스테네스의 체를 이용하면 되고, 골드바흐의 파티션을 어떻게 구할지 생각을 해줘야 한다.

😊 31번째 줄 코드는 이전 문제에서 사용한 것과 같고, 33-37번째 줄 코드에서 2부터 n까지 소수를 저장해준다.

중첩 for loop을 열고, 입력 받은 n을 0으로 만들 수 있는 소수의 짝을 checkPrimePair 배열에 2차원 형식으로 저장해준다.
(checkPrimePair가 저장된 모습은 [ [2, 3], [3, 5] ] 같은 형식이라고 생각해주면 된다)

그리고 또 다시 for loop을 열고 checkPrimePair중 가장 작은 차이가 나는 소수 짝의 index를 구해준다.

마지막으로, 해당 index의 짝을 join(' ')형식으로 출력해주면 된다.

지금까지 풀었던 알고리즘 중에 가장 길지 않나 싶다. 다시 풀어보며 조금 더 개선할 수 있는 곳을 찾아봐야겠다.

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

Code

😢 '에라토스테네스의 체'를 이용해서(1929번 문제) 구간만 잘 정해주면 된다.

😊 Solution 1)
마지막에 0을 받으면 끝나도록 while loop을 돌려줬다.
1929번 문제에서 M, N을 여기서는 n = 입력 받은 값, m = n * 2로 구간을 설정해줬다.
또한, 값을 판단하기 위해 선언하는 Array에서, 구간을 벗어나는 index에 false를 세팅해주고 시작하면 된다.
(0보다 크고 n보다 작거나 같을 때까지)

추가 Solution 2) 코드 개선
전체 입력을 반복하는 반복문은 for ... of로 대체하였으며, 첫 째 줄에 0을 받으면 break하도록 설정하였다.
n보다 크고 2n보다 작거나 같아야 하므로, 구간은 n+1부터 2n까지라고 보면 된다. 
따라서 n=num+1, m=2*num으로 구간을 선언해주었다.
마찬가지로, m+1만큼 Array를 선언해준 후 fill(true)로 채워줬다. (index 0과 1은 false로 채워줬다)
이제 에라토스테네스의 체 방법으로 소수를 구해주고, n부터 m까지 소수가 있다면 count 후 counter를 출력해줬다.

이렇게 3396ms에서 520ms로 속도를 개선할 수 있었다.

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

Code

😢 원리를 이해하고 코드를 구현하는 데, 시간이 조금 걸렸다. 여러 자료도 참고했다.

😊 에라토스테네스의 체 방법으로 소수를 구하는 문제다.
소수를 구하면, 그 소수의 배수는 소수가 될 수 없다. 그래서 그 배수들을 사전에 제거하고 남은 수를 이용해 소수를 구하는 방법이다.

먼저, (1 ≤ M ≤ N ≤ 1,000,000)이므로 MAX를 선언해준다.
그리고 소수를 판단할 isPrimeArr(Array)를 N+1만큼 선언해준다(인덱스를 N까지 사용할 것이므로)
isPrimeArr는 .fill()을 이용해 모두 true값으로 세팅해줬다. 그리고 0과 1은 소수가 아니므로 false를 세팅해줬다.

for loop을 돌리면서 해당 소수의 배수는 false로 값을 바꿔준다. 그리고 조건문을 이용해 우리가 구할 숫자를 넘어가면 break;
내부 for loop에서 for조건문의 마지막을 넣지 않았는데, 그 안에 square += i를 넣어줘도 된다. 같은 의미다(배수를 계속 더해줌)

마지막에 입력 받은 구간만큼 for loop을 이용해 출력해주면 된다(isPrimeArr이 true면 소수)

아래 링크를 참고하면 이론과 함께 시각적으로 어떻게 진행되는지 볼 수 있어 좋다. 좋은 참고자료!

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

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

Code

😢 기본 '소수 찾기'문제에서 조건을 조금 추가해주면 쉽게 해결되는 문제

😊 최솟값을 구해주기 위해 Array를, 소수값의 합을 구해주기 위해 sum 변수를 추가했다.
소수를 구하는 부분은 function으로 따로 빼주었으며,
function내에서 소수를 찾으면 arr에 push함과 동시에 소수들을 sum에 누적해 줬다.
그리고 마지막에 만약 Array.length가 없다면 소수는 없는 것이므로 -1을 출력하도록 했다.

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

Code

😢 소수란? 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수.

😊 따로 function을 만들어서 풀었다.
0 또는 1은 소수가 아니므로 if(n < 2) 조건문을 걸어 return;했고,
2부터 자기 자신-1까지 나눠주면서 나머지가 0된다면 소수가 아니므로 return;
위의 조건에 모두 해당되지 않는다면, 해당 숫자는 소수이므로 counter++;

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

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)