알고리즘/백준
-
[백준]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 캐시에 저장합니다 ..
-
[백준]18500. 미네랄2알고리즘/백준 2021. 1. 10. 23:57
[백준]18500. 미네랄2 📄 링크 미네랄2 💡 문제 분석 이 문제를 풀기 위해 필요한 과정 막대를 던져 미네랄을 파괴했을 때 공중에 떠 있는 클러스터를 찾기 공중에 떠 있는 클러스터를 적절히 밑으로 내리기 1번 해결 바닥에 있는 미네랄들을 bfs해서 모두 방문 처리를 해줍니다 방문 처리가 되지 않은 미네랄들이 있다면 이는 공중에 떠있다는 것을 알 수 있습니다 2번 해결 공중에 떠 있는 클러스터를 ‘.’로 바꿔놓고 밑으로 내릴 수 있는 최대값을 구합니다 왼쪽, 오른쪽 번갈아 가며 막대를 던지기 때문에 불린을 바꿔가며 처리했습니다 막대를 던진 높이에 미네랄이 없을 때 예외처리를 하지 않아 많은 시행착오를 했습니다. 문제를 풀면서 미네랄을 파괴했을 때 2개 이상의 클러스터가 동시에 떨어지는 경우가 없다는 ..
-
[백준]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..
-
[백준]1504. 특정한 최단경로알고리즘/백준 2021. 1. 8. 01:43
[백준]1504. 특정한 최단 경로 📄 링크 특정한 최단 경로 💡 문제 분석 1번 정점에서 N번 정점까지 이동할 때, 주어진 두 정점을 반드시 경유해서 이동하는 최단 경로를 구하는 문제입니다. a와 b를 경유해서 N으로 가는 최단 거리를 구하기 위해서는 1 → a → b → n으로 가는 경로와 1 → b → a → a로 가는 경로를 비교해서 최소값을 구해야합니다. 1번 정점과 A, B에서 각각 다익스트라 알고리즘을 사용하여 다른 점으로 가는 최단 거리를 구하여 계산하였습니다. 최단 거리를 구했을 때 아주 큰 값이 나온다면 경로가 존재하지 않는다고 판단하여 -1을 출력하였습니다. ⌨️ 코드 import java.io.BufferedReader; import java.io.IOException; import..
-
[백준]11657. 타임머신알고리즘/백준 2021. 1. 7. 00:26
📄 링크 타임머신 💡 문제 분석 음의 가중치를 가질 수 있는 최소 비용 문제입니다. 음의 가중치를 가지고 있는지 판단할 수 있는 벨만-포드 알고리즘을 사용 해야겠다고 생각했습니다. V - 1번을 완화작업을 하면 모든 정점의 최소 비용을 알 수 있습니다. 그리고 V번째 완화 작업을 했을 때 실패하지 않고 성공한다면 음수 간선이 존재하는 것입니다. 문제를 풀면서 계속 출력초과 에러가 발생해서 계속 고민을 하다가 아주 큰 음수 가중치를 계속 더하면 언더플로우가 발생할 수 있다는 것을 깨달았습니다. 그래서 upper 배열 값을 long 타입으로 바꿨더니 해결이 되었습니다. ⌨️ 코드 import java.util.ArrayList; import java.util.Arrays; import java.util.Sc..
-
[백준]1238. 파티알고리즘/백준 2021. 1. 7. 00:16
📄 링크 파티 💡 문제 분석 N개의 정점, M개의 간선을 가진 그래프입니다. 무향 그래프였다면 도착지인 X가 정해져 있어서 한 번의 다익스트라로 가능했을 것 같은데 방향 그래프였기 때문에 플로이드-와샬을 쓰기로 했습니다. N이 1000이기 때문에 플로이드-와샬의 시간 복잡도 O(N^3)이므로 빠듯해보였습니다. 그래서 플로이드-와샬에서 i에서 k로 가는 정점이 없다면 건너 뛰는 가지치기를 적용했습니다. ⌨️ 코드 import java.util.Arrays; import java.util.Scanner; public class _1238_파티 { static int N, M, X; static int[][] adj; public static void main(String[] args) { // 입력 Scan..
-
[백준]1916. 최소비용 구하기알고리즘/백준 2021. 1. 7. 00:04
📄 링크 최소비용 구하기 💡 문제 분석 출발 지점과 도착지점이 제시되어 있고 간선에 가중치가 붙어 있기 때문에 다익스트라 혹은 벨만-포드로 풀 수 있다고 생각했습니다. 음의 가중치가 없어서 굳이 벨만-포드는 쓰지 않고 다익스트라를 사용했습니다 우선순위큐 정렬을 할 때 comparable을 쓸 때와 comparator 혹은 lambda 할수를 쓸 때 메모리와 시간이 많이 차이가 나는 것을 알게 되었습니다. 여유가 되는 문제들은 lambda를 사용하고 시간이 빠듯하면 comparable을 사용하는 것이 좋을 것 같습니다. ⌨️ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import..