알고리즘 및 데이터 구조

코딩테스트 연습 → 탐욕법(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 =..

✅ 문제There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:Every worker in the paid group must be paid at least their minimum wage ex..

✅ 문제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)..

✅ 문제12110번 2048 (Easy) 12100번: 2048 (Easy)첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2www.acmicpc.net✅ 풀이import java.io.*;import java.util.*;public class Main { private static class Block { public Block(long num, int count) { this.num = num; this.count = count; // 몇 번째 이동에서 움직였는지 확인할 변수 ..

🔗 2011번 : 암호코드● Java 풀이● 시간 제한 2초● 메모리 제한 128 MB✅ 문제상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야.선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어.상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는건 쉽게 알수 있잖아?선영: 예가 적절하지 않았네 ㅠㅠ 만약 내가 500자..