1. 문제 설명 📌문제 설명문제 설명 생략2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHMGreedy 알고리즘은 매 선택의 순간에 당시 할 수 있는 최선의 선택을 하는 것이 전체 문제에서도 최적의 해를 구하는 것임을 가정하는 알고리즘이다.여기서는 미사일의 묶음을 끝지점 기준 오름 차순으로 정렬하고, 미사일 묶음의 최대한 끝지점에서 차례대로 요격해 나가면 최소한으로 요격 미사일을 사용하는 것이다. 해당 방법은 다음과 같은 이유로 유효하다.미사일을 만나면 무조건 요격해야 한다. 안하고 지나치는 경우는 없다.따라서 미사일을 만나면 최대한 겹치게 삭제해야 한다.하나의 미사일 묶음 A가 다른 미사일 묶음과 최대한 겹치는 경우는 A의 끝지점에서만 발생한다.예를 들어보겠다.다음과 같이 폭격 미사..

1. 문제 설명 📌문제 링크아날로그 시계의 초침이 시침 혹은 분침과 겹칠 때마다 알람을 울릴 건데, 주어진 시작 시간부터 끝시간 내에 알림이 몇 번 울렸는지 횟수를 반환하는 함수를 작성하는 문제. 시계의 초,분,시침은 연속적으로 움직인다. 따라서 겹치는 시기가 0.001초 단위일 수도, 0.00001초 단위일수도 있다. 이를 다 생각해서 겹치는 횟수를 구해라! (Lv2 맞나?? Lv3로 격상해야할 듯...)2. 접근 방식 🗃️KEY WORD: SIMULATION시계 침들의 겹침 현상을 최대한 코드로 구현해야 한다. 하지만 연속적으로 이루어지는 움직임 속에서 겹치는 순간을 포착한다는 것은 불가능한 일이다. 따라서 겹친다의 기준을 다음과 같이 정한다.(1) 겹친다의 기준각도 상 초침이 시침 혹은 분침보다..

1. 문제 설명 📌문제링크2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHMGreedy Algorithm은 매 선택의 순간마다 당시 최선의 선택을 하는 것이 전체 문제에서 봤을 때 최선이라는 가정을 하는 알고리즘이다. 해당 문제는 -를 만난 순간부터 뒤에는 무조건 괄호를 활용해 모든 값을 -로 만들어버리면 된다. 최초 -를 만난 후 뒤의 계산에 +가 오든 -가 오든 적절히 괄호만 치면 모든 값을 -로 만들 수 있다. 예를 들어 25 + 32 - 26 - 27 + 28 - 29 + 30 - 3125 + 32 - 26 - (27 + 28) - (29 + 30) - 31처럼 말이다. 3. 코드 소개 🔎(0) 사전 지식문제의 입력이 String으로 뭉뚱그려 주어지기 때문에 문자열 자르기에 ..

1. 문제 설명 📌문제 링크회의시간의 시작과 끝이 주어질 때, 최대한 많은 강의를 회의실에 배정해라 (A 강의의 끝시간과 B 강의의 시작 시간이 같으면 연달아 배정할 수 있는 것으로 간주한다.) 2. 접근 방식 🗃️KEY WORDS: GREEDY ALGORITHMGreedy Algorithm은 선택의 순간에 최적의 선택지를 고르는 것이 전체 문제에서 최적의 선택을 하는 것이라 가정하는 알고리즘이다.빨리 끝나는 순으로 회의를 정렬제일 빨리 끝나는 회의가 A라면 A 회의 이후에 시작할 수 있으면서도, 최대한 빨리 끝나는 회의를 선택하는 것이 전체 문제에서 봤을 때 최대한 많은 강의를 고를 수 있는 방법임.2번을 모든 회의를 돌아보며 더 이상 고를 수 있는 회의가 없을 때까지 반복 3. 코드 소개 🔎..

