Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처장작넣기 골드 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로 잡아야 안전하다. 코드..

✔️ 문제테스트를 하는데 자꾸 이상하게 예측값보다 -1 인 값이 나와서보니 테스트 코드를 잘 못 짜서 그런 것이였다. @Transactional과 @BeforeEach를 제대로 사용하지 않았기 때문이였다. 문제의 코드 @Slf4j@SpringBootTestclass FocusTimeJdbcRepositoryTest { @Autowired FocusTimeJdbcRepository repository; @Autowired FocusTimeJpaRepository jpaRepository; @Autowired MemberRepository memberRepository; @Autowired TransactionTemplate transactionTemplate;..

🧫 문제 분석 ✔️ 출처도미노 (Small) 골드 1 📖 문제 DP 풀이 문제였는데나는 우선순위 큐로 풀었다. 각 도미노가 넘어뜨릴 수 있는 최대개수를 구하고우선순위 큐에 넣은 다음 가장 많이 쓰러뜨린 도미노 먼저 꺼낸후해당 도미노를 넘어뜨렸을 때 넘어진 도미노들을 방문체크한다.이를 반복하면 된다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static class Domino { int x, h; long left, right; public Domino(int x, int h) { this.x = x; this.h = h; ..

🧫 문제 분석 ✔️ 출처화살표 미로 (Easy) 골드 3 📖 문제 BFS 탐색 문제나는 끝지점에서 상하좌우의 방을 탐색후 현재 방을 가리키는지 체크하고현재 방을 가리키지 않았다면 주문서를 써서 방향을 바꾸고 바꾼 방향으로 현재 방을 가리킬 수 있는지 확인후 이동하는 식으로 구현하였다. 🔅 문제 풀이import java.io.*;import java.sql.SQLOutput;import java.util.*;public class Main { static int R, C, K; static char[][] map; static boolean[][][] visited; static int[] dr = {-1, 0, 1, 0}; static int[] dc = {0, 1..

🧫 문제 분석 ✔️ 출처내일 할거 골드 5 📖 문제 문제를 제대로 안읽어서 한 번 틀렸다.내일 부터 연속으로 최대로 놀 수 있는 기간을 출력하는 건데최대 놀 수 있는 기간을 출력해버렸다... 과제 마감 시간을 기준으로 내림차순 정렬하여과제 시작일을 구하고이전 과제 시작일과 비교해서 현재 과제 시작일을 배치한다. 다 구한 후 마지막으로 구한 이전 과제 시작일 - 1 이 내일부터 놀 수 있는 기간이다. 🔅 문제 풀이// 코드 내용import java.io.*;import java.util.*;public class Main { // 계산은 long static class Assigment implements Comparable { int d, t; public Ass..