Manta Ray's

https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 풀이 : 동적 계획법 Dynamic Programming ① N이 8개 이상이면 -1을 반환하도록 했으므로, N이 최대 8개일때까지만 계산을 수행 ② N을 0~x개 사용했을 때의 결과값 각각 저장함. - 1) N을 0~x개 만큼 이어붙인 자연수를 저장함. - 2) 1)에서 저장한 케이스를 조합해 사칙연산을 수행 (N*N, N/N, NN*N .... ) N3 = N1 사칙연산 N2 와 N2 사칙연산 N1, NN 사칙연산 N - 3) 2)의 결과에서 number(구하려는 값)이 나오면 연산을 중단하고 N의 갯수를 출력함. [케이스 예시] ① N..

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 : 탐욕 알고리즘 ① 구간 시작위치가 가장 먼저인 구간부터 차례로 비교하면서 카메라의 설치 구간을 탐색 ② 카메라가 설치된 구간과 route(자동차 통과구간)를 비교하면서 카메라 설치 구간을 줄여나감. ③ 겹치는 구간이 없으면 자동차 통과구간을 카메라 설치구간에 추가함. 구현 JAVA import java.util.*; public int solution(int[][] routes) { //먼저 빠져나가는 거리 순으로 정렬 Arrays.sort(routes, (..

https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 : 탐욕 알고리즘 / 프림 알고리즘 / 최소신장트리 찾기 참고 : 2021.09.20 - [알고리즘/알고리즘] - 탐욕 알고리즘 Greedy Algorithm 탐욕 알고리즘 Greedy Algorithm 탐욕 알고리즘 현재 상황에서 가장 좋아보이는 답을 선택하는 방법. 상황마다 최적을 선택하면 전체 결과값도 최적이 될것이라는 가정을 전제로 함. ① 각 단계에 도달할 때 마다, 최적의 결과 mantaray.tistory.com class Solution {..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이 : 최소값과 최대값을 동시에 찾아낼 수 있는 Collection의 TreeMap을 이용함. import java.util.*; class Solution { public int[] solution(String[] operations) { // 큐 TreeMap tm = new TreeMap(); for(int i = 0; i

https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 우선순위 힙을 이용해 풀이 참조 : https://codevang.tistory.com/316 프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA) 문제 설명 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입 codevang.tist..

https://programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr import java.util.*; class Solution { HashMap genreSum; public int[] solution(String[] genres, int[] plays) { genreSum = new HashMap(); List playList = new ArrayList(); for(int i = 0; i

문제 : https://www.acmicpc.net/problem/1927 관련 알고리즘 : 힙 정렬 2021.09.21 - [알고리즘/알고리즘] - 힙 정렬 Heap Sort 답안/풀이 JAVA ArrayList 혹은 LinkedList로 풀면 시간초과 발생 import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.ut..

힙의 형태 완전 이진 트리 : 각 노드의 자식 수가 2 이하이며, Root 노드부터 Leaf 노드까지 빠짐없이 채워져있는 트리 최대힙 Max-Heap 부모 노드 > 자식 노드 Root 노트의 값이 가장 크다. 최소힙 Min-Heap 부모 노드 < 자식 노드 Root 노드의 값이 가장 작다. 힙 배열 저장 방식 Root 노드는 배열의 첫 번째에 저장 각 노드들은 레벨 별로 저장 ▶ 부모 : 현재위치 / 2 ▶ 왼쪽 자식 : 현재위치*2 ▶ 오른쪽 자식 : 현재위치 *2+1 힙의 높이 O(logN) 힙 특성관리 Max-Heapify 노드가 입력으로 주어졌을 때 max-heap 특성이 유지되도록 바꾸는 연산 입력값이 흘러내리게 함. 시간복잡도 O(logN) 힙 구조 만들기 입력받은 트리에 Max-Heapify..

파티셔닝을 이용한 정렬방법 ① 기준값을 정한다. ② 첫번째부터 차례로 비교해나가면서 기준값보다 작으면 왼쪽 그룹의 끝자리+1과 위치를 바꾼다. 퀵 정렬의 수도코드 시간복잡도 Balanced Partitioning : 파티셔닝의 크기가 n/2로 줄어드는 경우 => 높이 logN * 각 층별 N번의 연산을 수행 => O(NlogN) UnBalanced Partitioning : 파티셔닝의 크기가 1과 n-1개로 줄어드는 경우 => 높이 N-1 * 각 층별 N-1번의 연산을 수행 => O(N²) * Unbalanced Partitioning(최악의 경우)를 피하기 위해 파티셔닝의 크기를 랜덤하게 가져가는 Randomized QuickSort가 등장함. 구현 JAVA package algorithm; impor..

탐욕 알고리즘 현재 상황에서 가장 좋아보이는 답을 선택하는 방법. 상황마다 최적을 선택하면 전체 결과값도 최적이 될것이라는 가정을 전제로 함. ① 각 단계에 도달할 때 마다, 최적의 결과를 도출한다. ② 결과를 저장한다. ③ 이미 저장한 결과는 다시 판단하지 않는다. 탐욕 알고리즘이 적용된 알고리즘들 선택정렬 Selection Sort 배낭문제 Knapsack Problem 단일 출발지 최단 경로 문제 Single-Source Shortest Path Proble, 최소 신장 트리 Minimum Spanning Tree 프림 최소 신장 트리 알고리즘 Prim's Minimum Spanning Tree Algorithm 쿠스칼 최소 신장 트리 알고리즘 Kruskal's Minimum Spanning Tre..