1. 문제 설명 📌문제 링크문제에서 수열이 주어지는데, 수열은 기본적으로 모두 더해진다. 하지만 만약 사용자가 임의의 수 2개를 골라서 괄호를 쳤을 경우, 해당 수는 곱해진다. 모든 수는 단 하나의 괄호에 포함되거나 아니면 괄호에 아예 포함되지 않는 2가지 선택지밖에 없다고 했을 때, 수열로 만들 수 있는 최대값을 구하라.예를 들어 수열이 [0,1,2,4,3,5]로 주어졌을 때, 괄호가 없다면 합은 15이지만, 다음과 같이 괄호를 활용하면 0 + 1 + (2*3) + (4*5) 가 되면 값이 27로 최대가 된다.2. 접근 방식 🗃️KEYWORD: GREEDY ALGORITHM(1) 경우의 수 생각하기먼저 주어진 두 개의 수로 최대값을 만들 수 있는 경우는 무엇이 있을까?두 수 모두 0보다 클 때: 이..

1. 문제 설명 📌문제 링크이번 문제도 조건이 직관적이어서 추가적인 설명 생략2. 접근 방식 🗃️KEY WORD: Greedy AlgorithmGreedy 알고리즘은 매 선택의 순간에 최선의 선택을 해나가는 것이 전체 문제에서 봤을 때도 최선이라고 가정하는 알고리즘이다. 해당 문제도 최소한의 비교를 위해서는 매번 카드 수가 적은 묶음을 2개 골라서 합치면서 나아가야 한다. 그렇기에 Greedy 알고리즘을 활용해야 한다. 여기서 주의해야할 점은 합친 카드 뭉치보다 카드 수가 더 작은 기존 카드 뭉치가 2개 이상 존재할 수 있다는 것이다. 이러한 경우가 문제의 예제에는 안 나와 있어서 간과하기 쉽다. 예를 들어보자.N = 6이고 각 카드 묶음의 카드 수는 [10, 15, 17, 19, 24, 25]라고 ..

1. 문제 설명 📌문제 링크설명이 직관적이라 추가 설명 생략2. 접근 방식 🗃️KEY WORD: Greedy Algorithm동전 수가 무한하기 때문에 Greedy 알고리즘을 적용하면 된다. Greedy 알고리즘은 매 순간 최적의 선택을 하는 것이다. 여기서 최적의 선택은 가능한한 큰 단위의 동전을 사용하여 동전 개수를 줄이는 것이다. 따라서 내림차순으로 동전 단위를 하나씩 훑으며, K원을 최대한 큰 단위의 동전으로 차감한다.내림차순으로 동전 조회만약 현재 조회 중인 동전으로 K원을 나눌 수 있다면? 나눈 몫만큼 동전을 사용 가능한 것임으로 몫을 답에 누적시킴K원은 (해당 동전의 단위 x 몫) 만큼 차감되었으므로, 나머지만큼만 남아있는 것이다. 따라서 K = K%단위로 갱신한다.1,2,3번을 K ==..

1. 그리디 알고리즘은 무엇인가요? 💡Greedy Algorithm은 매 선택의 순간마다 당시에 고를 수 있는 최선의 선택지를 골라가는 것이 전체에서 봤을 때 최선의 선택이라고 가정하는 알고리즘이다.예를 들어 다음과 같은 문제가 있다고 해보자.현재 A의 시점에서 고를 수 있는 선택지 중 C가 최단거리이다. 그러므로 C를 선택한다.C 시점에서 고를 수 있는 선택지 중 최단 거리로 갈 수 있는 노드는 G이다. 따라서 G를 선택한다. 두번의 선택 후 무조건 F를 비용 0으로 갈 수 있다고 할 때, 전체 노드는 다음과 같다.매 순간 갈 수 있는 최선의 선택지를 골랐더니 전체에서 봤을 때도 최선의 선택이었다. 이와 같이 매 순간의 최선 = 전체의 최선 이 성립할 때, 이러한 논리를 Greedy 알고리즘이라 한다..