Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처문제집 골드 2 📖 문제 위상정렬 + 우선순위 큐 문제 먼저 푸는게 좋은 문제들은 위상정렬로 진입차수를 저장해준다. a b 로 a가 먼저 푸는게 좋은 문제면b의 진입차수 1을 늘려준다. 그리고 진입차수가 0인 문제들을 전부 우선순위 큐에 저장하고 하나씩 꺼내서 문제를 푼다. (우선순위 큐 기본 정렬을 사용했으므로 오름차순 정렬되어 난이도가 낮은 순으로 나온다.)풀고 해당 문제가 먼저 푸는게 좋은 문제였다면 연결되어있는 뒤 문제들의 진입차수를 -1 해준다. 이때 연결된 문제들의 진입차수가 0이 되었다면 더이상 먼저 푸는게 좋은 문제는 존재하지 않으므로해당 문제도 우선순위 큐에 저장한다. 🔅 문제 풀이import java.io.*;import java.util.*;import..

🧫 문제 분석✔️ 출처보석 도둑 골드 2 📖 문제 우선순위 큐 문제 주어진 가방을 무게 기준 오름차순 정렬하여 가장 작은 가방부터 보석을 담는다. 가장 작은 가방이 담을 수 있는 보석들 중 최대 값어치인 보석을 해당 가방에 담는식으로 하면 된다. 우선순위 큐를 가격이 높은순으로 사용한다.현재 선택한 가방이 담을 수 있는 보석들을 우선순위 큐에 다 담고하나를 꺼낸다. 이때 꺼낸 보석이 현재 가방이 담을 수 있는 최대 가격의 보석이 된다. 그리고 정답 범위가 30만 * 100만이기에 long타입으로 가격을 계산해야한다. 🔅 문제 풀이import java.io.*;import java.util.*;import java.util.stream.IntStream;public class Main { st..

🧫 문제 분석 ✔️ 출처이진 검색 트리 골드 4 📖 문제 노드가 최대 1만개 이며, 완전 이진 트리가 아니기 때문에 한쪽으로 치우쳐진 트리가 될 수 있다.이때 최대 인덱스는 iₙ = 2 * iₙ₋₁ + 1 점화식으로 증가하며, 1만번 반복되므로 상상을 초월하는 값이 나오기 때문에  절대로 배열로 해서는 안된다.  1~10까지를 순서대로 넣게되면1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047로 약 2^11 - 1 까지 커진걸 확인할 수 있다.  즉, 최대 1만개 노드라면 2^10000 - 1 까지 커질 수 있다. 따라서 노드 객체를 만들고 좌우에 노드를 연결하는 방식으로 접근해야한다. 자바에서는 객체의 주소 값을 복사하기 때문에 . 연산자로 접근해서 객체를 생성하여 ..

🧫 문제 분석 ✔️ 출처백준 17298번 오큰수 골드 4 📖 문제 오큰수는 현재 요소보다 크면서 가장 왼쪽에 있는 수이다.그렇다고 무작정 모두 비교하며 찾기에는 O(n^2)이 걸린다. 수열의 크기가 100만까지인 걸로 보아 1초안에는 절대로 불가능하다. 수열을 잘 생각해보자문제에서 [3, 5, 2, 7] 을 보면3은 바로 뒤 5가 있으므로 55 와 2는 7이 오큰수가 된다.  오른쪽 수가 크지 않다면 담아놓고담아놓은 수보다 큰 수가 나오면 이 수가 오큰수가 된다. 이렇게 사용할 수 있는 자료구조가 스택이다.  사실 단순한 스택문제이다.   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(..

🧫 문제 분석✔️ 출처스택 수열 실버 2 📖 문제 1~N까지의 숫자들이 오름차순으로 스택에 push될 수 있고,입력된 수열, 여기서는[4 3 6 8 7 5 2 1] 이라는 수열을 만들기 위해 스택이 해야하는 연산을 출력하는 문제이다.push : + pop : - 우선 먼저 수열의 맨 처음인 4를 놓기 위해서는 1~4까지 스택에 push 후 1번 pop한다. 그럼 스택에는 1 2 3 이 남게 된다. 그다음은 3이므로 pop 한 번 한다.다음 6이므로 5 6 을 push하고 pop 하여 6을 빼낸다. 즉 수열의 각 순서에 따른 수만큼 push하고 top의 수가 현재 순서의 수면 pop하고 아니라면 NO를 출력하고 중단한다.push는 현재 까지 넣은 수에 따라서 진행한다. 현재까지 넣은 수보다 큰 수가 오..

백준 2164번 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 풀이 카드 번호 1 2 3 ... N-2 N-1 N 특정 동작 카드가 한 장 남을때까지 반복 1) 제일 위 카드를 바닥에 드랍 2) TOP 카드를 BOTTOM 카드 밑으로 이동 각 동작 후 남은 카드 개수 확인 목표 : 제일 마지막에 남는 카드를 구하기 조건 (1