Daehyunii's Dev-blog
<인프런 알고리즘 문제풀이 기초강의> TIL-80 본문
오늘은 탐욕 알고리즘, 이분 검색, 이분 검색을 활용한 결정 알고리즘과 관련된 문제들을 풀었다. 탐욕 알고리즘이란 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 알고리즘을 말한다. 그렇기 때문에 최선을 선택을 위해 주어진 정보들을 잘 정렬하여 이를 활용할 필요가 있다. 탐욕 알고리즘에서 느낀점은 원하는 답을 찾기 위해서 문제를 잘 분석할 필요가 있다는 것이다. 회의실 배정 문제를 살펴보면 끝나는 가장 이른 시간에 끝나는 회의는 무조건 가장 빨리 끝나는 회의이기 때문에 반드시 들어가게 된다는 것만 알더라도 문제를 해결하는데 한결 수월해 진다. 이처럼 주어진 정보들을 잘 정렬하고 비교해야 하는 값들을 명확하게 구분한 후 코드를 작성해야 할 것 같다. 그리고 이분 검색의 경우에는 말 그대로 해당 값들의 중간을 기준으로 잡고 필요없는 나머지 부분들을 과감하게 제외하고 또 제외하고 남은 값들의 중간값을 구하는 방식으로 계속해서 절반씩 줄여나가 원하는 값에 도달하는 검색 방법이다. 한 번 검색을 할 때마다 검색해야 하는 정보가 절반씩 줄어들기 때문에 굉장히 효율성이 뛰어난 검색 방법이다. 또 이러한 검색 방법을 활용해서 결정 알고리즘 문제를 해결할 수 있다. 이분 검색의 절반씩 줄여나간다는 성질을 이용해서 문제를 해결하는 것이다. 물론 개념적으로는 너무 쉽게 와닿지만,,,막상 코드를 구현하는것 자체는 쉽지 않았다. 강의와 코드 설명을 듣고 코드를 구현해야 그나마 문제를 해결할 수 있었던것 같다...
2022.09.06 - [언어 공부 및 정리/JS[알고리즘 문제풀이(인프런 강의)]] - 회의실 배정(탐욕 알고리즘)
회의실 배정(탐욕 알고리즘)
문제(출처 : 인프런 자바스크립트 알고리즘 문제풀이 강의, 정보올림피아드) 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들 려고 한다. 각 회의에
pinetree93.tistory.com
부터
2022.09.06 - [언어 공부 및 정리/JS[알고리즘 문제풀이(인프런 강의)]] - 마구간 정하기(결정알고리즘)
마구간 정하기(결정알고리즘)
문제(출처 : 인프런 자바스크립트 알고리즘 문제풀이 강의, 정보올림피아드) N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마 구간간에 좌표가 중복되
pinetree93.tistory.com
까지
'✏️ 2022. TIL > September' 카테고리의 다른 글
| <인프런 알고리즘 문제풀이 기초강의> TIL-82(문제풀이 기초강의 완강) (0) | 2022.09.07 |
|---|---|
| <인프런 알고리즘 문제풀이 기초강의> TIL-81 (0) | 2022.09.06 |
| <인프런 알고리즘 문제풀이 기초강의> TIL-79 (0) | 2022.09.04 |
| <인프런 알고리즘 문제풀이 기초강의> TIL-78 (0) | 2022.09.02 |
| <인프런 알고리즘 문제풀이 기초강의> TIL-77 (0) | 2022.09.02 |
