Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처이진 검색 트리 골드 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