본문 바로가기
반응형

알고리즘 PS113

[백준] 16954번 - 움직이는 미로 탈출 (Java)(○) https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 1. 체스판의 크기는 8 x 8이다. 모든 판은 빈 칸(.)과 벽(#)으로 되어 있다. 2. 가장 왼쪽 아래 칸에서 가장 오른쪽 윗 칸으로 이동해야 한다. 3. 1초마다 모든 벽이 아래에 있는 행으로 한칸씩 이동한다. 만약 가장 아래 였으면 벽이 사라진다. 4. 캐릭터는 인접한 한 칸 또는 대각선으로 이동하거나, 현재 위치에 서 있을 수 있다. 5. 1초 동안 캐릭터가 먼저 이동하고, .. 2023. 3. 13.
[백준] 7576번 - 토마토 (Java)(○) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 토마토를 보관하는 창고(N * M)이 있다. 칸 마다 토마토를 보관한다. 토마토는 익은 것과 덜 익은 것들이 섞여 있다. 보관 후 하루가 지나면 잘 익은 토마토의 상/하/좌/우에 있는 토마토들도 익게 된다. 토마토가 혼자서 익는 경우는 없고 반드시 영향을 받아서 익는다. 창고의 토마토들이 모두 익게 되는 최소 일수를 구하라. 상자의 일부 칸에 토마토가 없는 경우도 있다. 상하좌우로.. 2023. 3. 2.
알고리즘 풀이용 코드 스니펫(Java) 1. 회의들(시작시간, 종료시간)을 종료시간을 기준으로 오름차순 정렬하려면 static ArrayList A; class Meeting implements Comparable { int s, e; Meeting (int s, int e) { this.s = s; this.e = e; } @Override public int compareTo(Meeting o) { if (this.e == o.e) { // 종료시간이 같은 회의라면 return this.s - o.s; // 시작시간 작은 회의가 앞쪽에 위치 } else { return this.e - o.e; // 종료시간이 작은 회의가 앞쪽에 위치 } } } Collections.sort(A); 2023. 2. 23.
백트래킹 vs DFS 알고리즘 문제를 풀다보면 DFS인 것 같은데 백트래킹으로 분류된 문제들이 있다. 헷갈린 부분이 있어서 이번 기회에 확실히 정리를 하고 넘어가고자 한다. * DFS (깊이 우선 탐색) 가능한 모든 경로를 다 탐색한다. 따라서, 불필요한 경로도 무조건 끝까지 탐색을 하기 때문에 경우의 수를 줄이지는 못한다. * 백트래킹 (Back-tracking) 답을 찾아가는 도중, 지금의 경로가 답이 될 것 같지 않으면 더이상 진행하지 않고 윗단계로 되돌아간다. 이를 가지치기라고 하는데, 불필요한 경우의 수를 줄일 수 있으므로 시간복잡도를 개선할 수 있다. 문제풀이에서는 DFS로 모든 경우의 수를 완전탐색하는 과정 중에 조건문을 걸어서 답이 절대로 나올 수 없는 상황을 정의하고, 해당이 되면 탐색 중단 후 그 이전으로 .. 2023. 2. 19.
코딩테스트 입력값 받기 (1) 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100) 둘째 줄부터 N개 줄에는 그림이 주어진다. 5 RRRBB GGBBB BBBRR BBRRR RRRRR void inputData() throws Exception { InputStreamReader reader = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(reader); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); map = new char[N][N]; for (int i=0; i 2023. 2. 18.
[백준] 13023번 - ABCDE (Java)(△) https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 인접리스트 방식으로 입력값을 저장한다. 2. 중복값을 값을 허용하지 않기 때문에 방문배열을 사용한다. 3. 친구관계는 A-B, B-C, C-D, D-E로 4개로 고정이 되어 있다. 따라서 호출 level이 5가 되면 친구관계를 다 찾은 것이다. 5. level == 5이면 더 이상 다른 친구관계를 찾을 필요없이(가지치기) 1을 출력하고 종료하면 된다. 6. 그래프의 시간복잡도 O(V + E)이므로 2,000 + 2,000 = 4,000, 모든 노드에 대한 탐색은 4,000 * 2,000 = 8,0.. 2023. 1. 26.
[백준] 2023번 - 신기한 소수 (Java)(△) https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 1. 신기한 소수란? 왼쪽부터 1자리, 2자리.... N자리까지 모두 소수인 수 예) 7331 : 7 - 73 - 733 - 7331 모두 소수이다. 2. N자리가 주어졌을 때 신기한 소수를 모두 찾아서 출력하자. 3. 입력범위가 N : 1 ~ 8이다. DFS 백트래킹으로 풀이가 가능하다. * 재귀함수 구현 1. 중복숫자 허용함(방문배열 사용X) 2. 순서다르면 다른 조합으로 인정 (i.. 2023. 1. 26.
[백준] 1377번 - 버블 소트 (Java)(△) https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 더보기 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.util.Arrays; import java.util.PriorityQueue; import java.lang.Comparable; public class Main { s.. 2023. 1. 4.
[백준] 11286번 - 절댓값 힙 (Java)(◎) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1. 입력값이 실시간으로 오른차순 정렬이 되어 있어야 한다. 2. 입력값이 양수와 정수가 번갈아 존재하고, 절대값 기준으로 정렬이 되어야 한다. 3. 절대값이 같을 경우 부호를 붙였을 때 작은 수가 앞쪽에 와야 한다. 4. PriorityQueue를 사용해서 실시간 정렬을 해보자. 5. class Node를 구성해서 num은 원래 값, abs는 절대값을 저장한다. class .. 2023. 1. 3.
반응형

티스토리툴바