List와 Map, 백준 10807번 1707번, 스택 과 큐 , 이진트리

List와 Map, 백준 10807번 1707번, 스택 과 큐 , 이진트리

 

List와 Map 코드로 이해하기

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // ArrayList 생성 및 추가
        List<String> list = new ArrayList<>();
        list.add("Apple");
        list.add("Banana");
        System.out.println(list);

        // HashMap 생성 및 추가
        Map<String,Integer> map = new HashMap<>();
        map.put("Alice", 24);
        map.put("Bob", 27);
        
       // Alice의 나이 출력
       System.out.println(map.get("Alice"));
    }
}

 

 

 

 

 10807번 개수 세기 성공

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 입력 처리

        int N = scanner.nextInt();

       int[] numbers = new int[N];
       for(int i = 0; i< N; i++) {
           numbers[i] = scanner.nextInt();
       }


       //3번째 쭐
        int v = scanner.nextInt();

        // 문제 해결 코드

        int count = 0;

        for(int number : numbers) {
            if(number == v) {
                count++;
            }

        }



        // 출력
        System.out.println(count);
    }
}

 

 

풀이,

 

세 번째 입력은 찾고자하는 숫자 v입니다. 여기서 '2'가 해당되는 것은, 사용자가 "11", "1 4 1 2 4 2 4 2 3 4 4", 그리고 "2"라는 세 가지 입력을 주었기 때문입니다.

즉, 사용자는 첫 번째 줄에 정수의 개수인 '11'을 입력하고, 두 번째 줄에는 '11'개의 정수인 "1 4 1 2 4 2 ... (생략) ...3,4,4"를 입력했습니다. 그리고 세 번째 줄에서 찾으려는 숫자인 '2'를 입력했습니다.

이 프로그램은 이렇게 받은 세 가지 입력값을 바탕으로 작동하며, 마지막으로 주어진 정수들 중에서 찾으려는 숫자('2')가 몇 개 있는지 카운트하여 출력합니다. 따라서 이 경우에는 '3'이 출력됩니다(두 번째 줄에서 '2'가 총 세 번 등장하기 때문).

여기서 중요한 것은 이 코드가 사용자로부터 받아들이는 각각의 입력값들이 특정한 역할과 의미를 가진다는 점입니다. 첫번째 줄의 값은 전체 정수의 개수를 나타내며, 두번째 줄의 값들은 실제 데이터(정수들)를 나타내고, 마지막으로 세번째 줄의 값은 우리가 몇 개 있는지 알아보려하는 특정 숫자 v를 나타냅니다.

 

 

스택 과 큐 이해도

DFS

스택

push
pop
peek

,
종류
DFS , 백트래킹 
후입선출

 

 

---

BFS 

큐

종류

BFS 선입선출

 

 

1707번

 

 

 1707번

 

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph;
    static int[] color;

    public static boolean dfs(int node, int c) {
        color[node] = c; // 디버거 포인트 1: 현재 노드에 색상이 할당되었습니다.

        for (int adjNode : graph[node]) {
            if (color[adjNode] == 0) {
                if (!dfs(adjNode, 3 - c)) { // 디버거 포인트 2: 아직 색칠되지 않은 인접 노드를 방문하고 재귀적으로 dfs 함수를 호출합니다. 만약 false가 반환된다면 이분 그래프 조건이 위배된 것입니다.
                    return false;
                }
            } else if (color[adjNode] == color[node]) { // 디버거 포인트 3: 이미 색칠된 인접 노드의 색상이 현재 노드와 같다면 이분 그래프 조건이 위배됩니다.
                return false;
            }
        }
        return true;
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int testCaseCount = sc.nextInt();

        while (testCaseCount-- > 0) {
            int vertexCount = sc.nextInt();
            int edgeCount = sc.nextInt();

            graph = new ArrayList[vertexCount+1];

            for (int i=1; i<=vertexCount; i++) {
                graph[i] = new ArrayList<>();
            }

            color = new int[vertexCount+1];

            for (int i=0; i<edgeCount; i++) {
                int vertexU = sc.nextInt();
                int vertexV = sc.nextInt();

                graph[vertexU].add(vertexV);
                graph[vertexV].add(vertexU);
            }

            boolean isBipartite=true;

            for(int node=1 ; node<=vertexCount ; node++){
                if(color[node]==0 && !dfs(node, 1)){ // 디버거 포인트 4: 아직 방문하지 않은 각 노드에 대해 DFS를 수행합니다. 만약 false가 반환되면 해당 그래프는 이분 그래프가 아닙니다.
                    isBipartite=false;
                    break;
                }
            }

            System.out.println(isBipartite ? "YES" : "NO"); // 디버거 포인트 5: 모든 정점을 확인한 후, 최종적으로 이분 그래프 여부를 출력합니다.
        }
    }
}

 

간선과 정점 이란?

 

 

그래프에서 정점(vertex)은 위치를, 간선(edge)은 두 정점 사이의 연결을 나타냅니다.

간단히 말해, 정점은 '도시'라고 생각하면 되고, 간선은 '도시와 도시를 잇는 도로'라고 생각하면 됩니다. 이 때, 각 도로는 반드시 두 개의 도시를 연결합니다.

따라서 주어진 입력에서 4개의 정점과 4개의 간선이 있다는 것은 총 4개의 '도시'가 있으며 이들을 직접 연결하는 '도로'가 4개 있다는 것을 의미합니다.

 

 

위 코드로 예제 입력인 4, 4, 1 2, 2 3, 3 4, 4 1 을 주면, 출력 결과는 다음과 같습니다:

Visit node: 1
Visit node: 2
Visit node: 3
Visit node: 4

 

이것은 DFS 알고리즘이 1, 2, 3, 4 순서로 정점을 방문했음을 나타냅니다.

 

 

이진검색 트리의 구조

 

이진트리 

구조