코딩 테스트 개요 및 문제 풀이를 위한 자바스크립트 문법 04

이 글은 네이버 블로그에 2024년 2월 4일에 올렸던 것을 그대로 옮겨온 것입니다.

탐욕 알고리즘

현재 상황에서 당장 가장 좋아보이는 상황만 선택하는 알고리즘

흔히 그리디 알고리즘, 탐욕법

최적의 해를 구하기 위한 근사적인 방법으로 사용

이진 탐색 알고리즘

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 하나씩 확인 한다.

이진 탐색 : 정렬 되어 있는 리스트에서 탐색 범위를 절반씩 좁혀 가며 데이터를 탐색한다.

이진탐색을 수행할 때는 시작점과 끝점을 기준으로 탐색 범위를 명시한다.

정렬된 배열에서 특정 원소의 개수 구하기

이진 탐색 알고리즘

값이 특정 범위에 속하는 원소의 개수 구하기

정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산 요구

lowerBound () / upperBound () 직접 구현해야해

lowerBound : 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 왼쪽 인덱스를 반환

upperBound : 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 오른쪽 인덱스를 반환

파라메트릭 서치

이진 탐색 아이디어

이진탐색 조건 : 변경할 값에 대해여 f(x)가 단조 증가/ 단조 감소

예. 성적이 [a,b] 사이인 학생들 찾기

최적화 문제를 결정 문제로 바꾸어 해결하는 기법이

파라메트릭 서치

특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

백트레킹 알고리즘

그래프/ 트리의 모든 원소를 완전 탐색하기 위해

누적합 알고리즘

구간합 문제 : 나열된 N개의 수가 있을때, 특정 구간의 모든 수를 합한 값을 계산하는 문제