Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처톱니바퀴 골드 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; /..

🧫 문제 분석 ✔️ 출처의좋은 형제 골드 5 📖 문제 현재 까지의 볏단 합의 최대, 최소를 구한다. 두 형제의 최대, 최소 합을 비교해서 현재 볏단 개수를 합하여현재까지의 볏단 합 최대 최소를 구한다. 마지막 N번째에는 무조건 대각 방향으로만 최대 최소를 구하고 N번째 두 형제의 최대 최소를 구한다음차를 구하면 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 32406번 의좋은 형제 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(S..

🧫 문제 분석 ✔️ 출처장작넣기 골드 5 📖 문제 완전탐색 문제 문제를 이해하는데 조금 어려웠다.처음 위치한 SKH의 위치에 대해서는 장작을 넣지 않는다.그 다음 부터 넣는다. 화력감소때 넣은 장작의 위치는 감소시키지 않는 형태로 진행한다. 장작은 왼쪽, 현재, 오른쪽으로 3가지를 탐색한다. 시간복잡도가 약 O(3^T * N) 정도 나오는 것 같다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { // 24884번 장작 넣기 // T시간동안 최소 K개 유지 static class Node { int SKH; int[] arr; int time; public Nod..

🧫 문제 분석 ✔️ 출처레이스 골드 2 📖 문제 이분탐색 + 그리디문제 이분탐색의 대상은 두 심판의 거리다.M명 배치할 수 있는 심판의 거리를 구해서 심판을 배치하고 그 중에서 가장 가까운 거리가 가장 긴 심판 배치를 출력한다. 그런데 가장 긴 심판 배치는 심판 거리계산하면서 자동으로 마지막에 계산된 것이 가장 긴 거리가 된다. (더 긴 거리를 탐색해보기 때문) 비슷한 문제로 예전에 풀었던 공유기 설치 문제랑 비슷하다. 나의 경우심판 배치 거리 탐색 - 이분탐색적절한 심판 배치 위치 탐색 - 이분탐색 3중 while문으로 풀어서 좀 보기 안좋을 수 있다.심판 위치 배치는 for문으로 해도 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class ..

🧫 문제 분석 ✔️ 출처엘리베이터 플래티넘 5 📖 문제 최단경로 + BFS + 역추적 문제 이문제를 풀면서 메모리초과가 진짜 자꾸 나서 정말 힘들었다. 여러번의 테스트 끝에 알아낸 것은컬렉션에서for (int i : list)향상된 for문(for-each)는 내부적으로 Iterator 객체를 생성해서 순회한다.때문에 수많은 엘리베이터를 갖는 리스트를 foreach로 접근했으니메모리초과될 수밖에 없었다. 많은 양의 요소를 담는 컬렉션 객체는 되도록이면 for-each문을 사용하지 말아야겠다. 그리고 거리는 dist배열로 따로 빼자.괜히 큐에 같이넣어서 메모리초과뜬다. 🔅 문제 풀이 [다익스트라]import java.io.*;import java.util.*;public class Main { ..

🧫 문제 분석 ✔️ 출처사수빈탕 골드 5 📖 문제 DP문제로 주어진 사탕 바구니 위치로 이동하며 최대 개수를 구하는 문제 한 번 움질일때마다 사탕바구니의 사탕이 -1이 된다. 사탕 바구니를 x,y로 오름차순 정렬해서 DP + DFS 탐색한다. 다른 사람풀이를 보니 bottom-up 으로 푸는 방법도 있다.🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int n, m; static int[][] arr; static int[][] dp; public static void main(String[] args) throws IOException { BufferedReader br = new..

Dockerfile직접 이미지를 생성할 수 있게 해주는 파일 명령어FROM [이미지명]:[태그명]COPY [호스트 컴퓨터에 있는 복사할 파일의 경로] [컨테이너 파일 위치 경로]ENTRYPOINT [명령문1, 명령문2, 명령문..]RUN [명령문]WORKDIR [작업 디렉토리로 사용할 절대 경로]EXPOSE [포트번호] FROM : 베이스 이미지 생성한다. 베이스 이미지 : 초기 기본 세팅, 쉽게 말해서 기본 프로그램 느낌이다.JAVA에 한해서는 JDK가 베이스이미지가 되겠다. COPY : 호스트 파일에 있는 파일을 컨테이너에 복사 ENTRYPOINT : 컨테이너 생성시 최초 실행때 수행하는 명령어 RUN : 이미지 생성과정에서 명령어를 실행시켜야 할 때 사용ex) npm install, apt upda..

배열의 연속된 구간의 합을 O(Log N)시간만에 할 수 있는 자료구조합 뿐만 아니라 구간 최대 최소, 곱 등도 구할 수 있다. 세그먼트 트리는 보통 3가지로 구성된다init : 세그먼트 트리 초기화query : 원하는 구간의 값을 구함update : 배열에서 요소 a를 변경했을 때 값을 갱신함 트리 크기세그먼트 트리도 결국 이진 트리 기반이기에 가질 수 있는 노드는2^h 개가 된다. h = ceil(log2(n)) , n = 배열의 요소 개수 treeSize = 2^h 높이를 올리는 이유n = 9 일때 log2(9) = 3.xx 로 나온다.그렇다고 높이를 3으로 해버리면2^3 이 되어 트리 크기가 8이 되고 9를 넣을 공간이 없어진다. 그래서 높이를 올림(ceil)해서 4로 잡아야 안전하다. 코드..