일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
31 |
- java
- 공부정리
- 카카오코딩테스트
- 문자열포맷
- 힙정렬자바
- 카카오코테
- 자바문자열
- 카카오기출
- heap
- 백준 1000번 java
- 백준 1924번
- heap정렬
- 코딩테스트기출
- java method
- Java heap
- 코테준비
- 알고리즘
- 백준 1000번
- 프렌즈4블록java
- 자료구조힙
- 프로그래머스
- 개발상식
- 객체프로그래밍
- 프렌즈4블록
- 자바
- 백준
- 자료구조 트리
- 카카오1차
- 객체프로그래밍이란
- 백준 1924번 java
- Today
- Total
목록CS/알고리즘 풀이 (49)
일단 시작해보는 블로그
DP가 아닌 Greedy를 떠올려야 하는 이유 Ai는 Ai-1의 배수이므로, 모든 경우의 수를 전부 다 해보는 dp로 한다면, 비효율적이다. 따라서 그리디로 구현해야한다. 코드 package greedy; import java.util.Scanner; // 문제 : 동전 0 // 예제1 : 동전 10(N)종류로 4200(K)원을 만들 때, 동전개수의 최솟값구하기 public class backjoon_11047 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 1. 입력 int N = sc.nextInt(); // N : 동전종류의 수 int K = sc.nextInt(); // K : 동전의 합 //동전의..
** dp문제라고 판단했을 때, 가장 먼저 해야하는 것 : 메모이제이션을 위한 배열 d 정의하기. ** d[i] 정의 i계단까지 왔을 때 문제에 만족하는 조건에 만족하며, 얻을 수 있는 최대 점수. 문제에 만족하는 조건 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 한 계단 전에서 왔다면 그 이전에는 두 계단 이전에서 왔어야한다. 마지막 도착 계단은 반드시 밟아야 한다. -> d[N]을 구하면 된다. 경우의 수 생각해보기 i의 입장에서 생각해 봤을 때 다음과 같다. 1. i-1을 밟고 온 경우 d[i] = d[i-3] + ..
스티커는 2행 n열로 주어진다. 하나를 떼면 왼쪽, 오른쪽, 위, 아래를 연속으로 뗄 수 없다. 따라서 왼쪽부터 오른쪽으로 스티커를 뗄 수 있으면서 그 값이 최댓값인 것을 경우의 수 중에서 고를 것이다. 생각 각각 열마다 3가지 경우의 수를 둘 것이기 때문에 이렇게 할당했다. int[][] d = new int[n+1][3]; d[i][0] = i열에서 하나도 안뗐을 때, 그전부터 이 상황((k=1; k '그 전부터 이 상황까지'의 부분이 dp가 적용되어야할 부분. d[i][1] = i열에서 위에꺼만 뗐을 때, 그전부터 이 상황까지 더한 값. d[i][2] = i열에서 아래꺼만 뗐을 때, 그전부터 이 상황까지 더한 값. -> 결국 마지막 열에서 d[n][0], d[n][1], d[n][2]의 최댓값을 구..
전형적인 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..
문제 요약 숫자(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)..
프로그래머스용 코드 import java.util.*; class Solution { static class Node{ int index; double value; Node(int index, double value){ this.index = index; this.value = value; } int printIndex(){ return this.index; } double printValue(){ return this.value; } } public int[] solution(int N, int[] stages) { int[] answer = new int[N]; int[] challenge = new int[N+1]; int[] numOfFailure = new int[N+1]; for(int i=0..
하,......................... 진짜 겨우풀었다. 아니 너무 복잡했어 ㅠㅠ 눈물나ㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏㅏ흑흑흑.............................................. 운동이나하러가야지.............................................. 프로그래머스용 코드 import java.util.*; class Solution { static int[] crewTimeTable = null; static int[] busTimeTable = null; //stringToMinute()는 역할이 비슷하므로, overloading 해줬음. //String으로 된 크루들의 도착 시간표를 분으로 나타낸 int[] crewTimeTable..