코테 전 읽고 가면 좋은 것

시험 전 외울 것 총정리

---

1. 입력

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
String s = sc.next();

---

2. 리스트안의리스트 (그래프)

List<List<Integer>> graph = new ArrayList<>();
for(int i = 0; i<=N; i++)
	graph.add(new ArrayList<>());
    
    
graph.get(a).add(b);

for(int nxt : graph.get(cur)){}

 

//리스트
List<Integer> list = new ArrayList<>();
list.add(10);
list.add(20);

for(int x : list) {
	System.out.println(x); 
}

for(int i = 0; i<list.size(); i++){
	System.out.println(list.get(i));
}    

for(int i=0; i<list.size(); i++){
	System.out.println(list.get(i));
}


//리스트안의 리스트
List<List<Integer>> graph = new ArrayList<>();

for(int i = 0; i<=N; i++){
	graph.add(new ArrayList<>()); //리스트 안에 리스트 만들기
} 

graph.get(1).add(2);
graph.get(1).add(3);
graph.get(2).add(1);

for(int i =0;i<graph.size();i++){
	for(int x : graph.get(i)){
    	System.out.println(i+"의 이웃"+x);
    }
}

//특정 칸만 순회 ([1] 의 2 , 3 순회)
for(int nxt:graph.get(1)) {
	System.out.println(nxt); //2,3
}

---

3. BFS

boolean[] visited = new boolean[N+1];
Queue<Integer>queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;

while (!queue.isEmpty()) {
	int cur = queue.poll();
    for(int nxt : graph.get(cur)){
    	if(!visited[nxt]){
        	visited[nxt] = true;
            queue.offer(nxt);
        }
    }
}

 

---

4. BFS 2차원 (ex 미로)

int[] dx = {-1,1,0,0};
int[] dy = {0,0,-1,1};

boolean[][]visited = new boolean[R][C];
Queue<int[]>queue = new LinkedList<>();

queue.offer(new int[]{x,y});
visited[x][y] = true;

while(!queue.isEmpty()){
	int[]cur = queue.poll();
    for (int i = 0; i<4; i++){
    	int nx = cur[0] + dx[i];
        int ny = cur[1] + dy[i];
        if(nx>=0 && nx < R && ny>=00 && ny<C){
        	if(!visited[nx][ny] && grid[nx][ny] ==0) {
            	visited[nx][ny] = true;
                queue.offer(new int[]{x,y});
              
            }
        }
    }
}

---

5. DFS

static void dfs(int cur) {
    visited[cur] = true;
    for (int nxt : graph.get(cur)) {
        if (!visited[nxt])
            dfs(nxt);
    }
}

---

6. 우선순위큐

// 최소힙
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 최대힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

maxHeap.offer(5);  // 넣기
maxHeap.poll();    // 꺼내기 (최댓값)

---

7. 정렬

// 1차원
Arrays.sort(arr);

// 2차원 (x기준)
Arrays.sort(arr, (a, b) -> Integer.compare(a[0], b[0]));

---

8. 2차원 누적합

// 만들기
for (int i = 1; i <= R; i++)
    for (int j = 1; j <= C; j++)
        prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];

// 구간합 쿼리
int sum = prefix[r2][c2] - prefix[r1-1][c2] - prefix[r2][c1-1] + prefix[r1-1][c1-1];

---

9. StringBuilder (출력)

StringBuilder sb = new StringBuilder();
sb.append(result).append('\n');
System.out.print(sb);

---

우선순위

순위 항목

★★★	BFS, DFS
★★★	우선순위큐
★★☆	리스트안의리스트
★★☆	2차원 누적합
★☆☆	2차원 BFS