응파카 성장일지

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 연산의 개수 n을 입력받는다. 이후 n 만큼의 반복을 실행하는 for 반복문을 만든다. 2. 입력값에 따라 출력 후 값 삭제 or 값 list 에 추가 -> 를 실행한다. 2-1. 0을 입력 받았을 경우 : list 에서 절댓값이 가장 작은 값을 출력한다. 2-1-1. 절댓값이 가장 작은 값이 여러 개일 경우 : 가장 작은 수를 출력한다. - 이를 구현하기 위해 Prio..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net Java 의 PriorityQueue 는 기본적으로 최소 힙을 사용한다. PriorityQueue 의 메서드들을 사용할 줄 알면 쉽게 풀 수 있는 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue;..

https://www.acmicpc.net/problem/1464 1464번: 뒤집기 3 세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 www.acmicpc.net 문자열을 입력받고 앞부터 .reverse() 가 가능하다. Brute Force 방식도 있지만 Greedy 방식 활용이 더 낫다. 1. 문자열 input 을 입력받고 앞부터 천천히 뒤집는다. 2. 뒤집을 때마다 check 메서드를 실행해 새로 생성한 문자열을 기존 제일 사전순 앞이던 문자열 answer 와 비교한다. 3. 비교해서 더 앞에 있으면 answer 를 업데이트하고, 더 뒤에 있으면 파기한다. ..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 골드 치고는 너무 쉬운 문제가 아닌가 싶었는데, 다음 문장이 눈에 들어왔다. [전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.] 정답률이 굉장히 낮다고 생각했는데, 분명 시간초과가 뜬 것이 분명했다. 알파벳 R과 D에 해당하는 연산을 수행해주는 것 이상으로 더 생각을 해 봐야 했다. - R을 할 때마다 뒤집는 것 -> 시간초과의 원인들 중 하나 - 따라서 R이 들어왔을 경우 뒤집는 대신 boolean 값 isRevers..

import java.util.Arrays; import java.util.Scanner; public class Main { //냅색 알고리즘 static int n, m; static int[] coins; //동전 종류 목록 static int[] dynamic; //최소 동전 개수 public int solution() { dynamic[0] = 0; for(int i=0; i

import java.util.Scanner; public class Main06 { //냅색 알고리즘 public static void main(String[] args) { Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int m = kb.nextInt(); int[] dynamic = new int[m+1]; for(int i=0; i=time; j--) { //앞에서부터 돌면 중복 //뒤에서부터 돌아야 중복 회피 dynamic[j] = Math.max(dynamic[j], dynamic[j-time]+score); } } System.out.println(dynamic[m]); } }

import java.util.Arrays; import java.util.Scanner; public class Main { public int count(int[] arr, int capacity) { int cnt = 1; int sum = 0; for(int x : arr) { if(sum+x > capacity) { cnt++; sum = x; } else { sum += x; } } return cnt; } public int solution(int n, int cd, int[] arr) { int ans = 0; int lt = Arrays.stream(arr).max().getAsInt(); int rt = Arrays.stream(arr).sum(); while(lt

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net Deque 자료구조를 이용하면 풀기 수월하다. 연산 횟수를 세는 경우는 오른쪽으로 한 칸씩 미는 경우와 왼쪽으로 한 칸씩 미는 경우 두 가지이다. 한 칸씩 이동하는 이유는 Deque의 첫 번째 값을 뽑아내는 1번 연산을 하기 위함이다. 찾고자 하는 숫자의 처음 Deque에서의 위치가 주어지면 두 가지 경우로 나뉜다. 오른쪽으로 한 칸씩 밀어가며 숫자를 첫 번째 값으로 위치시킬 것인지 왼쪽으로 ..

BFS import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Node{ int x; int y; public Node(int x, int y) { this.x = x; this.y = y; } } public class Main { static int answer = 0, n; static int[] dx = {1, 1, 1, -1, -1, -1, 0, 0}; static int[] dy = {1, 0, -1, 1, 0, -1, 1, -1}; static int[][] board; static Queue queue = new LinkedList(); public void BFS(int x, int y) { ..

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Tomato{ int x, y; public Tomato(int x, int y) { this.x = x; this.y = y; } } public class Main { static int[][] box; static int[][] day; static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, -1}; static int n, m; static Queue queue = new LinkedList(); public void BFS() { while(!queue.isEmpty()) { Tomato to..