zun

다이나믹 프로그래밍은 시간 단축을 위한 알고리즘이다. 탑다운 방식과 바텀업 방식이 존재하며, 결국 핵심은 계산한 값을 저장하고 재활용한다는 것이다.동적 계획법(DP)를 구현해 보자. 탑다운: 메모이제이션  이름에서 알 수 있듯 큰 문제부터 작은 문제로 해결하는 방식이다. ✅ 재귀구조가 직관적이고 구현이 간단하다. ✅ 재귀호출이 깊어질수록 스택 오버플로우 가능성이 있다.public class Fibonacci { static int[] dp; public static int fibonacci(int n) { if (n 바텀업: 터뷸레이션  이름에서 알 수 있듯 작은 문제부터 큰 문제로 해결하는 방식이다. ✅ 스택 오버플로우 위험이 없으며 모든 값에 쉽게 접근할 수 있다.✅ 반복문을 ..

인사말  모두들 안녕하신가요.  저는 어느덧 알고리즘을 건든 지 140일 지났답니다. 기쁜 소식이 있어 전해드리자면, 최근에 BFS 문제들을 풀며 골드 구간에 진입했어요. 목표는 골랜디 마스터고요. 이번에 문제를 풀며 스스로 아쉬웠던 부분들이 있어서 지금의 생각과 감정을 기록하려고 글을 적습니다.BFS인데 그래프가 2개?package bfs;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Problem10026 { static final int[] dx = {0, 0, -1,..

문제수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.이해하기좌표 압축을 적용한 값 X'i가  Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같다. 중복되는 원소가 같은 순위를 가진다는 점이 마치 SQL Server에서의 DENSE_RANK 느낌인데, 이 문제에서 추가로 고려할 점은 값이 작을수록 순위가 높다는 것과 가장 높은 순위는 0순위라는 점이다. 중복되는 원소를 같은 순위로 둔다는 점을 고려할 때, 일단 Set이나 Map을 활용..

문제정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다.push X: 정수 X를 큐에 넣는 연산이다.pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 큐에 들어있는 정수의 개수를 출력한다.empty: 큐가 비어있으면 1, 아니면 0을 출력한다.front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. BOJ에서 제공하는 큐 문제다. LinkedList와 ArrayDeque 모두 큐 자료구조를 구현할 ..

BufferedReader를 쓰면서 문자열을 숫자 값으로 전환하는 일이 많았다. 그래서 Integer.parseInt()가 자연히 몸에 배어있었는데, 이게 특정 진법으로 해석해 숫자 값을 뱉는 친구라는 건 오늘에서야 알았다. (지능 이슈) 변명이지만 지금까지 진법 자체를 다룰 일이 딱히 없었기도 하고, 아무튼 단순히 Int로 파싱 하는 거라 생각했는데, 아래와 같이 기수를 입력하면 해당 진법으로 해석해 값을 뱉어낸다.Integer.parseInt(Stirng, base)// 2진법Integer.parseInt("1010", 2); // -> 10 반환// 8진법Integer.parseInt("12", 8); // -> 10 반환// 16진법Integer.parseInt("A", 16); // -> 10 ..

요즘 변수명을 의미 있게 작성하려고 노력하는 중이다. 물론 알고리즘을 풀 때는 편의상 내가 알 수 있을 정도로만 작명한다. 동시에 메서드는 최대한 빼서 구현하는 편인데, 특별한 이유는 없고 메서드를 만드는 것에 익숙해지고 싶어서다.창문 닫기 문제는 9단계에 위치했지만 앞선 단계들보다 쉽다. 그래서 크게 생각할 점 없이 코드를 짤 수 있었다.// https://www.acmicpc.net/problem/13909import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Problem13909 { public static void main(String[] args) throws ..

들어가기에 앞서  이진 탐색이나 이분 탐색이나 영어로는 Binary Search로 같은 말이다.  결국 데이터를 반으로 나누어가며 목푯값을 찾는 알고리즘이다. 여기서 말하는 데이터는 정렬된 배열을 말한다.  정렬된 배열로 진행해야 하는 이유는 이진 탐색 원리에 있다.  우선 시작점과 끝점을 가지고 중간점을 만든다. 중간값을 기준으로 원하는 값과 비교하여 탐색할 구간을 좁혀나간다. 원하는 값이 중간값보다 작으면 왼쪽 절반을 탐색하고, 더 크면 오른쪽 절반을 탐색한다.  위 작업을 반복하다가 원하는 값을 찾거나 구간이 사라지면 종료한다. 이진 탐색을 왜 사용할까?  배열을 처음부터 끝까지 차례대로 탐색하는 방법을 선형 탐색이라고 한다. 배열의 길이가 N이라고 할 때, 최악의 경우 시간복잡도는 O(N)이다. ..

// https://www.acmicpc.net/problem/11866import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Problem11866 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); Queue q = new LinkedList(); for (int i = 1; i 1) { for (int i = 1; i "); }}▶ 문제..

소수 검증static boolean isPrimeNumber(int n) { if (n ▶ 특정 숫자가 소수인지를 판단할 때, 우리는 해당 숫자의 제곱근까지만 약수 여부를 검증하면 된다. 그런데 만약, 범위 내의 소수를 모두 알고 싶다면 어떻게 해야 할까?범위 내 소수 검증public static void main(String[] args) { Scanner sc = new Scanner(System.in); int start = sc.nextInt(); int end = sc.nextInt(); for (int i = start; i ▶ 앞서 제시한 메서드를 사용하면, 당연히 반복문을 통해 범위 내 소수를 나열할 수 있다. 하지만 입력된 범위가 커지면 커질수록 더 많은..

2차원 배열import java.util.*;public class Problem10814 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); String[][] infos = new String[N][2]; for (int i = 0; i () { public int compare(String[] o1, String[] o2) { return Integer.parseInt(o1[0]) - Integer.parseInt(o2[0]); } });..

import java.io.*;import java.util.Arrays;import java.util.StringTokenizer;public class Problem11650 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[][] coordinates = new int[N][2]; // [x, y] N개 StringTokenizer st; for (int i = ..

브루트 포스import java.io.*;import java.util.StringTokenizer;public class Problem2609 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int num1 = Integer.parseInt(st.nextToken()); int num2 = Integer.parseInt(st.nextToken()); ..

import java.io.*;import java.math.BigInteger;public class Problem15829 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int l = Integer.parseInt(br.readLine()); // 문자열 길이 String w = br.readLine(); // 문자열 BigInteger r = new BigInteger("31"); // r 고정 BigInteger sum = BigInte..

백준 2750번은 배열을 오름차순으로 정렬하면 되는 문제이다. Arrays.sort() 메서드로 쉽게 풀 수 있는 문제지만, 공부 목적으로 해당 메서드를 사용하지 않고 풀어보도록 하겠다.내 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.r..

반복문에 이름을 붙이다니, 왜?  ...라고 생각했다면 아래 코드를 보자. 다음은 백준 2839번 '설탕 배달'에 대한 나의 첫 번째 코드다.  문제 상황 속, 설탕 배달에 쓰일 봉투는 5kg짜리와 3kg짜리가 있다. 배달해야 할 설탕의 무게 N이 주어질 때, 설탕 봉투 수를 최소로 하는 경우를 찾아내 총 봉투 수를 출력해야 하는 문제이다.import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int temp = 0; for (int i = 0; i..