패스트캠퍼스 JavaScript 코딩테스트 강의 2주차

문종후·2023년 4월 30일

fastcampus 자바 자바스크립트 코딩교육 코딩자격증 코딩테스트 파이썬 패스트캠퍼스 패스트캠퍼스후기 패캠

학습기록

1. 정렬

1)선택정렬
매단계에서 가장 작은원소를 앞으로보내는정렬법(시간복잡도가 높은 비효율적인 정렬법이다.)
앞에것부터 모든요소를 전부다 체크한후 실행되기때문에 최악의경우 NxN의 시간복잡도를가짐.
(이중반복문으로구현)-->요소 두개 비교해서 작으면 위치바꾸고 (반복)하는식으로 구현.

2)버블정렬
붙어있는 두원소비교 정렬안되있으면 바꿔줌.
(정렬알고리즘짜보기)

const swap = function (idx1, idx2, arr) {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
};

let bubbleSort = function (arr) {
let N = arr.length;

for(let i = 0; i < N; i++) {
let count = 0;
for(let j = 0; j < N - 1 - i; j++) {
if(arr[j] > arr[j+1]) {
count++;
swap(j, j+1, arr);
}
}
// count가 0 이라는 것은 모든 요소들이 제자리(i번째)에 들어있다는 이야기이므로
if(count === 0) {
break; // 거기서 멈추기
}
}

return arr;
};

3)삽입정렬

각 데이터를 적절한위치에 삽입하는 정렬기법

4)병합정렬
분할,정복,조합 단계

재귀를 사용함( 큰문제를 비슷한 작은문제단위로 쪼개서 해결)

==>여기서 재귀를 사용하는경우에 오버헤드(overhead)가 발생할수있음
이녀석을 해결하기위해 메모이제이션기법을사용할때도있다.(객체로 중간값저장)

5)정렬 라이브러리->자바스크립트에선 sort()로 제공해줌.

그리디(탐욕)

그리디 알고리즘이란?

앞에서 간단하게 설명햇듯 결국 매순간 최고의선택(큰값)을 선택하며 나아가는 알고리즘을뜻함

일반적으로 코딩테스트에 출제되는 그리디알고리즘은 근사해가 최적의해인경우가많다.

그럼이거 어캐쓸꺼야?

먼저 이거쓰려면 방법을 고안해야됨 어떤식으로 현재상황에서 최선을고를지

그렇게짠후 고안한 알고리즘이 항상 최적의해를 뽑아주는지 확인한다(증명 단계)

잘이해 안될수도있으니 거스름돈 문제를가져와서 설명해봄.

만약 500원,100원,50원,10원짜리 동전이 엄청많은데 손님이 돈을 개같이줘서 6480원을 거슬러줘야한다고 해보자. 이때 동전의 개수를 최소화하려면 어떻게 거슬러줘야하는가?

자 동전의개수를 줄이려면 큰단위부터 거슬러줄수있는건 다거슬러주면됨.

500원으로 나눈최대치 개수 /남은돈

남은돈을 100원으로 나눈개수/남은돈..순으로 밑으로쭉쭉내려가면됨.

그럼이렇게 푸는게맞냐?라고 한다면 정당성을 따질때

왜 큰단위동전부터 고려를 해야하나? 라고따지면 할말이참많다.

이빡대가리야 큰단위로하면 작은단위로하는것보다 적게들지 이걸좀 고급지게말하면

각 화폐단위가 배수관계에있기때문이다. 500=100x5 /100=50x2 /50=10x5

밑으로 내려가면 내려갈수록 개수가늘어나지않는가? 따라서 내풀이는 정당하다.

이진탐색(알고리즘)

이태까지 우리가 탐색할떄 어떤식으로햇냐면 모든요소를 훑었다. 근데 이러면 시간이좀 오래걸리는감이있다.

이전에 재귀에 메모이제이션을 살짝이야기했는데 사실 그게 이거다.

이진탐색도 비슷하게 범위를 반씩 계속줄여나가 탐색시간을 줄여주는알고리즘이다.

function power(base, exponent) {
// todo: 여기에 코드를 작성합니다.
if(exponent===0)return 1

let half = parseInt(exponent/2)

let ans = power(base,half) // 계산량 줄임
// return ansans보다 return result 하는게 계산량이 줄어든다고 함. 그래서 한 변수에 넣은것
let result = ansans%94906249
if(exponent%2===0){
return result
}
else return result*base%94906249 // 마찬가지

}