개발하는 동그리

문제 풀이 설명 (summary)금지된 목록을 모두 숫자로 변환하고 오름차순으로 정렬최대 금지 항목이 30만개 이므로 이분 탐색으로 정렬하여 현재 n값보다 작은 갯수가 몇개인지 파악하여 추가금지항목 갯수만큼 n에 추가하고, 추가값도 반복해서 카운팅하고최종 카운트를 문자열로 바꿔서 출력한다. 문제 풀이 접근법26진법을 사용한다. 알파벳 하나하나 숫자로 해시맵에 저장문자열을 숫자로 변환하는 메서드 활용숫자를 문자열로 변환하는 메서드 활용 풀이 코드 (Code)import java.util.Arrays;import java.util.HashMap;import java.util.Map;public class Main { public static void main(String[] args) { ..

[프로그래머스] 17680 : 캐시 [JAVA] Lv.2 1. 준비대소문자 구분하지 않으므로, 주어진값을 모두 소문자로 변경한 후 계산해야 한다. 그리고 casheSize가 0인 경우에는 하나도 저장할 수 없으니 cities 크기만큼 * 5 해주면 된다. 2. 캐시 입출력이 문제는 deque 를 사용하면 쉽게 풀 수 있다.ArrayDeque cache = new ArrayDeque();cache.contains(city) 문제 풀이 설명 (summary)Deque를 활용하여 cities 값을 하나씩 검증하여 추가한다.같다면, 카운트를 + 1 해준다. 이전의 같은 값을 삭제하고 새로 city값을 추가해준다같지 않다면, 카운트를 +5 하고 가장 먼저 추가한 값을 삭제하고, city값을 추가해준다. 만약에..

[프로그래머스] 12927 : 야근지수 [JAVA] Lv.3 어려워 보이지만, 우선순위 큐만 사용해본 적이 있다면, 매우 쉽게 풀 수 있다. 우선은 내림차순으로 정렬해주는것이 가장중요하다. 왜냐하면 가진 업무처리 시간을 최적으로 활용하기 위해서는 남은 업무량을 큰것부터 없애는것이 가장 중요하다. 따라서 우선순위 큐를 사용하여, 모든 업무량을 넣어두고 큰 순서대로 업무를 처리하면 최종적으로 남는 업무를 모두 꺼내어 계산하면 끝난다. 문제 풀이 설명 (summary)우선순위 큐(PriorityQueue)(pq)를 사용하여, 업무량이 큰것부터 순차적으로 처리할 수 있도록 내림차순으로 정렬한다.작업시간만큼 우선순위 큐에서 큰것부터 꺼내어 count-1 해서 다시 pq에 넣어준다최종적으로 남은 pq를 모두 꺼..

[프로그래머스] 42884 : 단속카메라 [JAVA] Lv.3 1단계 : 정렬하기단속카메라 문제는 정렬하는게 가장 포인트다. 진입 지점으로 오름차순하면서 진입지점이 동일하다면, 진출 지점으로 오름차순을 하는 것이다. 예를 들어 {{2,5}, {2,4}, {3,3}, {5,8}} 가 있다고 가정하자. 우선 가장 작은 {2,5},{2,4}} 를 정렬하게 될텐데 진입 지점이 동일하므로, 진출지점으로 정렬하면 {2,4}{2,5} 가 된다. 나머지는 진입지점순서대로 정렬하면 {2,4}{2,5}{3,3}{5,8} 이 된다. 2단계 : 카메라 위치 지정하고 옮기기첫 카메라 위치는 현재 인덱스의 진출지점으로 초기화한다.첫 인덱스 진출지점은 4이므로, 현재 카메라 위치는 4가 된다.다음 인덱스 {2,5} = 진입시점 2..

[프로그래머스] 43238 : 입국심사 [JAVA] Lv.3 여러번 풀어보았던 문제인데, 다시 풀게 되었을 때 막막했다. 직관적으로 접근하면 문제를 해석하려고 하면 방법이 점점 복잡해지기만 할 뿐이었다. 그래서 느낀점은 문제를 읽고서 접근방식을 잘 선택하는게 가장 우선되어야 할 문제라고 생각했다.문제에서 순차적으로 진행되지 않고 주어진 시간내에 가능한 빨리 끝나도록 하는것이 목적이기 때문에 이번 문제는 각각 심사관들은 서로 연관성이 전혀 없다. 단 총 시간이라는 조건만 동일 할 뿐이다. 주어진 시간에 몇명을 심사할 수 있는지 각각 심사관별로 계산해서 총합이 주어진 시간에 심사할 수 있는 모든 사람의 수가 결정된다. 위에 글을 보고 풀 수 있다면, 가장 좋은 방법이 될 것이고 이해하기 어렵다면, 아래에 있..

문제 풀이 설명 (summary)각 도둑 A,B 가 각각 흔적 누적 개수 이상이 되면 실패한다. A 도둑이 남긴 흔적의 누적개수의 최솟값을 리턴해야 하므로 깊이 우선 탐색을 활용하여 도달했을 때 A도둑의 누적 개수를 기록 하여, 기존값과 비교해서 작은값을 저장해서 관리초기값 그대로라면 -1 출력 문제 풀이 접근법DFS 방식 가능DP 방식 가능 풀이 코드 (Code)import java.util.ArrayDeque;public class Main { public static void main(String[] args) { int[][] info = new int[][]{{1,2},{2,3},{2,1}}; int n = 4; int m = 4; Syst..

문제 풀이 설명 (summary)짝수인 경우 무조건 나누기홀수인 경우 -1 이동0이 될 때까지 반복 문제 풀이 접근법그리디 알고리즘(Greedy Algorithm)모든 상황에 순간이동이 무조건 우선적으로 실행하면 됨.현재 상황에 최적화 된 풀이로 진행 풀이 코드 (Code)public class Main { public static void main(String[] args) { int N = 6; System.out.println(solution(N)); } private static int solution(int s) { int ans = 0; while (s > 0) { if (s % 2 == 0) { ..

Deque / BFS / DFS 정리BFS (queue) -> add / poll : 먼저 들어온 데이터가 먼저 나가는 구조- FIFO (First In, First Out)- 삽입 (add): 데이터를 **뒤쪽(Rear)**에 추가.- 삭제 (poll): 데이터를 **앞쪽(Front)**에서 제거.DFS (stack) -> push / pop : 나중에 들어온 데이터가 먼저 나가는 구조- LIFO (Last In, First Out)- 삽입 (Push): 데이터를 **위쪽(Top)**에 추가.- 삭제 (Pop): 데이터를 **위쪽(Top)**에서 제거.-> BFS : Queue : 너비 우선 (Breadth) : 가까운 정점부터 탐색.-> DFS : Stack : 깊이 우선 (Depth) : 최대한 깊..

주제대표적인 알고리즘 기법(DP vs 다익스트라 vs 완전탐색) 구분하기 ✅ 알고리즘 세 가지 분류분류대표 기법주로 사용하는 상황완전탐색 (Brute Force)백트래킹, DFS, BFS가능한 모든 경우를 직접 탐색해야 할 때 (최대값, 조합 등)동적 계획법 (DP)Memoization, Tabulation중복된 하위 문제가 있고, 최적해를 저장하여 재활용 가능할 때다익스트라 (Dijkstra)우선순위 큐 기반 최단 경로가중치가 있는 그래프에서 최소 거리, 최소 비용 계산 시 ✅  각 기법의 특징 비교항목완전탐색동적 계획법 (DP)다익스트라시간 효율성가장 낮음 (보통 O(2ⁿ), O(n!))중간 (O(N²) ~ O(N×M))높음 (O(E log V))공간 효율성낮거나 중간중간 (DP 테이블 필요)중간 (..

문제 풀이 설명 (summary)전체 모양을 2차 배열모양으로 변경삼각형 모양이 있는 위치를 좌표로 변환홀수, 짝수에 따라 나올 수 있는 경우의 수 구분(DP) 각 인덱스에 나올 수 있는 경우의 수를 누적 마지막 인덱스를 출력 (모든 누적 결과 합) 문제 풀이 접근법정형화된 그리드 경로 문제는 BFS보다 DP가 훨씬 효율적입니다.BFS는 주로 최단거리 혹은 가중치가 있는 경로 탐색에 적합합니다.현재 문제에서는 단순 경로 수 계산 문제이기 때문에, DP 방식이 시간적으로 훨씬 효율적인 것입니다. 풀이 코드 (Code)import java.util.Arrays;public class Main { public static void main(String[] args) { int n = 4; ..