일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- 알고리즘
- 카카오코딩테스트
- 공부정리
- 자료구조힙
- 객체프로그래밍
- 코테준비
- 카카오기출
- 문자열포맷
- 카카오코테
- 자바문자열
- heap정렬
- 자료구조 트리
- 백준 1000번 java
- java method
- 백준 1000번
- 백준 1924번 java
- 프로그래머스
- Java heap
- heap
- java
- 프렌즈4블록java
- 프렌즈4블록
- 백준 1924번
- 코딩테스트기출
- 카카오1차
- 힙정렬자바
- 백준
- 개발상식
- 객체프로그래밍이란
- 자바
- Today
- Total
목록2019/09 (20)
일단 시작해보는 블로그
전형적인 dp문제 중, 최댓값(Math.max) 구하는 것. bottom-up, 저장해놓은 것보다 큰 값이면 ok아니면 새로 계산한 값 넣기의 종류 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 상담 가능 일자 int[] T = new int[N+10]; // 상담을 완료하는데 걸리는 일자 int[] P = new int[N+10]; // 상담을 했을 때 받을 수 있는 돈 int[] dp = new int[N+10];// dp memoization을 위한 배열 //1부터 N까지 입력받는다..
처음에 그냥 리스트에 넣고 정렬을 해줘서인지,,,,,, 시간초과가 났었던 문제. 정렬 시, 아주 빠른 속도를 보이는 우선순위큐를 이용해야했다. 시간복잡도 : O(logN) import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 보석 개수 int K = sc.nextInt(); // 1개의 보석만을 담을 수 있는 가방 Node[] jewelry = new Node[N]; // 보석의 정보를 담고 있는 Node 배열 int[] max = new int[K]; // 보석관련 정보를 N만큼 입력받는다. for(int..
순열이란? 수학적으로는 완전순열이라고 하는데, 쉽게 말해서 모든 원소의 위치를 바꿔서 주어진 수 배열을 나열할 수 있는 경우의 수를 모두 표현한 것이다. 예를들어, {1, 2, 3} 이라면 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}가 해당된다. 순열의 구현 첫번째로 생각해봐야하는 것은 해당 순열의 다음순열 구하기이다. 그래야 loop문으로 모든 순열을 구현할 수 있기 때문! [순열의 다음순열 구하기] {1 2 3 4 5 6 7}로 이루어진 순열을 사전순으로 나열했을 때, 마지막에 올 수 있는 것은 {7 6 5 4 3 2 1}일 것이다. 앞의 자리가 3이면서 마지막에 올 수 있는 것은 ? {3 7 6 5 4 2 1} 앞의 자리가 4 ..
부분집합이란? 예를 들어, 집합 A = {a, b, c, d}가 있다고 하면, A의 부분집합인 B는 {}, {a}, {b}, ... {a,b}, ... {a, b, c}, ... {a,b,c,d}, 16(2^4)가지수로 표현될 수 있다. 비트마스크 연산을 이용한 부분집합의 프로그램으로의 구현 부분집합은 집합에서 각각 원소가 있다(1) 혹은 없다(0)의 경우의 수로 볼 수 있는데, 이러한 경우로 보면 '비트마스크 연산'을 이용해 표현할 수 있다. 구현과정을 두가지로 나눌 수 있다. 1. 부분집합을 이진수로 표현하기 2. 각각 이진수를 부분집합으로 변환해서 출력하기. (1이면 해당 원소 출력, 0이면 continue;) 1. 각 원소를 이진수로 표현 다음은 집합 A = {a, b, c, d}의 부분집합을 이..
이진 검색 트리 (Binary Search Tree) 임의의 이진검색트리의 노드 N은 다음 조건을 만족한다. - 노드 N의 왼쪽 서브 트리의 모든 키 값은 N보다 작다. - 노드 N의 오른쪽 서브 트리의 모든 키 값은 N보다 작다. - 같은 키 값을 갖는 노드는 없다. 이때, 이진검색트리를 중위순회(Inorder)하면 다음과 같이 키 값의 오름차순으로 노드를 얻을 수 있다. 1 - 4 - 5 - 6 - 7 - 9 - 11 - 12 - 13 - 14 - 15 - 18 이렇게 중위 순회를 하면 키 값을 오름차순으로 노드를 얻을 수 있다는 점과 구조가 단순하다는 점, 이진 검색과 비슷한 방식으로 검색이 가능하다는 점, 노드의 삽입이 쉽다는 점 등의 특징이 있어 폭넓게 사용된다. 이진검색트리 구현 package..
문제 요약 숫자(0-9), '+', '-' 버튼으로 이루어진 리모컨으로 원하는 채널로 이동 하고 싶다. 단, 숫자 누르는 버튼(0-9) 중, 고장난 버튼이 주어진다. input 값 : N, M, 고장난 숫자 버튼 output 값 : 버튼(숫자, +, - 버튼)을 총 몇번 눌러야하는지. 100번 -> N 현재 채널 : 100번 이동하려고 하는 채널 : N 고장난 숫자 버튼의 수 : M 고장난 숫자 버튼 : B1, B2, .... , Bn (M개) 해결 전략 1. 고장나지 않은 버튼을 이용해 숫자로 이동할 수 있는 채널(c)을 구한다. c를 구하면 길이를 반환하면 된다 -> 'len' -> 0-500000까지 for-loop로 하나씩 맞는지 확인한다. 2. 이동할 채널(C)와 원래 이동하려고 했던 채널(n)..
요약 Comparable : 기본적인 정렬 기준으로 정렬. default = 오름차순이지만 내림차순도 있으며, 사전순으로 숫자크기순 등등이 이에 해당된다. @Override compareTo(Object o) -> this, o 비교 -> 오름차순이면 뒤에있는 o가 더 커야하므로 this > o 일 때 맞는거니까 양수 return! Comparator : 기본적인 정렬 기준 이외의 기준으로 정렬하고자 할 때 사용. 그러니까 사전순이 아닌, 여러 조건이 있을 경우라던지, 문자열의 길이 순, 객체내에 접근해서 값을 비교해야한다던지 등등 일 때 사용한다. @Override compare(Object o1, Object o2) -> o1, o2비교 -> 오름차순이면 뒤에있는 o2가 더 커야하므로 o1 < o2 ..
Set Interface 1. 데이터 중복 No! 데이터를 중복해서 저장할 수 없다. 2. 저장 순서가 보장되지 않음. index로 관리하는 것이 아니기 때문 . 3. Iterator의 객체(반복자)를 통해 반복문을 돌릴 수 있다. 이것도 인덱스로 관리하는 것이 아니기 때문. 대표적으로 HashSet, TreeSet, LinkedHashSet 등이 있다. HashSet 전형적인 Set 인터페이스의 특성을 갖추고 있다. 데이터 중복x, 입력한 순서대로 저장되지 않는다. package hash; import java.util.HashSet; import java.util.Set; // HashSet은 순서가 따로 없고 중복되지 않는다. if 중복 -> false를 반환한다. public class HashS..