응파카 성장일지

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. 갖고있는 카드의 개수 N 을 입력받는다. 2. N개 만큼 숫자를 입력받는다. 3. 정수 M을 입력받는다. 4. 숫자 M개를 입력받는다. N 개의 배열을 돌면서 내부적으로 M 번의 탐색을 하는 것은 O(N^2)라는 엄청난 시간복잡도가 나오기에 HashMap 를 사용하여 쉽게 풀 수 있다. import java.io.BufferedReader; import ja..

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]); } }

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..

https://programmers-story.tistory.com/10 [백준 알고리즘] 메모리 초과 발생 이유 및 해결 방안 문제를 푸시다보면 다양한 에러를 만나실텐데요. 오늘은 백준알고리즘 1697번을 풀면서 발생한 메모리 초과에 대해서 글을 써보려고 합니다. 메모리 초과가 발생하는 이유를 간단히 말씀드리자 programmers-story.tistory.com 단순한 탐색 문제로 생각하고 인접행렬을 사용해 다음과 같이 풀었더니 메모리 초과가 나왔다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; import java.util.StringT..

import java.util.Scanner; import java.util.Stack; public class Main { public int solution(String str) { int ans = 0; Stack stk = new Stack(); for(int i = 0; i < str.length(); i++) { char temp = str.charAt(i); if(temp == ')'){ if(str.charAt(i-1) == '(') { stk.pop(); ans += stk.size(); } else if(str.charAt(i-1) == ')') { ans++; stk.pop(); } } else if(temp == '(') stk.push(temp); } return ans; } pu..

import java.util.Scanner; import java.util.Stack; public class Main { public int solution(int l, int n, int[][] board, int[] moves) { int ans = 0; Stack stk = new Stack(); for(int x : moves) { for(int i = 0; i < l; i++) { if(board[i][x-1] != 0) { int temp = board[i][x-1]; board[i][x-1] = 0; if(stk.isEmpty()) { stk.push(temp); } else if(!stk.isEmpty() && stk.peek()==temp) { stk.pop(); ans += 2; }..