그리디 알고리즘(Greedy Algorithm)개요greedy형용사 - 1. 탐욕스러운 2.욕심 많은 그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적이라고 판단되는 선택을 반복하여 최종 해답을 구하는 알고리즘이다. 즉, 현재 단계에서의 최선의 선택이 최종적으로도 최적해(Optimal Solution)가 된다고 가정하고 문제를 해결한다. 코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형지역 최적해(Local Optimum) → 전역 최적해(Global Optimum) 보장 가능해야 함탐욕적 선택(Greedy Choice)과 최적 부분 구조(Optimal Substructure) 만족✅ 동적 프로그래밍(Dynamic Programming)과 차이..
📑 1. 문제설명 입출력 예 설명 💡 2. 접근방식이 문제는 저번에 풀었던 단속카메라 문제와 비슷하다. [프로그래머스] (Java) 단속카메라 (그리디/Greedy)📑 1. 문제설명💡 2. 접근방식입출력 예로 주어진 route 배열을 막대그래프로 그려 봤다. 최소한의 카메라를 배치해야 하므로 구간 종료 위치를 기준으로 오름차순 정렬 차량이 구간에서 카메라awesomepossum.tistory.com 예시 그래프는 각 미사일을 끝점 e 기준으로 오름차순 정렬시킨 모양이다.그래프에서 (3,7)와 (4,8)은 순서가 잘못되었는데 오류로 추정된다.단속카메라 문제와 요격시스템 문제의 차이는 끝점 포함 여부이고 둘 다 그리디 알고리즘으로 해결하면 된다. 문제 풀이 방법배열을 끝점 기준으로 오름차순 정렬각..
📑 1. 문제설명💡 2. 접근방식n명의 선수가 있을 때, 각 선수는 모든 다른 선수와 경기를 하여 n-1번의 승패를 기록한다.즉, 전체 승패 결과만 있으면 각 선수의 상대적 위치를 정확히 판단해서 순위를 확정 할 수 있다. 승패를 통해 순위를 결정하는 방법은 간단히 말하면 모든 선수들 간의 직접적인 경기 결과를 반영하는 것이다. 예를 들어, 선수 i와 선수 j가 경기를 하여 승패가 결정되면, 그 결과를 기록한다. 플로이드 워셜(Floyd-Warshall) 알고리즘모든 쌍 최단 경로(all-pairs shortest path)를 구하는 알고리즘으로 그래프의 모든 노드 쌍에 대해 가장 짧은 경로를 찾는 알고리즘이다. 이 알고리즘을 사용하면 그래프의 모든 노드에 대해 다른 모든 노드로 가는 최단 경로를 ..
📑 1. 문제설명✏️ 2. 문제 요약문제에서 주어진 조건CAR_RENTAL_COMPANY_CAR CAR_RENTAL_COMPANY_RENTAL_HISTORY CAR_RENTAL_COMPANY_DISCOUNT_PLAN대여 중인 자동차들의 정보자동차 대여 기록 정보자동차 종류 별 대여 기간 종류 별 할인 정책 정보CAR_ID, CAR_TYPE, DAILY_FEE, OPTIONSHISTORY_ID, CAR_ID, START_DATE, END_DATEPLAN_ID, CAR_TYPE, DURATION_TYPE, DISCOUNT_RATE- 자동차 ID,- 자동차 종류,- 일일 대여 요금(원),- 자동차 옵션 리스트,- 자동차 대여 기록 ID,- 자동차 ID- 대여 시작일, - 대여 종료일- 요금 할인 정책 ID,..
📑 1. 문제설명⭐ 2. 정답코드내가 푼 코드 ORDER BY DATEDIFF (입소일, 퇴소일)SELECT I.ANIMAL_ID, I.NAMEFROM ANIMAL_INS I JOIN ANIMAL_OUTS O ON I.Animal_id = O.Animal_idORDER BY DATEDIFF(I.DATETIME, O.DATETIME)LIMIT 2이렇게 해서 정답처리가 됬는데 다른 사람들이 쓴 코드를 보다가 뭔가 이상한 점 발견!보호소 퇴소일 - 입소일 을 해서 그 값이 큰 순서대로 2건을 반환하는 건데나는 입소일 - 퇴소일로 반대로 적었다 대신 오름차순으로 하니까 작동한다.🐦 3. 다른 사람들이 푼 코드ORDER BY DATEDIFF (퇴소일, 입소일) DESCSELECT I.ANIMAL_ID, I.N..
📑 1. 문제설명❌ 2. 실패한 코드 PRODUCT_CODE 컬럼이 예를 들면 'A1000011' 이기 때문에SUBSTRING(컬럼명,시작인덱스,끝인덱스)로 앞 두 자리만 떼어 내야 한다. SELECT SUBSTRING(Product_code,1,2) AS CATEGORY, COUNT(SUBSTRING(Product_code,1,2)) AS PRODUCTSFROM PRODUCTGROUP BY SUBSTRING(Product_code,1,2), Product_codeORDER BY Category; 내가 작성한 코드의 실행 결과를 보면 A2 기준으로 GROUP 으로 묶이지 않은 것을 확인 할 수 있다.⭐ 3. 정답코드GROUP BY 절에서 SUBSTRING(Product_code,1,2)로만 묶어야 함P..
📑 1. 문제설명❌ 2. 실패한 시도SELECT CASE WHEN SUBSTRING(DIFFERENTIATION_DATE, 6,7) IN ('01', '02', '03') THEN '1Q' WHEN SUBSTRING(DIFFERENTIATION_DATE, 6,7) IN ('04', '05', '06') THEN '2Q' WHEN SUBSTRING(DIFFERENTIATION_DATE, 6,7) IN ('07', '08', '09') THEN '3Q' WHEN SUBSTRING(DIFFERENTIATION_DATE, 6,7) IN ('10', '11', '12') THEN '4Q' END AS QUARTER, COUNT(..
