본문 바로가기

Java21

BOJ 20058 - 마법사 상어와 파이어 스톰(Java) https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 1. 명령의 수 만큼 반복, 명령 L에 대해 진행 1) 2L X 2L로 구역 나누기, 구역 별 회전 2) 인근 지역에 얼음이 없다면 얼음줄이기 - 동서남북 4방향에 대해 얼음이 남은 인접 칸의 개수 확인 - 인접 칸의 개수가 3이상이 아니라면 해당 칸의 얼음을 1 줄임 2. 1이 끝나면 남아있는 얼음의 합, 전체 영역 중 가장 큰 덩어리를 탐색 명령 L에 따른 구역 나누기.. 2022. 1. 8.
BOJ 16985 - Maaaaaaaaaze(Java) https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이 1. 2가지를 기준으로 모든 경우의 수를 탐색 1) 판의 회전(어느 판을 얼만큼 회전할지) 2) 회전을 완료한 5개의 판 쌓기 2. 위의 기준으로 만든 3차원 행렬을 bfs 거리 탐색 몇번째 판이 몇도 회전하는지 각 판마다 몇 도 회전하는지 모든 경우의 수를 탐색 - 현재 판을 90도 회전 시키고 다음 판에 대해 재귀 호출 5번째(마지막)판에 대한 결정이 끝나면 판을 쌓.. 2022. 1. 6.
BOJ 1202 - 보석 도둑(Java) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 완전 탐색으로 풀 경우 보석의 개수 N(1 ~ 300,000), 가방의 개수 M(0 ~ 100,000,000)으로 O(N*M)의 시간 복잡도를 가짐, 안될 거라 생각하고 풀어봤지만 역시나 시간초과 발생 * 시간 복잡도를 줄여야하며 우선순위 큐를 이용하여 품 우선 순위 큐를 이용한 풀이 - 가방에 대해서는 for문을 이용하여 탐색 -.. 2021. 12. 31.
BOJ 1715 - 카드 정렬하기(Java) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 이전의 합이 누적되는 형태 - (a + b) + (a + b + c) + (a + b + c + d) + ...... - 각 합의 작은 값이 누적되는 횟수를 크게, 큰 값이 누적되는 횟수를 작게 해야함 불가능한 방법 입력 요소의 정렬 만으로는 해결 불가능 - ex) 60, 50, 70, 80 - 요소 정렬 : 50, 60, 70, 80 - 누적 합 -> (50 + 60) + (.. 2021. 12. 27.
BOJ 4256 - 트리(Java) https://www.acmicpc.net/problem/4256 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 풀이 전위 순회 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드 중위 순회 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드 * 전위 순회의 0번째 노드는 현재 노드, 중위 순회 요소에서 현재 노드를 기준으로 왼/오른쪽 노드로 나뉨 위의 2가지 순회로 트리 구조 및 후위 순회 파악 가능 now= 0을 루트로 [0 ~ N]의 범위에 대해 탐색 1. preOrder[now] = 현재 노드 2.. 2021. 12. 23.
BOJ 23291 - 어항 정리(Java) https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net 풀이 물고기 수의 최대/최소인 어항의 차이가 K이하일 때 까지 반복 1. 물고기가 최소인 어항에 물고기 추가 - 어항에 물고기 수가 최소인 어항들에 물고기 수를 1씩 추가 2. 어항 쌓기 - 시계 방향 90도로 어항을 말아서 쌓음 - 처음에는 가장 왼쪽의 1개 항만 이동, 이후부터는 쌓여져있는 모든 어항을 이동 3. 물고기 수 조절 - 상하좌우 인접 어항을 확인, 현재 어항이 인접한 어항의 물고기.. 2021. 12. 22.
BOJ 2638 - 치즈(Java) https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 매 시간마다 외부 공기와 2변 이상 접촉하면 해당 위치의 치즈가 녹음 외부 공기 판별 가장자리에는 치즈가 없다. -> 모든 가장자리는 외부 공기 (0, 0)의 위치로 부터 시작 해서 치즈를 만나지 않는 위치로 dfs 탐색을 이용하여 외부 공기 판별 가능 private static void checkExternalAir(int i, int j) { visit[i][j] = true.. 2021. 12. 20.
ALGOSPOT - Synchronizing Clocks(JAVA) https://www.algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 www.algospot.com 풀이 스위치를 누르는 모든 경우의 수를 탐색(브루트 포스) 3, 6, 9, 12를 1, 2, 3, 0으로 변환 for (int j = 0; j < LEN; j++) { int temp = Integer.parseInt(st.nextToken()); watches[j] = (temp / 3) % 4; } 같.. 2021. 12. 16.
Programmers - 문자열 압축(Java) https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 같은 값이 연속해서 나타나는 경우 반복되는 갯수를 표기하며 줄여서 표기 ex) aaa -> 3a * 단, 정해진 길이가 반복되는 경우만 압축가능 ex) aabbb -> 2a3b(X) -> 2a2bb(O) * 완전 탐색으로 가장 작은 길이의 결과를 구하되, 탐색의 범위를 줄이는 것이 필요 주어지는 문자열의 길이를 이용하여 최대 압축 길이를 구함, 이 .. 2021. 12. 16.

티스토리툴바