📌강의 정리
이분탐색을 하는 것은 두 말 사이의 거리이다.
말들을 탐색하는 것이 아니다.
따라서 mid값은 1+9/2 → 5이고 ep라는 변수를 따로 만들어서
제일 가까운 두 말의 거리가 5일때 그리고 3일때 이런식으로 해서 최대거리를 구한다.
📌느낀점
쓰면서도 내가 제대로 이해한건가 싶다… 결정알고리즘은 한번으로 끝날 알고리즘이 아닌 것 같다.
우선 앞으로 나올 알고리즘들은 각 테마가 있고 그 테마들의 대표격인 문제들을 외워서 응용하든지 해야겠다.
마치 옛날에 수학풀때 매우 어려운 심화과정 문제들을 푸는 느낌이다.
이제부터는 전략을 다시 짤 필요가 있다.
아직 내 수준에서는 이제부터 나올 문제들을 완벽하게 풀어낼 수 없다.
//나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function count(stable, dist) {
let cnt = 1;
return cnt;
}
function solution(c, stable) {
let answer;
let lt = 0;
let rt = stable.length;
stable.sort((a, b) => a - b);
console.log(stable);
for (let i = 0; i < stable.length; i++) {
count(stable, 3);
}
return answer;
}
// 1 2 4 8 9
// 처음에 오름차순 sort하고
// 최대거리가 나올수 있게 그걸 이분 탐색한다.
// 계속 반복할때 최대값이 하나 업데이트 되는 함수를
// 만드는게 핵심이다.
// while(lt > rt),
// 양쪽 끝은 무조건 말이 하나씩 있다.
let arr = [1, 2, 8, 4, 9];
console.log(solution(3, arr));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function count(stable, dist) {
let cnt = 1,
ep = stable[0];
for (let i = 1; i < stable.length; i++) {
if (stable[i] - ep >= dist) {
cnt++;
ep = stable[i];
}
}
return cnt;
}
function solution(c, stable) {
let answer;
stable.sort((a, b) => a - b);
let lt = 1;
let rt = stable[stable.length - 1];
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (count(stable, mid) >= c) {
answer = mid;
lt = mid + 1;
} else rt = mid - 1;
}
return answer;
}
let arr = [1, 2, 8, 4, 9];
console.log(solution(3, arr));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 7. 정렬과 그리디, 결정알고리즘' 카테고리의 다른 글
| 11.뮤직비디오(결정알고리즘) (0) | 2022.07.09 |
|---|---|
| 10.이분검색 (0) | 2022.07.08 |
| 9.결혼식 (0) | 2022.07.07 |
| 8.회의실 배정 (0) | 2022.07.06 |
| 7.좌표 정렬 (0) | 2022.07.05 |