22. 그리디 (Greedy)항상 가장 최선의 선택(국소 최적)이 전체 최적을 만든다고 가정예: 거스름돈 문제int[] coins = {500, 100, 50, 10};int target = 1260;int count = 0;for (int coin : coins) { count += target / coin; target %= coin;}System.out.println(count); // 최소 동전 개수📌 대표 문제: 동전 문제, 회의실 배정, 배낭 문제(단순), 줄 세우기, 최소 비용 선택 23. 누적합 (Prefix Sum)구간 합을 빠르게 구하기 위해 전체 누적합을 미리 계산int[] arr = {1, 2, 3, 4, 5};int[] prefix = new int[arr.length..
📑 1. 문제설명💡 2. 풀이 과정 문제를 요약하면 토너먼트 게임에서 특정한 번호의 두 참가자가 만날 때 까지 몇 번의 경기를 진행해야 하는지 횟수를 구하는 문제이다. 처음에 참가자들은 1부터 N까지 번호를 받는다.그리고 다음 라운드에 진출한 참가자들은 다시 1부터 N/2 까지의 번호를 받는다. 입출력 예N=8, A=4, B=7 이 경우 8명의 참가자들이 경기를 할 때 4번 선수와 7번 선수가 만날 때까지의 경기 횟수를 아래 그림으로 그려 보았다.각 라운드에서 4번과 7번은 항상 이겨서 다음 라운드로 진출한다고 가정하고 풀어야 하는 문제이다.4번과 7번은 계속 이겨서 다음 라운드로 진출한다4번은 3번을 이기고, 1 또는 2번을 이겨서 총 2번 이긴다7번은 8번을 이기고, 5 또는 6번을 이겨서 총 ..
스택(Stack)개요"스택"은 데이터를 쌓아서 사용하는 자료구조로, "후입선출(LIFO, Last In First Out)" 방식으로 작동한다. 즉, 나중에 들어간 데이터가 먼저 나오는 구조이다. 스택은 주로 함수 호출, 계산기 프로그램에서 수식 계산, 또는 브라우저의 뒤로 가기 기능 등에서 사용된다.* 이와 반대의 "선입선출(FIFO, First In First Out)" 구조의 자료구조를 '큐'라고 한다. 스택을 활용한 코딩테스트 문제는 유형이 정해져 있다. 문제를 잘 읽어보고 데이터를 쌓아 올린다든지, 나중에 쌓은 데이터를 먼저 처리하는 방식이면 스택을 활용하면 된다. 스택을 사용하는 문제 유형 ✅ 괄호 유효성 검사주어진 문자열에서 괄호의 짝이 맞는지 확인하는 문제스택을 사용해 여는 괄호는 스..
📑 1. 문제설명10진수를 입력받아 2진수로 변환해 반환하는 solution() 함수를 구현하세요 제약조건decimal은 1이상 10억 미만의 자연수입출력 예decimalreturn10101027110111234511000000111001 💡 2. 풀이 과정10진수를 2진수로 표현하는 과정은 이미 수학적으로 증명된 것이기 때문에 간단하게 적는다.10진수 N을 2로 나눈 나머지, 즉 %2 연산을 한 값을 저장하고, N은 다시 2로 나눈다.몫이 0이 아니라면 나머지를 버리고 다시 1을 수행한다모든 과정이 끝나고 1에서 저장한 수를 뒤부터 순서대로 가져와 붙인다. 예를 들어 십진수 13을 위 과정대로 2진수로 변환하는 모습은 위 그림과 같다. 13을 2로 나누어가면서 나눈 나머지를 순서대로 저장한 후, ..
정렬(Sort)개요데이터를 오름차순 또는 내림차순으로 배열하거나 리스트의 요소를 정렬하는 과정이다. 정렬을 활용한 코딩테스트 문제는 매우 다양하다. 정렬 문제는 문제를 풀 때는 정렬 기준을 정확히 파악하고, 그에 맞는 알고리즘을 선택하는 것이 중요하다. 정렬 알고리즘, 이진 탐색, 투 포인터, 빈도수 계산 등 다양한 기술을 조합해 해결해야 하는 문제들이 많다. 주어진 조건을 Arrays.sort() 를 이용해서 정렬해야 하는 문제도 있고, 정렬 기준을 사용자 정의 객체에 맞게 지정해야 하는 경우, Comparator 인터페이스를 구현한 객체를 Collections.sort() 또는 Arrays.sort()에 전달하여 정렬하면 되고, 이 때 Java 8 이상에서는 Comparator를 람다 표현식으로 ..
그리디 알고리즘(Greedy Algorithm)개요greedy형용사 - 1. 탐욕스러운 2.욕심 많은 그리디 알고리즘(Greedy Algorithm)은 매 순간 가장 최적이라고 판단되는 선택을 반복하여 최종 해답을 구하는 알고리즘이다. 즉, 현재 단계에서의 최선의 선택이 최종적으로도 최적해(Optimal Solution)가 된다고 가정하고 문제를 해결한다. 코딩테스트에서 만날 경우 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형지역 최적해(Local Optimum) → 전역 최적해(Global Optimum) 보장 가능해야 함탐욕적 선택(Greedy Choice)과 최적 부분 구조(Optimal Substructure) 만족✅ 동적 프로그래밍(Dynamic Programming)과 차이..
