코딩테스트 연습 → 탐욕법(Greedy) → Lv.3 단속카메라알고리즘 문제를 많이 풀어본 사람은 문제 유형만 봐도 그리디(Greedy) 알고리즘을 사용한다는 것을 바로 판단해야 한다. 필자 또한 비슷한 유형의 문제들을 풀어본 경험으로 인해 그리디를 사용한 문제라는 것을 알았지만, 왜 그리디를 사용하는 것인가? 라는 주입식 교육의 폐해인 의문이 들어 풀이 방법을 함께 살펴보고자 한다.풀이 방법 공식 예시와 함께 문제를 살펴보자. 먼저, 첫 번째 차량은 -20의 위치에서 진입하여 -15의 위치까지 달린다. 현재까지의 단속카메라 위치는 -20 ~ -15 사이의 어디든 설치해도 1개의 카메라만 설치하면 될 것이다.  두 번째 차량은 [-14, -5]의 위치까지 달린다. 그림으로 봤을 때 첫 번째 차량과 겹치는..

코딩테스트 연습 → 연습문제 → Lv. 3 최고의 집합 풀이 방법결론부터 말하자면 그리디(Greedy) 기법을 사용해야 한다. 집합 내 필요한 원소의 개수 n개가 있을 때, 각각의 원소에 s 값이 골고루 분배 되어야 한다. 즉, 차이가 가장 덜 나는 원소들로 집합을 이루어야 한다는 것이다. 말로 설명하자면 어려우니 예시와 함께 이해해보자. n = 2, s = 9일 때를 보자. 현재 집합에 아무 숫자도 넣지 않았기 때문에 필요한 원소의 개수는 2개이다. 이는 [1, 8], [2, 7], [3, 6], [4, 5]와 같이 분배가 될 수 있는데 각 원소의 차이가 가장 적은 원소 집합은 [4, 5]이다. 그러므로 정답이 [4, 5]가 되는 것이다. 위의 예시만으로는 감이 잡히지 않을 것이다. 다른 예시로 n =..

✅ 문제14002번 가장 긴 증가하는 부분 수열 4 14002번: 가장 긴 증가하는 부분 수열 4수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net ✅ 풀이import java.io.*;import java.util.StringTokenizer;public class Main { private static int[] nums, count; private static StringBuilder sb; public static void main(String[] args)..

🔗4386번 : 별자리 만들기● Java 풀이● 시간 제한 1초● 메모리 제한 128 MB✅ 문제도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.✅ 테스트 케이스/** 출처 (https://www.acmicpc.net/board/view/82327) **/// input64 15 82 18 42 91 4// answer18.3..

🔗17135번 : 캐슬 디펜스● Java 풀이● 시간 제한 1초● 메모리 제한 512 MB문제 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에..

🔗 1600번 : 말이 되고픈 원숭이● Java 풀이● 시간 제한 2초● 메모리 제한 256 MB 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x   x  말  x   x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움..