_

Always be tactful

개인 학습/알고리즘 18

[Java] 알고리즘 설계 기법: 최적화 문제를 위한 DP

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

[Java] 그래프 탐색 알고리즘: DFS, BFS

인사말  모두들 안녕하신가요.  저는 어느덧 알고리즘을 건든 지 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,..

[Java] BOJ 18870: 좌표 압축과 랭킹 알고리즘

문제수직선 위에 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을 활용..

[Java] BOJ 18258: LinkedList vs ArrayDeque

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

[Java] BOJ 1550: Integer.parseInt()

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

[Java] BOJ 13909: 창문 닫기와 힙 메모리 한도

요즘 변수명을 의미 있게 작성하려고 노력하는 중이다. 물론 알고리즘을 풀 때는 편의상 내가 알 수 있을 정도로만 작명한다. 동시에 메서드는 최대한 빼서 구현하는 편인데, 특별한 이유는 없고 메서드를 만드는 것에 익숙해지고 싶어서다.창문 닫기 문제는 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 ..

[Java] BOJ 11723: 비트마스크 (BitMask)

들어가기에 앞서  비트마스크란 컴퓨터의 비트를 이용해, 이진 데이터로 상태를 저장하고 처리하는 기법이다. 작은 메모리 공간으로 다양한 연산을 수행할 수 있기에 효율적인 알고리즘을 설계할 수 있다. 주로 플래그 설정, 집합의 요소 추적, 특정 비트에 대한 연산 등에 사용된다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.StringTokenizer;public class Problem11723 { public static void main(String[] args) throws IOException { ..

[Java] BOJ 1654: 이진 탐색, 이분 탐색 (Binary Search)

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

[Java] BOJ 4134: 에라토스테네스의 체

소수 검증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 ▶ 앞서 제시한 메서드를 사용하면, 당연히 반복문을 통해 범위 내 소수를 나열할 수 있다. 하지만 입력된 범위가 커지면 커질수록 더 많은..

[Java] BOJ 2750: 오름차순 정렬하기, 거품 정렬

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

[Java] BOJ 2839: 반복문에 이름 붙이기, 레이블

반복문에 이름을 붙이다니, 왜?  ...라고 생각했다면 아래 코드를 보자. 다음은 백준 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..