My Tech Blog (Greedy)

그리디 알고리즘(Greedy Algorithm)개요greedy형용사 - 1. 탐욕스러운 2.욕심 많은  그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적이라고 판단되는 선택을 반복하여 최종 해답을 구하는 알고리즘이다. 즉, 현재 단계에서의 최선의 선택이 최종적으로도 최적해(Optimal Solution)가 된다고 가정하고 문제를 해결한다. 코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형지역 최적해(Local Optimum) → 전역 최적해(Global Optimum) 보장 가능해야 함탐욕적 선택(Greedy Choice)과 최적 부분 구조(Optimal Substructure) 만족✅ 동적 프로그래밍(Dynamic Programming)과 차이..

📑 1. 문제설명💡 2. 접근방식입출력 예로 주어진 route 배열을 막대그래프로 그려 봤다. 최소한의 카메라를 배치해야 하므로 구간 종료 위치를 기준으로 오름차순 정렬 차량이 구간에서 카메라를 단 한 번만이라도 만나면 됨종료 지점에서 다음 구간과 겹치게 되므로 최소한의 카메라를 배치가능카메라 배치는 도로의 가장 왼쪽 끝부터 탐색하며 시작된다.입출력 예시에서 MIN_VALUE인 -20 지점부터 오른쪽으로 가며 종료구간과 시작구간이 겹치는 부분에 카메라가 배치된다.구간 중 가장 처음으로 만나는 종료 위치는 -15이다.따라서 이 위치에 첫 번째 카메라를 설치한다. 그리고 -13지점에서 현재 구간과 다음 구간이 만나지만 이미 해당 구간에는 카메라가 설치 완료 되었으므로 스킵한다. 그리고 다음 구간인 [-..

📑 1. 문제설명💡 2. 접근방식문제에서 주어진 것n : 전체 학생의 수lost : 체육복 도난당한 학생들의 번호들  (배열) reserve : 여벌 가져온 학생 번호들 (배열)체육복은 앞,뒤 번호 학생 에만 빌려줄 수 있음.도난 당한 학생들은 여분이 없어서 체육복 빌려줄 수 없음.1. `lost`와 `reserve` 배열 정렬 2. 체육수업에 참여할 수 있는 학생의 수 = 체육복이 있거나 빌릴 수 있는 학생들의 수 `체육복을 도난 당하지 않은 학생의 수` + `도난당했지만 예비로 들고 온 학생의 수` + `도난당했지만 체육복을 빌릴 수 있는 학생의 수`이 모든 학생들의 수를 누적해서 answer 변수에 담아 준다.  ✅ 체육복을 도난 당하지 않은 학생의 수= 전체 학생의 수 - 체육복을 도난당한 학..