본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[boj] 백준 20056 마법사 상어와 파이어볼 (Java) - 시뮬레이션 [문제] https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net [풀이] 1. 파이어볼이 d 방향으로 s만큼 이동한다. 2. 같은 칸에 2개 이상의 파이어볼이 있다면 합쳐진 후 4개로 나눠진다. 3. 이렇게 k번 이동한다. 처음에는 파이어볼을 이동시키기 위해서 board[][] 배열에 파이어볼을 저장한 후 add와 remove를 사용했으나 이 경우 remove 때문에 인덱스가 변경되어 배열 접근 시 오류가 쉽게 ..
[boj] 백준 골드4 7662 이중 우선순위 큐 (Java) - TreeMap [문제] https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net [풀이] 이전 프로그래머스 풀이대로 minHeap과 maxHeap 두개를 이용해 구현하면 시간초과가 발생한다. 시간초과가 발생하는 이유는 다른 우선순위큐의 원소를 제거하기 위해 remove()를 사용할 경우 O(N)이 소요되기 때문이다. 따라서 우선순위큐가 아닌 TreeMap을 이용해서 원하는 원소를 바로 찾아 제거할 수 있도록 하였다. [코드] package heap_stack_de..
[boj] 백준 골드4 14500 테트로미노 (Java) - DFS [문제] https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net [풀이] 이전에 풀었던 코드. 이전에는 ㅏ, ㅓ, ㅜ, ㅗ 모양에 대해 하드코딩을 했었다. 그러나 하드코딩을 하지 않아도 2칸이 선택되었을 때, 3번째 칸에 대해서는 방문 표시만 해두고 다시 원래의 좌표인 r, c에서 dfs 탐색을 진행하면 위의 4가지 모양에 대해서도 테트로미노의 합을 구할 수 있다. [코드] package bfs_dfs; import java.util.*; import..
[boj] 백준 2636 치즈 (Java) - BFS [문제] https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net [풀이] 1. 가장자리의 치즈만 녹아 없어지고 내부에 공간이 있는 경우 영향을 주지 않는다. 따라서 치즈가 없다고 명시된 (0,0)부터 탐색을 진행하면 가장자리의 치즈만 녹일 수 있다. 2. 치즈가 없으면 큐에 넣고 계속 탐색을 진행하고, 치즈가 있으면 치즈를 녹인 후 탐색을 멈춘다. 한번 BFS가 호출될때마다 가장자리의 치즈가 모두 녹을 것이므로 t를 증가시킨다. 3. 탐색이 끝나고 남은 치즈의..
[boj] 백준 1043 거짓말 (Java) - 유니온 파인드 [문제] https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net [풀이] 진실을 아는 사람과 같이 파티에 참석했던 사람들은 진실을 알게 된다. 1. 같이 파티에 참석한 사람들이 같은 parent를 갖도록 union 해준다. 2. 진실을 아는 사람의 최종 parent는 같은 파티에 참석했으므로 진실을 알게된다. knowTruth에 체크해준다. 3. 파티 참석자 중 누군가의 최종 parent가 진실을 알고 있다면 그 파티에서는 거짓말을 할 수 없다. [코드] pac..
[boj] 백준 12852 1로 만들기 2 (Java) - dp [문제] https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net [풀이] 3으로 나눌 수 있는 경우, 2로 나눌 수 있는 경우, 1을 뺄 수 있는 경우에 대해서 dp[i]는 i를 1로 만들 수 있는 연산의 최솟값을 저장해준다. 정답 출력 시 과정도 함께 출력해야 하기 때문에 trace[i]에 이전 값을 저장해둔다. [코드] package dp; import java.util.*; import java.io.*; public class boj_12852_java { static int n; static int[] dp; static int[] trace; p..
[boj] 백준 1654 랜선 자르기 (Java) - 이분탐색 [문제] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [풀이] 기본 이분탐색 문제이다. 다만 주의해야 할 점은 랜선의 최대 길이가 2^31-1 이기 때문에 low, mid, high 값을 long으로 선언해주어 오버플로우가 발생하지 않게 해야 한다. [코드] package 이분탐색; import java.util.*; import java.io.*; public class boj_1654_java { //k개의 ..
[boj] 백준 19236 청소년 상어 (Java) - DFS, 시뮬레이션 [문제] https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net [풀이] 상어는 같은 방향으로 최대 *3만큼 이동할 수 있으며 이 모든 이동경로에 따라 상어가 먹을 수 있는 물고기 번호의 합이 달라질 수 있으므로 dfs를 통해 탐색해야 한다. 1. 상어가 이동하여 물고기를 잡아 먹는다. 상어는 잡아먹은 물고기의 방향을 갖게 된다. 2. 물고기를 이동시킨다. 1~16번까지 차례로 이동하며 물고기가 이동 가능하다면 위치를 바꿔준다. 불가..

티스토리툴바