알고리즘/백준

문제 출처 : https://www.acmicpc.net/problem/24479 소요 시간 : 시도(30m) + 풀이 문제 시도 오랜만에 '데이터 구조' 전공 수업에서 듣던 알고리즘을 접했다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int N, M, R; private static int[] visited; private static int[][] E; public static void main(String[] args) throws IOException ..

문제 출처: https://www.acmicpc.net/problem/1520 소요 시간 : 시도(30m) + 풀이(???) 문제 시도 처음엔 단순하게 시작점(0, 0)에서 종착점(N, M)으로 갈 수 있는 경우의 수만 따지면 되겠지 생각하고 가볍게 여겼는데, 2가지에서 난항을 겪었다. 첫째는 기존 수보다 낮은 값을 지닌 칸으로만 이동할 수 있다는 점, 그리고 둘째는 이동이 좌 → 우, 상 → 하 뿐만 아니라 조건만 만족한다면 우 → 좌 로의 이동까지 가능해야 한다는 점이다. 문제에선 예시를 매우 순탄한 걸로 줘서 괜찮을 수도 있지만 극단적으로 다음과 같이 지도가 주어진다면 어떻게 대처해야 할지 고민했다. 3 2 1 1 2 3 2 1 2 3 2 2 1 1 1 이런 극단적인 지도가 주어진다면 어떻게 처리해..

문제 출처: https://www.acmicpc.net/problem/11049 문제 시도 손도 못 대고 무력하게 다른 사람의 풀이를 참고했다.... 풀이 이번 문제를 풀 때 가장 고민했던 점은 아래 코드의 `matrix[start][0] * matrix[divide][1] * matrix[end][1]` 부분이었다. 문제에 대한 이해가 부족했던 점도 있었지만 결국 고려해야 했던 점은 start부터 end 까지의 곱셈 연산 횟수였었다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { publi..

문제 출처: https://www.acmicpc.net/problem/17299 문제 시도 이전에 풀어봤던 오큰수 로직을 약간 수정하여 시도해봤다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; // N 입력 받기 fin..

문제 출처 : https://www.acmicpc.net/problem/17298 소요시간 (문제 파악 10분 + 풀이 20분) 문제 시도 문제의 카테고리가 스택이 아니었다면 꽤 골머리를 안고 포기했을 문제였다. LIFO을 고려하여 수열을 먼저 입력받고, 뒤에서부터 요소를 꺼내면서 우측 값 중 자신보다 큰 값을 찾아 비교하였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; // A size : 1 ~ 1,000,000 // A elem : 1 ~ 1,000,000 public class Main { public static ..

문제 출처: https://www.acmicpc.net/problem/9935 문제 시도 일단 무난하게 contains()로 확인하고 replace로 대체하는 식으로 작성했다. import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = br.readLine(); String expl = br.readLine(); while (str.contains(expl)) { str = str.replace(expl, ""); } System.out..

문제 출처: https://www.acmicpc.net/problem/11286 문제 시도 일단 나름대로 Heap을 작성해봤는데 절댓값 비교 부분으로 인해 실패한다. 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.readLine()); AbsoluteHeap ah =..

문제 출처: https://www.acmicpc.net/problem/11279 문제 시도 처음엔 문제 카테고리를 신경 쓰지 않고 내가 생각해본 LinkedList를 통해 풀어보기로 했다. LinkedList 삽입, 삭제가 자유롭고, 조회에 대한 시간 복잡도가 O(n)이라는 단점이 있지만 문제는 가장 큰 요소, 즉 첫 번째 요소를 출력할 걸 요구하기 때문에 문제가 없을 거라고 여겼다. import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; public class Main { public static void main(String[] args) ..

문제 출처: https://www.acmicpc.net/problem/2565 문제 시도 문제 등급이 실버이든 골드이든 동적 계획법 문제는 점화식과 메모이제이션에 대한 감이 안 잡혀서 항상 난처함만 더해갔다. 풀이 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.Arrays; import java.util.Comparator; public class Main { static Integer[] dp; static int[][] wire; public static void main(String[] ar..

문제 출처: https://www.acmicpc.net/problem/11053 문제 시도 배열의 첫 번째 요소부터 마지막 요소까지 각각 자기 위치에서 마지막까지 찾아가는 방법을 생각했으나 일단 이중 반복문으로 시간 복잡도가 O(n^2)여서 절대 좋은 결과는 안 나올거라고 생각해 동적 계획법에 관한 블로그부터 다시 찾아봤다. 풀이 import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static int[] arr; // 원 배열 private static int[] lis; // LI..