java
-
[백준]17289. 오큰수 - Java알고리즘/백준 2021. 2. 19. 01:17
📄 링크 boj 17298. 오큰수 💡 문제 분석 N * N으로 모든 경우를 비교하면 시간 초과가 납니다 O(N) 방법 순서대로 스택에 숫자를 넣을 때, 스택에 숫자가 들어있다면 현재 넣을 숫자와 비교해 봅니다 만약 현재 넣을 숫자가 더 크다면, 스택에 있는 숫자들의 오큰수는 현재 넣을 숫자가 됩니다 마지막 숫자까지 스택에 넣었다면 모든 오큰수를 구한 것이 됩니다. ⌨️ 코드 public class _17298_오큰수 { static class Pair { int idx, n; Pair(int idx, int n) { this.idx = idx; this.n = n; } } public static void main(String[] args) throws IOException { BufferedReade..
-
[백준]16639. 괄호 추가하기 3알고리즘/백준 2021. 1. 10. 23:58
[백준]16639. 괄호 추가하기 3 📄 링크 괄호 추가하기 3 💡 문제 분석 수식을 입력받고 여기에 괄호를 임의로 추가하여 최대값을 구하는 문제입니다 이 문제의 핵심은 괄호를 마음대로 넣을 수 있기 때문에 연산자의 우선순위는 아무런 의미가 없다는 것입니다. 그렇기 때문에 괄호를 넣을 수 있는 모든 방법으로 완전 탐색을 진행하고 캐시에 저장해서 해결하였습니다 하지만 이 문제에서 *연산을 할 때 음수 * 음수를 했을 때 가장 큰 수가 나올 수 있기 때문에 가장 작은 값들도 계속 저장을 하고 있어야합니다. Calc(max, max) Calc(max, min) Calc(min, max) Calc(min, min) 4가지 계산을 모두 해서 가장 큰 수는 max 캐시에, 가장 작은 수는 min 캐시에 저장합니다 ..
-
[백준]1918. 후위 표기식알고리즘/백준 2021. 1. 8. 23:16
[백준]1918. 후위 표기식 📄 링크 후위 표기식 💡 문제 분석 중위 표기식을 입력으로 받아 후위 표기식으로 출력하는 문제입니다. 후위 표기식은 괄호가 필요 없기 때문에 입력으로 받아도 출력하지 않습니다. 보통 이런 수식 문제들은 스택을 이용하는 경우가 많은 것 같습니다. ArrayDeque을 이용해서 풀어보았습니다. ‘(‘ 열린 괄호가 나온다면 스택에 푸시합니다 ‘)’ 닫힌 괄호가 나온다면 열린 괄호가 나올 때까지 출력합니다. A ~ Z 그대로 출력합니다 Operator 자신보다 우선순위가 낮은 연산자가 나올 때까지 스택에서 뽑아서 출력합니다 우선순위를 리턴하는 함수를 만들었습니다. 마지막엔 스택이 빌때까지 뽑아서 출력합니다. ⌨️ 코드 import java.util.ArrayDeque; import..
-
[백준]1629. 곱셈알고리즘/백준 2021. 1. 8. 23:00
[백준]1629. 곱셈 📄 링크 곱셈 💡 문제 분석 자연수 A, B, C를 입력 받아 A를 B번 곱한 것을 C로 나눈 나머지를 구하는 문제입니다. 시간 제한이 0.5초이고 B가 21억까지 나올 수 있기 때문에 단순히 21억번을 곱하는 문제는 아닐 거라고 생각했습니다. 분할 정복을 사용해서 홀수일 때와 짝수일 때를 나누어 답을 구해나갔습니다. 절반으로 나눈 값을 곱해줄 때 java의 Math.pow 메서드를 사용했었는데 double 타입을 반환하여 오버플로우가 발생하여 실패했습니다. 오버플로우 방지를 위해 왠만하면 모든 계산에 % C를 해주자 ⌨️ 코드 import java.util.Scanner; public class Boj1629_tk { public static void main(String[] a..
-
[백준]1916. 최소비용 구하기알고리즘/백준 2021. 1. 7. 00:04
📄 링크 최소비용 구하기 💡 문제 분석 출발 지점과 도착지점이 제시되어 있고 간선에 가중치가 붙어 있기 때문에 다익스트라 혹은 벨만-포드로 풀 수 있다고 생각했습니다. 음의 가중치가 없어서 굳이 벨만-포드는 쓰지 않고 다익스트라를 사용했습니다 우선순위큐 정렬을 할 때 comparable을 쓸 때와 comparator 혹은 lambda 할수를 쓸 때 메모리와 시간이 많이 차이가 나는 것을 알게 되었습니다. 여유가 되는 문제들은 lambda를 사용하고 시간이 빠듯하면 comparable을 사용하는 것이 좋을 것 같습니다. ⌨️ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..
-
[백준]10021. Watering the Fields알고리즘/백준 2021. 1. 5. 01:22
📄 링크 Watering the Fields 💡 문제 분석 최대 2000개의 정점을 가진 그래프의 MST를 구하는 문제입니다 정점들 사이의 거리를 구하고 입력에 주어진 C값으로 간선의 수를 제한하고 있지만, 상당히 많은 간선이 생길 것 같아 프림 알고리즘을 사용하기로 했습니다. 프림 알고리즘 모든 정점들에 굉장히 큰 값을 주고 시작합니다 임의로 시작 정점을 골라 연결되어 있는 정점들의 가중치를 갱신합니다 정점들 중 가장 가중치가 작은 정점을 골라 이를 반복합니다.(우선순위 큐를 사용할 수도 있습니다) 모든 정점을 갱신했다면 종료 → 이 문제에서는 그래프가 연결되어 있지 않은 경우가 존재하기 때문에 모든 정점을 검사하여 한 번도 갱신되지 않은 정점이 있다면 분리되어 있다고 판단하여 -1을 출력하도록 하였습..
-
[백준]20530. 양분알고리즘/백준 2021. 1. 5. 01:01
📄 링크 양분 💡 문제 분석 이런 문제가 왜 골드2인지 모를 정도로 힘든 문제였습니다. 처음엔 아무 생각 없이 dfs로 모든 경로를 다 찾아보려 했지만 정점이 200000개.. 당연히 시간초과가 떴습니다 이 문제의 핵심은 간선의 개수가 정점의 개수와 같기 때문에 반드시 하나의 사이클이 존재한다는 것입니다. 예제 입력을 그래프로 그려보았습니다. 어떤 두 정점으로 가는 단순 경로는 사이클이 하나이기 때문에 2개 또는 1개 밖에 나올 수 없습니다 2가지가 나오는 경우 두 정점이 모두 사이클에 속해 있는 경우 양 방향으로 갈 수 있기 때문에 2가지 경로가 존재합니다 LCA(최소 공통 조상)이 다른 경우 사이클을 구성하고 있는 정점들을 루트로 아래쪽 부분을 서브트리라고 생각했을 때 다른 루트에서 뻗어나왔다면 사이..
-
[백준]1904. 01타일알고리즘/백준 2021. 1. 5. 00:58
📄 링크 01타일 💡 문제 분석 입력 N이 100만으로 꽤 큰 숫자입니다. 기존 숫자에서 00을 더할지 1을 더할지를 선택하는 방법으로 메모이제이션을 사용했었는데 재귀로 문제를 풀면 스택 오버 플로가 발생하였습니다. 어쩔 수 없이 반복적 dp를 사용하였습니다. 덧셈을 할 때 계속 15746으로 나누어 주지 않으면 오버플로가 발생하게 됩니다 ⌨️ 코드 import java.util.Scanner; public class _1904_01타일 { static int[] cache = new int[1000001]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); cache[1] =..