Meluu_의 코딩 공부 일지

백준 20058번 : 마법사 상어와 파이어스톰 [자바]

🧫 문제 분석 ✔️ 출처마법사 상어와 파이어스톰 골드 3 📖 문제 모든 칸을 격자로 나누고 90도 회전 후 인접한 얼음이 있는 칸이 3개 미만이면 얼음의 양이 - 1로 줄어든다 (이는 동시다발로 일어난다.) 격자 나누는걸 좀 복잡하게 구현했더니 좀 느리긴한데(700ms) 회전하는 로직만 바꾸면 충분히 빠르게 될거라고 생각된다. 찾아보니 2차원 배열 회전 공식이 있어 공부했다.참조: https://taaewoo.tistory.com/10🔅 문제 풀이import java.beans.Customizer;import java.io.*;import java.util.*;public class Main { static int N, Q, size; static int[][] map; stat..

백준 20056번 : 마법사 상어와 파이어볼 [자바]

🧫 문제 분석 ✔️ 출처마법사 상어와 파이어볼 골드 4 📖 문제 뭔가 생각보다 어려웠다. 항상 짜잘한거에서 틀려서 그렇지 전체적인 로직은 잘 짰다. 어려웠던것중첩 파이어볼을 어떻게 저장해놓을까 -> List[][] 로 처리하면 시간복잡도는 괜찮은가, K만큼 재생성해야함 -> O(K)중첩 파이어볼은 어떻게 처리할까-> 위에 저장한 파이어볼 식별값을 사용해 한번에 더한 다음 연산후 처리 소멸조건에서if (sumM/5 == 0)을 비교해야하는데 sumM을 비교해서 틀렸다. 이것만 빼면 다른 로직은 다 정상작동했다. 🔅 문제 풀이import java.beans.Customizer;import java.io.*;import java.util.*;public class Main { static int ..

🧫 문제 분석 ✔️ 출처모노미노도미노 2 골드 2 📖 문제 게임 개발하는 거 같아 좀 재밌었다. 빨간 칸에 입력으로 주어지는 좌표와 도형 형태를오른쪽, 아래로 2개의 도형이 내려가는 형태의 테트리스 같은 게임이다. boolean 2차원 타입으로 현재 테트리스 상태를 저장한 라인이 전부 도형 즉, 가득 찬 상태는& 연산자를 통해서 확인 연한 색의 부분은 라인 개수를 세고 그 개수만큼 띄어서 옮기기 🔅 문제 풀이import java.io.*;import java.util.*;import java.util.stream.IntStream;public class Main { // 20061번 모노미노도미노 2 // 블록은 한번 보드 위에 놓이면 다른 블록과 합쳐지지 않음 // 1. 점수를..

🧫 문제 분석 ✔️ 출처원판 돌리기 골드 2 📖 문제 문제가 이해가 되는듯 안되는 문제였다. 진행 프로세스인데2번줄부터 이해가 안간다. 인접하면서 수가 같은 것을 모두 찾는다 -> 돌려진 상태에서 모든 원판의 인접하면서 수가 같은 것을 모두 찾는다.그러한 수가 있는 경우 -> 인접하면서 수가 같은 게 1개라도 있는 경우없는 경우 -> 인접하면서 수가 같은게 1개도 없는 경우원판에 적힌 수의 평균 -> 모든 원판에 적힌 수의 평균 평균보다 큰 수에서 -1, 작은거에서 +1문제에서는 당연히 소수점을 버린다는 말이 없었는데 내 멋대로 소수점을 버려서 예제 마지막이 실패했다.평균을 소수점을 포함해서 비교해야한다. 🔅 문제 풀이import java.io.*;import java.util.*;public..

🧫 문제 분석 ✔️ 출처드래곤 커브 골드 3 📖 문제 재밌는 문제였다. 끝지점을 기준으로 회전시켜서 선분을 복사 핵심 끝지점 기준 회전 방법기존 세대 드래곤 커브 복사 풀이기존 드래곤 세대의 끝지점부터 시작지점 순으로 탐색하면서각 지점에 들어오는 방향을 기준으로 회전시킨다음 현재 위치에서 해당 방향으로 1칸씩 전진하면서 해결하였다.이동한 방향를 다시 현재 위치로 갱신하면서 진행한다. 자료구조현 세대의 시작부터 끝지점까지의 방향정보를 담는 Deque새로운 세대의 드래곤 커브를 임시 저장할 Queue 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 15684번 사다리 조작 static int N; stat..

🧫 문제 분석 ✔️ 출처사다리 조작 골드 3 📖 문제 i번째 사다리로 시작해서 i번째 사다리로 끝나도록 가로선을 최소한으로 추가하는 문제다. 가로선은 최대 3개까지 추가할 수 있고불가능하거나 3개를 넘어가면 -1로 반환한다. 1. 현 상태 사다리 시뮬레이션 구현2. 가로선을 추가시 인접한 사다리의 가로선과 맞닿는지 확인 그리고 처음에 풀이시 2200ms가 나왔다.그저 낮은 깊이부터 탐색하면 되는데 굳이 처음부터 3까지 탐색해서 시간이 이렇게 나왔다. 깊이 1일떄 조합깊이 2일때 조합깊이 3일때 조합 순으로 탐색하면 깊이가 낮을때 먼저 답 발견시 빠르게 끝날 수 있다. 🔅 문제 풀이import java.io.*;import java.util.*;import java.util.jar.JarEn..

🧫 문제 분석 ✔️ 출처감시 골드 3 📖 문제 완전탐색 + 구현 + 백트래킹 문제 핵심CCTV 감시 모든 경우의 수 탐색 (이미 감시한 곳은 넘어가고, CCTV를 넘어설 수 있음)CCTV 방향에 대한 탐색을 구현하는 방법 풀며서 실수한게항상 그렇듯, 변수 새로 생성하고 이전 변수를 안고쳐서변수에 값을 -1 빼서 사용한다 해놓고 정작 리턴하는 곳에서는 -1을 안해서 틀림. 로직을 짜고 좀 더 세심히 머리로 시뮬레이션을 그리며 코드를 점검해볼 필요가 있다.🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 15683번 감시 static int[] dr = {-1, 0, 1, 0}; static int[] dc = {0..

🧫 문제 분석 ✔️ 출처톱니바퀴 골드 5 📖 문제 전체적인 로직이해는 잘 했는데실시간 톱니가 회전된 상태에서 N, S를 비교하는게 아니라회전하기전 상태에서 비교하는건데 이걸 캐치하지 못했다. 또한 변동idx값을 따로 저장하는데-의 경우 8보다 커지면 + 8을 해줘도 인덱스가 -로 Array Index Out Of Bounds Exceptions가 터졌다. 음수로 변동값을 주었을때 그 값이 배열의 크기를 넘어버리면 안된다.따라서 해당 변동값 자체도 나눠버리면 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 14891번 톱니바퀴 // 시계방향 -1 // 반시계방향 +1 public static void ..

🧫 문제 분석 ✔️ 출처경사로 골드 3 📖 문제 구현 문제 높이 차가 1인 각 칸의 연결을 어떻게 해결하는가가 관건한쪽 방향이 아닌 양쪽에서 높이차를 두었을때 어떻게 해결할 것인가단, 높이가 1을 초과한다면 지나갈 수 없다. 행은 행끼리열은 열끼리 문제를 나눠 풀되 로직은 같다. 행을 기준으로A행이라고 가정하고 A 행의 0열을 이전값으로 삶고A행의 1열과 비교해서 같다면 같은 수를 센다. 현재보다 높이가 높은 다음 칸을 만날경우여태 센 같은 수의 개수가 경사로의 설치 기준 개수를 넘어선다면 높이가 높은 칸을 자연스럽게 지나가면 된다. 반대로 현재보다 높이가 낮은 다음 칸을 만날 경우다음칸부터 다음칸의 같은 높이를 가지는 연속된 칸들의 개수를 센다.그 수가 경사로 설치 기준 개수를 넘어선다면경사..

🧫 문제 분석 ✔️ 출처로봇 청소 골드 5 📖 문제 구현문제 BFS를 활용하여 풀었다. 문제가 좀 이해가 안될 수 있는데 현재 칸이 아직 청소되지 않은 경우 청소현재 칸의 주변 4칸 모두 청소되었다면바라보는 방향 유지한 채 한칸 후진 가능시 후진후진한 곳이 벽이면 작동 종료 (청소끝)현재 칸의 주변 4칸중 하나라도 청소안되어있다면반시계 방향 90도 회전회전 후 바라보는 앞쪽칸이 청소되지 않았다면 한칸 전진 후 1번으로 아니라면 다시 90도 회전이렇게 나뉜다.이것만 잘 이해하면 아주 쉽게 풀 수 있는 문제였다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 14503번 로봇 청소기 static int N, M; /..