Manta Ray's

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

기본타입 Primitive Type byte, char, short, int, long, float, double, boolean 실제 값을 변수 안에 저장한다. 참조타입 Reference Type 배열타입, 열거타입, 클래스, 인터페이스, Integer 메모리에는 실제값의 주소(번지)가 저장되고, 실제 값은 힙 영역에 저장된다. 2021.10.02 - [JAVA/JAVA] - JVM 자바 가상머신 기본타입 종류 정수형 [byte] 색상 정보 및 파일 또는 이진(바이너리) 데이터를 처리할 때 주로 사용됨. 정수 타입 중 가장 작은 범위의 값을 표현함. 저장되는 값의 범위 : -27 ~ 27 메모리 사용 크기 : 1 byte ( 8 bit ) [char] 글자 1개, 유니코드 1개를 저장하기 위한 데이터 ..

개념 NaN : Not a Number, 숫자가 아닌 값 Infinity : 무한대 System.out.println( 5 % 0.0); System.out.println( 5 / 0.0); NaN Infinity 실제 연산 시 ArithmeticException이 발생함. System.out.println( Integer.valueOf(5%0) ); System.out.println( Integer.valueOf(5/0) ); Exception in thread "main" java.lang.ArithmeticException: / by zero 특징 /, % 연산의 우측 연산자가 0일때 나타남. 이 값들에 추가 연산을 해도 NaN 또는 Infinity가 그대로 출력됨. 처리방법 해당 값이 NaN이나 ..

문제 : 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..

에러 메시지 No enclosing instance of type Class is accessible. Must qualify the allocation with an enclosing instance of type Class (e.g. x.new A() where x is an instance of Class). 원인 static void main 메소드에서 최상위 클래스 선언 없이 내부 public 클래스 생성자를 호출했을 때 발생함. public class Sample { public static void main(String[] args) { A sampleA = new A(); } class A { int a; A(){ this.a = 0; } A(int a){ this.a = a; } publ..

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

플로이드-와샬 알고리즘 모든 정점 사이의 최단 거리를 찾는 알고리즘. 그래프를 인접행렬로 표현한다. 정점마다 경로 가중치를 기록한 인접행렬을 탐색하여 최단경로를 찾는 방식이다. 슈도코드 ① 인접행렬 A 생성 ② for ( k to 정점갯수) { for ( i to 정점갯수) { for ( j to 정점갯수) { //현재 경로 값과 정점 K를 거쳐가는 경로 값을 비교하여 더 작은 값을 저장 if (A ( i , j ) > A ( i , k ) + A( k , j ) ) { A ( i , j ) = A ( i , k ) + A( k , j ); } } } } 시간복잡도 ① 정점 K를 거쳐가는 경로를 탐색 ② ①을 수행할 때마다 경로 가중치를 기록한 인접행렬 V²을 탐색 O(V³) 구현 JAVA package..

벨만-포드 알고리즘 음수 가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘. 벨만-포드 알고리즘에서 최단 경로는 출발점으로부터 도달가능하며 음의 값을 가지는 순환이 없는 경우를 의미함. 그래프에 있는 모든 정점을 한번씩 탐색함. 슈도코드 BELLMANFORD(그래프, 가중치, 시작점) 시작점 초기화 최단경로의 비용을 MAX으로 초기화 ① 모든 경우의 수 for ( 그래프의 모든 정점을 탐색) { for ( 그래프의 모든 엣지를 탐색){ if( U를 거쳐서 V로 가는 비용 < 현재 V의 최단 비용 ){ V로 가는 비용