개발 무지렁이

막대기 🪅 가장 늦게 들어온 데이터부터 검사하는 데이터의 흐름을 보고 스택을 생각해낼 수 있느냐 🪅 조건을 만족하는 데이터가 나왔을 때, 기준을 변경해야하는 것을 잊지 않았느냐 🪅 스택 관련 라이브러리를 사용할 줄 아느냐 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; /** * 백준 17608번 막대기 * * 입력: * 첫 번째 줄에는 막대기의 개수를 나타내는 정수 N (2 ≤ N ≤ 100,000)이 주어지고 이어지는 N줄 각각에는 막대기의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다. * * 출력: * 오른쪽에서 N개의..

요세푸스 문제 🪅 일부가 순환되는 것을 보며 큐(queue)를 생각할 수 있느냐 🪅 큐를 구현할 수 있느냐 💡 문제 접근 과정 : k번째가 되어 제거되기 전까지는 첫번째 ~ k-1번째까지는 순서가 뒤로 밀린다. 즉, 첫번째부터 k-1번째까지 빼서 뒤로 넣으면 되고, 빼는 출구와 넣는 입구가 다르므로 큐를 생각해냈다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; /* * 백준 1158번 요세푸스 문제 * * 입력: * 첫째 줄에 N과..

구간 합 구하기 5 🪅 이차원배열에서의 누적합을 구할 수 있느냐 🪅 누적합 배열을 만들 때, 패딩을 넣을 생각을 했느냐 🪅 답을 구하는 규칙을 만들 수 있느냐 => int res = accTable[x2][y2] - accTable[x2][y1-1] - accTable[x1-1][y2] + accTable[x1-1][y1-1]; 💡 문제 접근 과정 : 누적합을 이용해서 구간합을 구할 때는, 큰누적합- 작은누적합을 생각해야하고 항상 누적합의 시작점은 같아야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Str..

구간합 구하기4 🪅 구간합을 구할때 누적합 - 누적합을 생각해낼 수 있느냐 🪅 누적합 배열을 만들때 index 0에 패딩까지 만들었느냐 => arr[i] + accSum[i-1]; [시간초과난 코드.java] public class Main { /** * 백준11659 구간합구하기4 * 입력: * 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. * 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. * 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. * * 출력: * 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. * @throws IOException */ public static void main(Str..

개수세기 🪅 Scanner를 사용할 수 있느냐 🪅 입력받은 데이터들의 개수만큼 배열에 저장할 수 있느냐 import java.util.Scanner; public class B10807_개수세기 { /** * 백준10807 개수세기 * 입력: * 첫째 줄에 정수의 개수 N(1 ≤ N ≤ 100)이 주어진다. * 둘째 줄에는 정수가 공백으로 구분되어져있다. * 셋째 줄에는 찾으려고 하는 정수 v가 주어진다. * 입력으로 주어지는 정수와 v는 -100보다 크거나 같으며, 100보다 작거나 같다. * * 출력: * 첫째 줄에 입력으로 주어진 N개의 정수 중에 v가 몇 개인지 출력한다. */ public static void main(String[] args) { Scanner sc = new Scanner(S..

그래프의 모든 노드를 탐색하는 BFS(Breadth First Search) 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 시작노드에서 출발하여 레벨 기준으로 자기 레벨을 다 탐색하고 내려가는 과정을 반복하는 것을 ' 넓이우선탐색(BFS) '라고 한다. ** (시작노드 기준으로 가까운 노드를 먼저, 최단경로를 보장) ** 🕑 시간복잡도: O(V+E) (V:정점수, E:간선수) [모든 정점을 한 번씩 방문하고, 그러기 위해 모든 간선을 한 번씩 검사했으니] BFS와 큐 BFS는 큐(Queue)로 구현하며, 큐(Queue)란 먼저 들어온게 먼저 빠지는 형태의 자료구조(FIFO)를 말한다 Queue queue = new ArrayDeque(); BFS 코드 구현 ⚠️ 한번 방문한 노드..