https://www.acmicpc.net/problem/2606

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제

어떻게 풀까

각 노드의 값을 인덱스값으로 하여 인접한 노드의 리스트를 리스트 형태로 저장하고, bfs 구현 코드를 활용하여 인접한 노드 방문수를 센다 주의점으로는 인덱스 값이기 때문에 각 노드값에 -1 감염된 컴퓨터의 수이기 때문에 시작 노드는 카운트에 포함하지 않는다

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int M;

    static int comCount = -1;
    private static List<List<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(read.readLine());
        M = Integer.parseInt(read.readLine());

        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<>()); // 각 노드마다 빈 리스트를 초기화
        }

        for (int i = 0; i < M; i++) {
            StringTokenizer stoi = new StringTokenizer(read.readLine());
            int mainNode = Integer.parseInt(stoi.nextToken())-1;
            int connectNode = Integer.parseInt(stoi.nextToken())-1;
            if (!graph.get(mainNode).contains(connectNode)) {
                graph.get(mainNode).add(connectNode);
            }
        }

        BFS(0);

        System.out.println(comCount);
    }

    private static void BFS(int startNode) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode); // 시작 노드를 큐에 추가
        visited[startNode] = true; // 시작 노드 방문 처리

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 노드를 꺼냄

            // 현재 노드의 인접 노드를 탐색
            for (int adjacent : graph.get(node)) {
                if (!visited[adjacent]) { // 방문하지 않은 노드가 있으면
                    queue.add(adjacent); // 큐에 추가
                    visited[adjacent] = true; // 방문 처리
                    comCount ++;
                }
            }
        }
    }
}

https://www.acmicpc.net/problem/31575

문제

전날에 비해 비트코인의 시세가 백만원이나 오른 어느 아침, 진우는 거래소에 가서 비트코인을 매도하려고 한다. 현재 비트코인의 시세가 점점 떨어지고 있기 때문에 진우는 최대한 빨리 거래소에 가야 한다. 도시는 가로 $N$, 세로 $M$ 크기의 격자 모양으로 이루어졌다. 진우는 북서쪽 끝에 있고 거래소는 남동쪽 끝에 있다. 도시의 일부 구역은 공터 또는 도로라서 진우가 지나갈 수 있지만, 어떤 구역은 건물이 있어서 진우가 갈 수 없다. 진우는 최대한 빨리 거래소에 가야 하므로, 동쪽(오른쪽) 또는 남쪽(아래쪽)으로만 이동하여 거래소로 도착할 수 있어야 한다. 진우를 도와 거래소로 갈 수 있는지 구하는 프로그램을 작성하여라. 진우의 현재 위치가 거래소일 수 있다.

입력

첫 번째 줄에 도시의 가로 크기 $N$과 세로 크기 $M$ ( $1 \le N, M \le 300$)이 주어진다. 두 번째 줄부터 $M$개의 줄에는 도시의 형태를 나타내는 $N$개의 정수가 공백을 사이에 두고 주어진다. 각 칸이 1인 경우 진우가 갈 수 있는 칸을 의미하고 0인 경우 진우가 갈 수 없는 칸을 의미한다. 왼쪽 위의 끝 칸과 오른쪽 아래의 끝 칸은 모두 1이다.

출력

첫 번째 줄에 진우가 거래소로 갈 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

예제

5 4
1 1 1 1 1
0 1 0 0 1
1 0 0 0 1
0 0 0 1 1

-> YES

어떻게 풀까?

dfs를 활용하여 방문처리와 함께 경로 탐색

gpt 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int n, m;
    static int[][] road;
    static boolean[][] visited;

    static int[] dx = {1, 0};    // 방향 배열(동, 남)
    static int[] dy = {0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        n = Integer.parseInt(stoi.nextToken());
        m = Integer.parseInt(stoi.nextToken());

        road = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            StringTokenizer stoiLoad = new StringTokenizer(read.readLine());
            for (int j = 0; j < n; j++) {
                road[i][j] = Integer.parseInt(stoiLoad.nextToken());
            }
        }
        if (dfs(0,0)){
            System.out.println("Yes");
        }else {
            System.out.println("No");
        }
    }



    public static boolean dfs(int x, int y) {    // dfs 알고리즘
        visited[x][y] = true;    // 방문한 배열은 true 저장
        for(int i = 0; i < 2; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX >= 0 && nextY >= 0 && nextX < m && nextY < n && !visited[nextX][nextY]) {    // 범위 내에 있고 방문한 적이 없으면
                if(road[nextX][nextY] == 1) {    // 배열 값이 1이면
                    dfs(nextX, nextY);    // dfs 호출
                }
            }
        }
        return visited[m-1][n-1];    // 거래소 방문여부 리턴
    }
}

첫번째 풀이

    static boolean dfs(int x, int y) {
        //도착 지점에 도착했는가?
        if(x == m-1 && y == n-1){
            return true;
        }
        //주어진 지도에서 벗어났는가?
        if(x >= m || y >= n){
            return false;
        }
        //오른쪽, 아랫쪽 1인 길로 가서 dfs 함수 재귀호출
        if (road[x + 1][y] == 1) {
            dfs(x + 1, y);
        } else if (road[x][y + 1] == 1) {
            dfs(x, y + 1);
        }
        return false;
    }

방문처리가 안됨, 잘못 갔을 경우 돌아올 수 없다

두번째 풀이

static boolean dfs(int x, int y) {
    // 종료 조건: 목적지 도달 시 true 반환
    if (x == n - 1 && y == m - 1) {
        return true;
    }

    // 범위를 벗어나거나 이동할 수 없는 위치일 경우 false 반환
    if (x < 0 || x >= n || y < 0 || y >= m || road[x][y] == 0 || visited[x][y]) {
        return false;
    }

    // 현재 위치를 방문 처리
    visited[x][y] = true;

    // 동쪽 또는 남쪽으로 이동하며 DFS 재귀 호출
    if (dfs(x + 1, y) || dfs(x, y + 1)) {
        return true;
    }

    // 방문 취소
    visited[x][y] = false;
    return false;
}

범위를 벗어나거나 이동할 수 없는 위치일 경우 false 반환 이 조건에서 false를 반환할 것이 아니라 그 뒤로 돌아가서 다시 탐색이 안 되는것 같다. 다시 어떻게 뒤로 돌아가지?

재귀함수 모르겠다! 스택 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static int n, m;
    static int[][] road;
    static boolean[][] visited;

    static int[] dx = {1, 0};    // 방향 배열(동, 남)
    static int[] dy = {0, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        n = Integer.parseInt(stoi.nextToken());
        m = Integer.parseInt(stoi.nextToken());

        road = new int[m][n];
        visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            StringTokenizer stoiLoad = new StringTokenizer(read.readLine());
            for (int j = 0; j < n; j++) {
                road[i][j] = Integer.parseInt(stoiLoad.nextToken());
            }
        }
        if (dfsIterative(0, 0)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static boolean dfsIterative(int startX, int startY) {
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[] {startX, startY});
        visited[startX][startY] = true;

        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int x = current[0];
            int y = current[1];

            // 목적지 도달 여부 확인
            if (x == m - 1 && y == n - 1) {
                return true;
            }

            // 동쪽 및 남쪽 방향으로 이동할 수 있는지 확인
            for (int i = 0; i < 2; i++) {
                int nextX = x + dx[i];
                int nextY = y + dy[i];

                // 유효한 위치이고, 방문하지 않았으며, 도로(1)인 경우 스택에 추가
                if (nextX >= 0 && nextY >= 0 && nextX < m && nextY < n && !visited[nextX][nextY] && road[nextX][nextY] == 1) {
                    stack.push(new int[] {nextX, nextY});
                    visited[nextX][nextY] = true;
                }
            }
        }

        return false;  // 스택이 비었으나 목적지에 도달하지 못한 경우
    }
}

1인 곳에 가면 스택에 push 하고 이후에 들어간 방향의 스택에서 1인 쪽의 경로가 없을때 까지 탐색한다 오른쪽, 아래쪽 모두 1일때 이후에 push된 경로로 탐색하다가 경로가 없어서 push하지 못하면 그때 양쪽 모두 들어갔을때의 요소로 다시 탐색한다.

GraphQL(Graph Query Language) API를 위한 쿼리 언어, SQL이 데이터베이스 시스템으로부터 데이터를 가져오는 목적을 가진다면, GraphQL은 클라이언트가 데이터를 서버로부터 가져오는 것을 목적으로 한다.

특징

• restful api 와는 다르게 하나의 엔드 포인트를 사용, 모든 요청을 post로 보냅니다
• restful api는 호출할때에 각 리소스의 모든 데이터가 반환 → overfetching (필요 이상의 데이터가 전송) 발생 → GraphQL방식 → 쿼리에서 요청한 데이터만 응답
• Caching 캐싱이 어렵다 요청들이 복잡한 graphQL 메시지로 되어있어서 이것을 기준으로 캐싱하기 용이하지 않음
• 쿼리를 서버에서 해석해서 작업을 수행하기 때문에 서버에 부담이 갈 수 있음

RESTful API로 구현했을때 문제점을 개선

Underfetching 문제 → 하나의 요청으로는 충분한 데이터를 모두 받아오지 못하는 문제 Overfetching → 필요 없는 데이터까지 모두 받아오게 되는 문제

책 상세 페이지 (책 정보, 리뷰 리스트, 리뷰 유저 정보)

1. 책정보, 2. 리뷰, 3. 리뷰쓴 사용자 정보, … → 여러번 API를 호출, 이때마다 필요없는 정보도 같이 받아오게됨 api를 여러번 호출 해서 받은 데이터를 다시 조합하여 사용, 이때 필요없는 데이터도 생기게 되는 문제점을 개선 → graphQL

데이터 추가 수정 삭제는 어떻게?

• mutation을 사용한다 (메소드 같은 개념)

addbook -> 책 추가 하는 타입 -> 책 추가 하는 동작 수행 addbook 내부의 데이터로 책의 데이터를 추가 그 아래 타입의 형태로 데이터를 반환

구독 기능

Subscription 구독

실시간 데이터 변화를 감지하여 표시하여야 할때

• restful api → 새로운 리뷰 쌓이는거 확인하기 위해 수시로 api 요청해서 데이터를 받아와야한다
• graphql 특정 리소스 데이터 업데이트 마다 알림을 받을 수 있음, 리소스 업데이트때 보내주는 정보로 프론트에서 반응하여 화면을 업데이트 해서 보여주게됨 → 웹소켓을 사용

subscription{
    reviewAdded(bookId: "1") {
    //보내줄 정보
        comment
        rating
        user {
            name
        }
    }
}

graphQL 규칙 문서 (Schema 스키마)

graphQL이 적합한 서비스

• 다양한 데이터 요구가 있는 모바일/웹 애플리케이션 소셜 미디어 앱 (예: Facebook, Instagram 등) → 사용자 피드, 프로필 정보, 알림 등 여러 개의 리소스중 필요한 리소스만 가져오게 하는 graphQL이 적합

• 복잡하고 방대한 데이터 모델을 가진 서비스 대용량 데이터를 다루는 대시보드/분석 애플리케이션 데이터 시각화/분석 도구 (예: Google Analytics, Tableau) → Overfetching, Underfetching으로 발생하는 오버헤드가 큰 서비스 → graphQL 적합

• 데이터 업데이트 실시간 반응이 필요한 서비스 (graphQL 구독 기능 활용) 채팅 애플리케이션 (예: Slack, Discord) → 실시간으로 많은 데이터가 업데이트되는 경우, 필요한 정보만 선택적으로 구독

• 클라이언트가 데이터 요청에 많은 제어권을 가진 서비스 (예시..?)

참고: https://www.youtube.com/watch?v=lYuWfoWD67Q

HTTP, HTTPS, SMTP 등을 통해 XML 기반의 메시지를 컴퓨터 네트워크 상에서 교환하는 프로토콜 입니다.

특징

• XML을 사용 → json 보다 큰 양을 보내고 받습니다.
• POST의 body에 xml의 내용을 담아 보냅니다.
• 요청하는 바를 body에 담은 태그를 보고 확인합니다.

  //xml 일부
  <soapenv:Body>
    <lib:AddBookRequest>
         <lib:Title> aaa </lib:Title>
         ...
    </lib:AddBookRequest>
  </soapenv:Body>

  json이라면?

POST 
"book" : {
    "title" : "aaa"
}

WSDL (Web Services Description Language)

• WSDL 일부

  <!-- Abstract interfaces -->
   <interface name="RESTfulInterface">
      <fault name="ClientError" element="tns:response"/>
      <fault name="ServerError" element="tns:response"/>
      <fault name="Redirection" element="tns:response"/>
      <operation name="Get" pattern="http://www.w3.org/ns/wsdl/in-out">
         <input messageLabel="GetMsg" element="tns:request"/>
         <output messageLabel="SuccessfulMsg" element="tns:response"/>
      </operation>
      <operation name="Post" pattern="http://www.w3.org/ns/wsdl/in-out">
         <input messageLabel="PostMsg" element="tns:request"/>
         <output messageLabel="SuccessfulMsg" element="tns:response"/>
      </operation>
      <operation name="Put" pattern="http://www.w3.org/ns/wsdl/in-out">
         <input messageLabel="PutMsg" element="tns:request"/>
         <output messageLabel="SuccessfulMsg" element="tns:response"/>
      </operation>
      <operation name="Delete" pattern="http://www.w3.org/ns/wsdl/in-out">
         <input messageLabel="DeleteMsg" element="tns:request"/>
         <output messageLabel="SuccessfulMsg" element="tns:response"/>
      </operation>
   </interface>

soap 으로 구현된 서비스 사용 설명서 (타입, 규칙 정의 문서) → 프로그램이 읽으라고 작성한 문서 XML 형태로 작성

• 서비스에 대한 상세한 표준화
• 클라, 서버 기능 자동화, 개발과정 간소화
• 사람이 작성하기 어려움, 유연성 부족
• 캐싱이 용이하지 않다 - 복잡한 XML, 모두 POST 요청 캐싱하기 어려움

SOAP 보안

WS-Security 보안 프로토콜 지원

• 메시지의 무결성, 기밀성 인증가능

• 금융, 의료정보, 정부 서비스 (높은 보안 수준 요구 서비스에 사용)

• 서버와 클라간 유연하지 않음 ⇒ 엄격한 규약에 적합 금융에 적합 - 하나의 트랜젝션으로 처리되어야 함

• ACID (Atomicity, Consistency, Isolation, Durability)

  • 트랜젝션을 안전하게 처리하는 프로토콜을 지원 ※ 원자성(Atomicity), 일관성(Consistency), 격리성(Isolation), 지속성(Durability)
    • State, 상태를 저장할 수 있다 → 이전 단계의 상태를 저장해야하는 트랜젝션에 적합

RESTful 한 API, REST의 특징과 규칙을 지키는 API 공통적으로 규칙을 정해두어 협업, public api 사용 등과 같이 restful api를 사용시 따로 학습 코스트를 들이지 않아도 된다.

RESTful API 규칙

• URI에서는 어떤 자원에 관한 것인지만 표현해야 한다 /users -> users에 관한 api
• 어떤 작업을 하는지에 대한 동사는 포함하지 않는다 /users/get -> get (x)
• HTTP 메소드로 어떤 종류의 작업을 하는지 표현한다 (POST, GET, PUT, PATCH, DELETE)
• 쿼리 파라미터로 조건을 지정할 수 있다 (페이징 정보)
• 특정 데이터를 받고 싶을때 끝에 고유 식별자를 넣어준다 (/books/1) → 1번 책
• 하위 항목이 있다면 그 뒤에 붙인다 (books/1/reviews) → 리소스들이 서로 어떤 관계를 갖는지 URI를 통해 쉽게 파악할 수 있음

• HATEOA (Hypermedia As The Engine Of Application State) → 각 요청의 응답에 사용가능한 다른 요청의 정보를 포함 시킨다 (update, delete..)

HTTP 메소드

• GET - 데이터의 정보를 가져온다
• POST - 데이터 추가
• PUT - 데이터 업데이트 (데이터 전체)
• PATCH - 데이터 일부 업데이트
• DELETE - 데이터 삭제

특징

Stateless (무상태)

상태가 없는 통신, 클라이언트의 상태 정보는 서버가 저장하지 않아야 합니다. 즉, 클라이언트 요청시 매번 필요한 정보를 줘야 합니다. 서버는 클라이언트 요청과 관련된 데이터를 저장할 수 없습니다.

• 서버의 확장성 고려, 연관되어 있다면 확장 어려움

Idempotent (균일한 인터페이스)

동일한 리소스에 대한 모든 API 요청은 요청의 출처에 관계없이 동일하게 표시되어야 합니다.

Cacheability (캐시 가능성)

서버와 클라이언트 간에는 정보를 저장하지 않아야하지만, 자기가 어떤 응답을 보냈는지 어떤 응답을 받았는지는 기억해야 합니다.

캐싱 - 요청에 대한 응답을 캐싱해두면 같은 요청 여러번 보낼 필요 없고, 같은 요청에 대해서는 캐싱해둔 데이터만 보내면 되어 응답에 대한 리소스를 아낄 수 있습니다.

https://www.acmicpc.net/problem/1388

문제

형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나무 판자는 크기 1의 너비를 가졌고, 양수의 길이를 가지고 있다. 기훈이 방은 직사각형 모양이고, 방 안에는 벽과 평행한 모양의 정사각형으로 나누어져 있다. 이제 ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어진다. 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자이다. 기훈이의 방 바닥을 장식하는데 필요한 나무 판자의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 방 바닥의 세로 크기N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 M개의 문자가 주어진다. 이것은 바닥 장식 모양이고, '-‘와 ’|‘로만 이루어져 있다. N과 M은 50 이하인 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

어떻게 풀까?

2차원 배열로 각 문자를 각 위치에 저장해두고 문자에 해당하는 방향으로 다른 문자가 나올때 까지 DFS 방식을 사용하여 탐색헌다. 방문한 곳은 방문한 표시를 해서 중복으로 찾아지지 않도록 한다

코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int n,m;
    static char[][] board;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        n = Integer.parseInt(stoi.nextToken());
        m = Integer.parseInt(stoi.nextToken());

        board = new char[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String strLine = read.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = strLine.charAt(j);
            }
        }

        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j]) {
                     dfs(i, j, board[i][j]);
                     count++;
                }
            }
        }

        System.out.println(count);
    }

    static void dfs (int x, int y, char sym){
        visited[x][y] = true;

        // 방향 설정: '-'는 오른쪽, '|'는 아래쪽으로만 탐색
        int dx = 0, dy = 0;
        if (sym == '-') dy = 1;
        else if (sym == '|') dx = 1;

        int nx = x + dx;
        int ny = y + dy;

        // 다음 위치가 경계를 넘지 않고, 방문하지 않았으며, 같은 모양일 경우 DFS 재귀 호출
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && board[nx][ny] == sym) {
            dfs(nx, ny, sym);
        }
    }
}

DFS, BFS 모두 그래프 탐색 알고리즘 입니다. 그래프 탐색 방향의 우선순위의 차이가 있습니다.

DFS (깊이 우선 탐색, Depth-First Search)

출처 : https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

DFS는 깊이 우선 탐색 알고리즘으로, 시작점에서 출발하여 한 경로로 깊이 들어가 가능한 한 끝까지 탐색한 후, 더 이상 탐색할 수 없으면 다시 되돌아와 다른 경로를 탐색하는 방식입니다.

장점

• 특정 경로 탐색에 매우 유리합니다.
• BFS와 비교해 메모리를 적게 사용합니다(특히 노드 수가 많을 때).
• 조건을 만족하는 경로를 찾고, 조건을 만족하지 않으면 되돌아가는 문제에서 DFS가 효율적입니다.

동작

• 시작점을 지정합니다.
• 현재 노드를 재방문하지 않도록 방문 처리 합니다.
• 인접 노드를 계속 탐색 합니다.
• 이 경로에서 더 이상 탐색할 인접 노드가 없다면 이전 노드로 돌아가서 다른 경로를 탐색합니다.
• 모든 노드를 방문할때까지 or 조건을 만족하는 노드를 찾을때까지 반복합니다.

구현

재귀함수를 사용한 DFS

    // 그래프를 저장할 인접 리스트
    private static List<List<Integer>> graph = new ArrayList<>();
    // 방문 여부를 저장할 배열
    private static boolean[] visited;

    private static void DFS(int node) {
        visited[node] = true; // 현재 노드 방문 처리
        // 현재 노드의 인접 노드를 하나씩 탐색
        for (int adjacent : graph.get(node)) {
            if (!visited[adjacent]) { // 방문하지 않은 노드가 있으면
                DFS(adjacent); // 재귀 호출로 탐색
            }
        }
    }

재귀함수를 사용하면 코드가 간결하고 이해하기 쉬우며, 콜 스택을 자연스럽게 활용하여 노드 간의 깊이 우선 탐색을 처리할 수 있습니다. 하지만 그래프의 깊이가 매우 깊을 경우 스택 오버플로우가 발생할 수 있습니다.

스택을 사용한 DFS

 private static List<List<Integer>> graph = new ArrayList<>();
 private static boolean[] visited;


    private static void DFS(int startNode) {
        Stack<Integer> stack = new Stack<>();
        stack.push(startNode); // 시작 노드를 스택에 추가

        while (!stack.isEmpty()) {
            int node = stack.pop(); // 스택에서 노드 꺼내기

            if (!visited[node]) {
                visited[node] = true; // 방문 처리

                // 인접한 노드들을 스택에 추가
                for (int adjacent : graph.get(node)) {
                    if (!visited[adjacent]) {
                        stack.push(adjacent); // 방문하지 않은 인접 노드 스택에 추가
                    }
                }
            }
        }
    }

스택을 사용한 구현은 재귀 호출을 사용하지 않고 명시적으로 스택을 사용하여 탐색합니다. 이 방법은 스택 오버플로우 문제를 해결할 수 있고, 재귀에 익숙하지 않은 경우에도 쉽게 사용할 수 있습니다. 다만 코드가 다소 복잡해질 수 있습니다.

BFS(너비 우선 탐색, Breadth-First Search)

출처: https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif

BFS는 너비 우선 탐색 알고리즘으로 시작점에서 인접한 노드에서부터 인접한 노드를 모두 탐색한 후 더 이상 인접한 노드가 없으면 다음 깊이의 노드로 이동하여 더 방문하지 않은 노드가 없을 때 까지 인접한 노드를 탐색하는 방식입니다.

장점

• 최단 경로를 쉽게 찾을 수 있습니다. BFS는 모든 경로를 동시에 탐색하므로, 목표 노드를 가장 먼저 찾았을 때 그 경로가 최단 경로임을 보장합니다.
• BFS는 노드를 레벨별로 탐색하기 때문에 특정 레벨 내에 있는 모든 노드를 쉽게 찾을 수 있습니다.
• BFS는 시작 노드로부터 같은 거리만큼 떨어진 노드들을 모두 탐색한 후, 다음 레벨로 넘어가는 방식이기 때문에 계층적 탐색을 하고자 할 때 BFS가 유리합니다.

동작

BFS는 큐(Queue)를 사용하여 노드들을 순차적으로 탐색합니다.

• 탐색을 시작할 노드를 큐에 넣습니다.
• 큐에서 노드를 하나 꺼내 그 노드를 방문 처리합니다.
• 현재 노드에 인접한 노드들을 확인하여, 아직 방문하지 않은 노드들을 큐에 넣습니다.
• 큐에 더 이상 탐색할 노드가 없을 때까지 반복합니다.

구현

    0 — 1 — 2
    |   |
    3 — 4

public static void main(String[] args) {
    // 그래프 초기화
    // 노드 0 -> graph의 인덱스 0에 0과 인접한 노드를 리스트로 저장
    graph.add(Arrays.asList(1, 3));       // 노드 0의 인접 노드
    graph.add(Arrays.asList(0, 2, 4));    // 노드 1의 인접 노드
    graph.add(Arrays.asList(1));          // 노드 2의 인접 노드
    graph.add(Arrays.asList(0, 4));       // 노드 3의 인접 노드
    graph.add(Arrays.asList(1, 3));       // 노드 4의 인접 노드

    // 방문 배열 초기화
    visited = new boolean[5];

    // BFS 시작 노드를 0으로 설정
    BFS(0);
}


    private static List<List<Integer>> graph = new ArrayList<>();
    private static boolean[] visited;

    private static void BFS(int startNode) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode); // 시작 노드를 큐에 추가
        visited[startNode] = true; // 시작 노드 방문 처리

        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 노드를 꺼냄
            System.out.println("Visited Node: " + node);

            // 현재 노드의 인접 노드를 탐색
            for (int adjacent : graph.get(node)) {
                if (!visited[adjacent]) { // 방문하지 않은 노드가 있으면
                    queue.add(adjacent); // 큐에 추가
                    visited[adjacent] = true; // 방문 처리
                }
            }
        }
    }

DFS가 BFS보다 메모리를 왜 더 적게 사용하는가?

BFS는 한 번에 많은 노드를 큐에 저장해야 하므로, 너비가 큰 그래프일수록 더 많은 메모리를 사용하게 됩니다. 반면 DFS는 깊이 우선 탐색이므로, 스택에 경로의 깊이 만큼의 노드를 저장하여 메모리 사용량이 적습니다. (재귀함수를 사용하더라도 시스템 스택을 사용하여 메모리 적으로는 크게 다르지 않습니다.)

• BFS는 너비 우선 탐색 방식으로, 현재 레벨의 모든 노드를 저장한 후 다음 레벨로 넘어갑니다. 특정 노드의 인접 노드들을 모두 한꺼번에 큐에 넣기 때문에, 한 번에 큐에 저장되는 노드의 수가 많아집니다.

• 그래프의 너비가 클수록, 한 번에 탐색해야 하는 인접 노드의 수가 많을수록 큐에 저장해야 하는 노드가 많아지고 메모리 사용량이 커집니다.

https://www.acmicpc.net/problem/12015

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

어떻게 풀까?

upperBound를 활용하여 가장 작은 값부터 증가된 수 개수 + 1로 하면 될것 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(read.readLine());

        int[] arr = new int[N];
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stoi.nextToken());
        }
        Arrays.sort(arr);

        int answer = 1;
        for (int i = 0; i < N; i++) {
            if(i > 0 && arr[i] != arr[i-1] ){
                int upper = upperBound(arr, arr[i]);
                if(upper > 0){
                    answer += 1;
                }
            }
        }
        System.out.println(answer);
    }

    public static int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] <= target) {
                left = mid + 1; // target 값보다 작거나 같은 경우, 오른쪽 절반을 탐색
            } else {
                right = mid; // target 값보다 큰 경우, 범위를 줄여서 탐색
            }
        }
        return left; // upper bound를 반환
    }
}

뭐가 문제 일까, GPT의 답변은 이랬다

문제점 1: i = upper;로 인덱스 갱신

현재 코드에서는 upperBound를 사용하여 i 값을 갱신하는데, 이렇게 하면 일부 값들이 건너뛰어져서 누락될 수 있습니다.

문제점 2: 중복된 값 처리

if (i > 0 && arr[i] != arr[i - 1])로 중복값을 처리하고 있지만, 이 방식은 증가하는 부분 수열을 찾는 데 적합하지 않습니다.

수정

입력 받은 배열의 요소를 먼저 정렬하지 말고, 새로운 배열을 만들어서 그 배열에서 중복 된다면 교체, 그렇지 않다면 적절한 위치 인덱스 값을 찾아서 값을 추가 하는 방법으로 수정

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(read.readLine());
        int[] arr = new int[N];

        StringTokenizer stoi = new StringTokenizer(read.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stoi.nextToken());
        }

        // LIS를 저장할 리스트
        ArrayList<Integer> lis = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            int num = arr[i];

            // 이진 탐색을 통해 적절한 위치에 값을 삽입 또는 대체
            int pos = binarySearch(lis, num);

            if (pos == lis.size()) {
                lis.add(num);
            } else {
                lis.set(pos, num);
            }
        }

        System.out.println(lis.size());
    }

    // 이진 탐색을 사용하여 LIS 리스트에서 값의 적절한 위치를 찾는 함수
    public static int binarySearch(ArrayList<Integer> lis, int target) {
        int left = 0;
        int right = lis.size();

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (lis.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left; // 타겟 값이 들어갈 위치 반환
    }
}

OWASP Top Ten은 웹 애플리케이션에서 가장 위험한 보안 취약점 10가지를 정리한 목록입니다. 전 세계 보안 전문가들이 제공한 데이터를 바탕으로 만들어지며, 매 몇 년마다 업데이트되어 최신 보안 위협을 반영해 목록을 갱신 합니다.

1. Broken Access Control

사용자가 허용되지 않는 기능이나 데이터에 접근하여 발생하는 보안 취약점 입니다.

예시

• /admin 경로로 관리자 메뉴로 접근
• ID 123인 유저가 url 상의 파라미터인 userID를 userID=567로 보냄

해결방법

• 역할 기반 접근 제어 (RBAC) 사용자의 역할에 맞게 명확한 권한에 대한 정의를 하여, 자기의 역할에 필요한 리소스와 기능에만 접근 가능하도록 해야합니다.
• 최소 권한 원칙 사용자가 서비스를 사용하는데 필요한 최소한의 권한을 부여해야 합니다. (사용자의 최소 권한) (RBAC 역할에 대해 최소 권한)
• 간접 참조 (Indirect Object References) 매핑이나 토큰을 사용하여 직접적인 숫자나 데이터 참조를 피하는 방식을 사용

2.암호화 실패 (Cryptographic Failures)

암호화가 필요한 민감한 데이터를 암호화 하지않았을때 발생하는 보안 취약점 입니다.

예시

• 비밀번호 등과 같은 민감한 데이터 정보를 암호화 되지 않은 평문으로 저장
• 오래된 암호화 알고리즘을 사용
• 데이터를 탈취, 변조

해결 방법

• SSL/TLS 인증서 관리: SSL/TLS 인증서는 항상 유효한 상태를 유지해야 하며, TLS를 사용해 네트워크를 통한 데이터 전송을 암호화해야 중간자 공격(MITM)을 예방할 수 있습니다.
• 강력한 암호화 알고리즘 (AES-256) 사용
• 민감한 정보의 저장은 해시 알고리즘(bcrypt, scrypt, Argon2)을 사용하여 저장
• 암호화 키 관리
  • 암호화 키는 소스 코드에 저장 되면 안됩니다
  • 생성 시 임의성(Randomness)을 보장하는 보안된 난수 생성기를 사용해야 합니다.
  • 키 관리 시스템(KMS, Key Management System)을 사용합니다 (AWS KMS, Google Cloud KMS)
  • 정기적인 암호화 키 교체
  • 사용자히 않는 암호화 키는 재생하여 사용될 수 없도록 처리후 폐기
  • 암호화 키 접근, 사용기록을 로그로 남김, 모니터링

3.인젝션 (Injection)

외부로부터 입력받은 데이터를 제대로 검증하지 않고, 해당 데이터를 데이터베이스 쿼리나 운영체제 명령 등으로 실행하는 경우 발생하는 보안 취약점 입니다. 대표적으로 sql Injection이 있습니다.

예시

• sql Injection passord 부분에 무조건 참이 되게 하는 조건을 추가하여 비밀번호를 입력하지 않아도 로그인 되게 해버림

  SELECT * FROM users WHERE username = 'admin' AND password = '' OR '1'='1';
  

### 해결방법
- 사용자 입력 데이터의 필터링 (Sanitization)
입력 받은 데이터가 사전에 설정한 데이터의 형태가 맞는지 확인
- 매개변수화된 쿼리(Parameterized Queries)
쿼리와 입력 데이터를 분리 하여, 입력 자체는 쿼리를 완성하기 위한 데이터로만 취급
- 입력 유효성 검사(Input Validation)
사전에 설정한 데이터 구조인지, 쿼리의 매개변수에 넣을때 문제 없는 데이터 인지(특수문자) 유효성 검사


## 4.불완전한 설계 (Insecure Design)
> 보안적인 관점에서 적절하게 설계되지 않았을 때 발생하는 보안 취약점 입니다.
보안 요구 사항을 충분히 고려하지 않았거나, 위험 관리가 부족할 때 발생합니다.

### 원인
- 세션 관리 미흡, 세션 하이재킹(토큰 탈취)과 같은 공격에 노출
- 오류 처리 및 로깅 부족
- 데이터 보호 미흡, 데이터 암호화를 설계 단계에서 충분히 고려하지 않으면, 데이터 유출의 위험
- 불필요하게 복잡한 기능 추가, 핵심 기능에 필수적이지 않거나 복잡한 기능을 추가하면 공격 표면이 넓어져 공격에 취약
- 위협 모델링 부족: 잠재적인 보안 위협을 미리 분석하고 설계에 반영하지 않는 것
- 테스트 부족: 개발 과정에서 보안 테스트를 충분히 포함하지 않으면, 취약점 사전 예방 어려움

### 해결 방안
- 잠재적 위협을 설계 단계에서 분석하고, 그에 맞는 방어 전략을 수립
- 데이터 입력 검증 설계 단계에 포함
- 세션 하이재킹을 방지하기 위한 보안 강화 설계(세션 타임아웃 설정, 안전한 쿠키 사용 등)를 적용
- 에러 메시지나 로그에 중요한 정보가 노출되지 않도록 설계
- 데이터 암호화, 데이터 보호 메커니즘을 고려

## 5. 보안 설정 오류 (Security Misconfiguration)
> 시스템의 보안 설정이 잘못 정의되었거나, 제대로 구현되지 않거나 유지 관리되지 않을 때 발생하는보안 취약점 입니다. 이 취약점은 애플리케이션 스택의 어느 수준에서도 발생할 수 있습니다. 

### 원인
- 기본 사용자명 및 비밀번호 사용: 설정 후 기본 계정 정보를 변경하지 않으면, 공격자는 쉽게 시스템에 접근 (root / 1)
- 불완전한 설정: 필요한 모든 보안 제어가 제대로 구현되지 않아 시스템의 일부가 보호되지 않은 상태로 남아 있을 수 있음
- 디버깅 정보 노출: 프로덕션 환경에 디버깅 정보를 남겨두면, 공격자가 이를 악용해 시스템에 대한 중요한 정보를 파악 가능
- 보안 패치 미적용: 시스템에 최신 보안 패치가 적용되지 않으면, 알려진 취약점에 쉽게 노출
- 디렉터리 목록 노출: 디렉터리 목록이 허용된 경우, 공격자는 시스템의 구조와 중요한 파일을 쉽게 탐색

### 해결방법
- 기본 사용자 이름과 비밀번호는 반드시 변경, 자격 증명을 설정
- 보안 패치 및 업데이트 주기적 적용
- 필요하지 않은 기능을 비활성화, 미설치, 삭제
- 에러 처리시 민감한 정보가 노출되지 않도록 설정
- 최소 권한 원칙 적용

## 6. 취약하고 오래된 구성 요소(Vulnerable and Outdated Components)
> 최신 보안 패치가 적용되지 않은 오래된 소프트웨어를 사용하는 경우 발생하는 보안 취약점 입니다.

### 원인
- 오래된 프레임워크나 라이브러리는 새로운 보안 취약점이 발견되어도 더 이상 업데이트되지 않기 때문에 공격자가 이를 악용해 시스템에 침투
- 패치되지 않은 플러그인이나 확장 기능은 시스템 내의 민감한 데이터에 접근할 수 있는 취약점을 제공할 수 있으며, 공격자에게 쉬운 진입점을 제공

### 해결방법
- 구성 요소의 정기적인 보안 검사: 취약한 구성 요소를 식별하고, 이를 자동으로 모니터링하는 도구를 사용 (Reflectiz 외부 의존성을 스캔하고, 취약점을 발견하면 경고를 제공)
- 외부 구성 요소가 최신 상태로 유지되도록 정기적으로 업데이트하고 보안 패치를 적용
- 지원 중단된 소프트웨어 교체 안전한 대체 솔루션으로 전환

## 7.식별 및 인증 실패 (Identification and Authentication Failures)
> 사용자의 신원을 확인하고 인증하는 과정에서 발생하는 취약점입니다. 사용자가 올바르게 인증되지 않거나, 인증 정보가 안전하지 않게 관리될 때 발생하며, 공격자는 이를 통해 시스템에 무단 접근할 수 있습니다.

### 원인
- 약한 비밀번호 정책, 비밀번호가 너무 짧거나 복잡하지 않으면, 공격자가 이를 쉽게 추측
- 다중 인증 미사용, 2단계 인증 같은 추가적인 보안 레이어가 없는 경우
- 비밀번호 저장의 불안정성, 비밀번호를 평문으로 저장, 안전하지 않은 해시 알고리즘을 사용
- 세션 관리 취약점, 세션이 만료되지 않거나, 세션 토큰이 쉽게 예측 가능한 경우

- 무작위 대입 공격(Brute-force attacks): 공격자가 모든 가능한 비밀번호 조합을 시도해 인증 시스템을 뚫으려는 공격입니다. 약한 비밀번호를 사용할 경우 쉽게 성공할 수 있습니다.
- 크리덴셜 스터핑(Credential Stuffing) 공격, 이는 유출된 사용자 이름과 비밀번호 목록을 사용해 다른 사이트에 무단 로그인을 시도하는 방식입니다.

### 해결방법
- 강력한 비밀번호 정책 적용, 복잡한 비밀번호를 요구하고, 주기적인 변경을 권장
- 다중 인증(2FA) 적용, 비밀번호 외에도 추가 인증 수단(예: SMS, OTP, 인증 앱)을 사용
- 안전한 비밀번호 저장 방식 사용: 비밀번호는 bcrypt나 Argon2 같은 강력한 해시 알고리즘으로 저장하고, 솔트 값을 사용해 안전성을 높여야 합니다.
- 세션 관리 강화, 만료시간 설정
- 여러 번의 실패한 인증 시도를 감지해 계정을 잠그고, 사용자에게 경고


## 8.소프트웨어 데이터 무결성 실패 (Software and Data Integrity Failures)
> 소프트웨어나 데이터가 안전하게 보호되지 못하고, 공격자가 이를 수정하거나 변조할 수 있는 취약점입니다. 이 문제는 종종 업데이트, 데이터 처리, 코드 배포, 그리고 의존성 관리에서 발생합니다.

### 원인
- 신뢰할 수 없는 업데이트 소스(서드파티 소프트웨어나 라이브러리)를 통해 소프트웨어가 변경될 때, 공격자가 악성 코드를 삽입
- 무결성 검사 미사용, 소프트웨어나 데이터가 변경되었는지 확인하는 절차(디지털 서명, 해시 값 검사)가 없으면, 공격자는 중간에 데이터를 조작, 악성 코드 삽입
- 비정상적인 데이터 입력 처리, 사용자로부터 입력된 데이터가 제대로 검증되지 않으면 공격자가 그 데이터를 조작해 소프트웨어나 시스템 손상시킴

### 해결방법
- 소프트웨어 업데이트나 설치 시 신뢰할 수 있는 출처에서만 제공된 소프트웨어인지 확인하는 검증 절차를 적용
- 코드 서명 사용, 코드 서명을 통해 소프트웨어의 진위 여부를 확인하고, 무단 변경 여부를 방지
- 소프트웨어 및 데이터의 무결성을 정기적으로 감사하고 모니터링하여 이상이 발견되면 즉시 대응
- 데이터 입력 검증, 모든 데이터 입력에 대해 엄격한 검증 절차를 적용

## 9.보안 로깅 및 모니터링 실패 (Security Logging and Monitoring Failures)
>  시스템 내에서 발생하는 보안 관련 이벤트들을 제대로 기록하지 않거나, 기록된 로그를 효과적으로 모니터링하지 않아 발생하는 취약점입니다.

### 원인
- 불충분한 로그 기록, 시스템에서 발생하는 주요 보안 사건들이 기록되지 않으면, 사고 발생 시 원인을 파악하거나 대응하기가 어려움
- 중앙 집중식 로그 관리 부족, 다양한 시스템의 로그가 분산되어 있으면 관리가 힘들어지고, 전체 보안 상황을 모니터링하기 어려움
- 의심스러운 활동 모니터링 실패, 로그 모니터링을 하지 않으면 비정상적인 활동이나 공격 시도를 즉시 탐지 불가능

### 해결방법 
- 모든 중요한 사건 로그 기록, 사용자 인증 실패, 권한 상승 시도, 시스템 변경 등의 보안 사건을 기록
- 중앙 집중식 로그 관리 (모든 로그를 한 곳에서 관리)
- 로그 데이터를 정기적으로 검토
- 알림 및 경고 시스템 설정, 비정상적인 활동이 탐지되면 즉시 경고를 받도록 설정


## 10. Server-Side Request Forgery (SSRF)

> 공격자가 서버를 속여서 서버 측에서 임의의 요청을 보내도록 만드는 취약점입니다. 이 공격은 서버가 신뢰할 수 있는 클라이언트의 요청을 처리하는 동안 발생할 수 있으며, 공격자가 외부 시스템이나 내부 네트워크 리소스에 접근할 수 있게 됩니다.

### 원인
- 사용자가 제공한 URL을 기반으로 서버가 외부 리소스에 요청을 보낼 때, URL에 대한 제한이나 검증이 없으면 공격자가 악의적인 URL을 입력하여 서버가 원치 않는 요청을 하도록 유도
- 공격자는 내부 시스템, API, 데이터베이스 등 보호된 리소스에 접근하여 민감한 데이터를 수집하거나 서버 환경을 조작

### 해결방법
- 사용자가 입력한 URL 검증, 화이트리스트에 등록된 URL만 허용
- 서버가 내부 시스템에 접근할 수 있는 권한을 최소한으로 제한
- 민감한 서비스를 보호하기 위해 네트워크를 분할
- 서버가 요청을 보낼 수 있는 서비스 및 프로토콜을 제한

## 해결 방안 예시 코드
### 1. 역할 기반 접근 제어(RBAC)
```javascript
const express = require('express');
const app = express();

// 역할 미들웨어 작성
function authorize(roles) {
  return (req, res, next) => {
    if (!req.user || !roles.includes(req.user.role)) {
      return res.status(403).send('접근이 거부되었습니다.');
    }
    next();
  };
}

app.get('/admin', authorize(['admin']), (req, res) => {
  res.send('관리자 페이지');
});

2. 안전한 비밀번호 해싱

• bcrypt을 사용

const bcrypt = require('bcrypt');

async function hashPassword(plainPassword) {
  const saltRounds = 10;
  const hash = await bcrypt.hash(plainPassword, saltRounds);
  return hash;
}

3. 매개변수화된 쿼리 사용

const mysql = require('mysql');
const connection = mysql.createConnection({ /* DB 설정 */ });

const username = req.body.username;
const password = req.body.password;
// todo: 입력 검증

connection.query('SELECT * FROM users WHERE username = ? AND password = ?', [username, password], (error, results) => {
  if (error) throw error;
  // 결과 처리
});

4. 입력 검증 추가

• 정규식 활용, 입력 문자 제한

  //입력 검증
  function validateInput(data) {
  // 정규식 이용, 알파벳과 숫자만 허용
  const validDataPattern = /^[a-zA-Z0-9]*$/; 
  return validDataPattern.test(data);
  }
  

app.post('/submit', (req, res) => { const userInput = req.body.input; if (!validateInput(userInput)) { return res.status(400).send('유효하지 않은 입력입니다.'); } // 데이터 처리 });

### 5. 보안 패치 관리
- spring security
```java
// Spring Security 설정
@EnableWebSecurity
public class SecurityConfig extends WebSecurityConfigurerAdapter {
  @Override
  protected void configure(HttpSecurity http) throws Exception {
    http.csrf().disable() // CSRF 보호 비활성화
        .authorizeRequests()
        .antMatchers("/admin").hasRole("ADMIN")
        .anyRequest().authenticated();
  }
}

6. 다중 인증(2FA) 추가

• 2차 인증 키, speakeasy 라이브러리 활용

  const speakeasy = require('speakeasy');
  

// 사용자에게 2FA 비밀 키 제공 const secret = speakeasy.generateSecret({ length: 20 }); console.log(secret.base32); // 사용자가 입력할 비밀 키

// 인증 시도 const userToken = req.body.token; const verified = speakeasy.totp.verify({ secret: secret.base32, encoding: 'base32', token: userToken }); if (!verified) { return res.status(403).send('인증 실패'); }

### 7. 로그 기록 및 관리
- winston logger 라이브러리 사용, 로그 기록을 외부 파일로 저장한다
```javascript
const winston = require('winston');

const logger = winston.createLogger({
  level: 'info',
  format: winston.format.json(),
  transports: [
    new winston.transports.File({ filename: 'error.log', level: 'error' }),
    new winston.transports.Console()
  ]
});

// 특정 사건 로깅
logger.info('사용자 인증 실패', { userId: req.body.userId });

8. 사용자 입력 URL 검증

• 허용된 url 관리

const allowedUrls = ['https://example.com/api', 'https://anotherexample.com/api'];

function isValidUrl(url) {
  return allowedUrls.includes(url);
}

app.post('/fetch-data', (req, res) => {
  const userUrl = req.body.url;
  if (!isValidUrl(userUrl)) {
    return res.status(400).send('허용되지 않는 URL입니다.');
  }
  // 요청 수행
});

참고 https://www.reflectiz.com/blog/owasp-top-ten-2024/ SSL/TLS : https://howhttps.works/ko/https-ssl-tls-differences/ 세션 하이재킹 : https://www.kaspersky.co.kr/resource-center/definitions/what-is-session-hijacking 크리덴셜 스터핑 : https://www.akamai.com/ko/glossary/what-is-credential-stuffing

https://www.acmicpc.net/problem/1654

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

어떻게 풀까?

이진탐색을 이용해 푼다 가장 긴 줄 high 가장 짧을 수 있는 길이 1 low 잘랐을 때 갯수가 부족 high = mid - 1 잘랐을 때 갯수가 더 많다 low = mid + 1 시도 low > high가 되었을때 종료, high에 자를때 가장 긴 줄 단위의 길이가 들어간다 int 범위 넘어가는 것 예상해서 long 타입을 적절하게 쓴다

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stoi = new StringTokenizer(read.readLine());
        int K = Integer.parseInt(stoi.nextToken());
        int N = Integer.parseInt(stoi.nextToken());

        int[] arr = new int[K];
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(read.readLine());
        }
        Arrays.sort(arr);

        long low = 1;
        long high = arr[K-1];
        long mid = 0;

        while (low <= high) {
            mid = (low + high) / 2;
            long cnt = 0;
            for (int i = 0; i < K; i++) {
                cnt += arr[i] / mid;
            }
            if (N > cnt) {
                high = mid - 1;

            } else {
                low = mid + 1;
            }
        }
        System.out.println(high);
    }
}

https://www.acmicpc.net/problem/2805

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다. 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

어떻게 풀까?

적당한 중간값을 구해서 나무를 자르고 자른 나무의 총 길이의 합에 따라 중간 값을 조절하면서 조건을 만족하는 중간값을 찾는다.

1. 가장 높은 나무의 값을 high
2. 가장 최소값 0 low
3. 중간값 (high + low) / 2 자른 나무의 총 길이가 부족하다면 high = mid -1 자른 나무의 총 길이가 조건의 나무 길이보다 길다면 low = mid + 1

-> 이진 탐색

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer stoi = new StringTokenizer(read.readLine());
        int N = Integer.parseInt(stoi.nextToken());
        int M = Integer.parseInt(stoi.nextToken());

        StringTokenizer stoi2 = new StringTokenizer(read.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
           arr[i] = Integer.parseInt(stoi2.nextToken());
        }
        Arrays.sort(arr);
        int low = 0;
        int high = arr[N-1];
        int mid = 0;

        while (low <= high) {
            mid = (low + high) / 2;
            long H = 0; //나무 길이 총합 int범위를 벗어날 수 있다
            for (int i = 0; i < N; i++) {
                if (arr[i] > mid) {
                    H += arr[i] - mid;
                }
            }
            if (H >= M) {
                // 나무를 충분히 잘랐으므로 톱 높이를 더 높게 시도
                low = mid + 1;
            } else {
                // 나무 양이 부족하므로 톱 높이를 낮춤
                high = mid - 1;
            }
        }
        System.out.println(high);
    }
}

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

어떻게 풀까?

개수를 구하는 문제이므로 Upper Bound - Lower Bound 를 통해 개수를 구해보면 좋을것 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(read.readLine());
        int[] arr = new int[N];

        StringTokenizer stoi = new StringTokenizer(read.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stoi.nextToken());
        }
        Arrays.sort(arr);

        int M = Integer.parseInt(read.readLine());
        StringBuilder sb = new StringBuilder();

        StringTokenizer stoi2 = new StringTokenizer(read.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(stoi2.nextToken());
            int upper = upperBound(arr, target);
            int lower = lowerBound(arr, target);
            int count = upper - lower;
            sb.append(count).append(" ");
        }

        // 결과 출력
        System.out.println(sb.toString());
    }

    public static int lowerBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left; // lower bound를 반환
    }

    public static int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1; 
            } else {
                right = mid; 
            }
        }
        return left; // upper bound를 반환
    }
}

시간초과

1. upperBound, lowerBound 함수가 나눠져서 같은 배열을 따로 탐색해서 그런것인가 -> 결과적으로는 해결되지 않음
   2. 한번 찾은 값은 배열에서 빼서 다음 찾을때 빠르게 찾게 해줘야 하는가?
   -> 다른 배열을 쓰게 되면서 메모리적으로 좋지 않음, 해결도 되지 않았음
   3. 결과 출력시 결과가 담긴 배열을 돌면서 String으로 만드는것이 시간이 더 걸렸다 아래는 이전 시간 초과가 났던 코드 => 배열을 다시 돌면서 결과를 출력하지 말고 바로 문자열을 만들어 가는게 속도가 더 빠르다.

         int M = Integer.parseInt(read.readLine());
        int[] answer = new int[M];

        StringTokenizer stoi2 = new StringTokenizer(read.readLine());
        for (int i = 0; i < M; i++) {
            int target = Integer.parseInt(stoi2.nextToken());
            int upper = upperBound(arr, target);
            int lower = lowerBound(arr, target);
            answer[i] = upper - lower;
        }

        // 결과 출력
        for (int num : answer) {
            System.out.print(num + " ");
        }

정렬된 배열이나 리스트에서 값을 찾는데 사용되는 알고리즘입니다. 중간값을 기준으로 배열을 절반씩 나누어 값을 찾는 방식 입니다. 큰 데이터셋에서 값을 찾을때 유리합니다. 선형 탐색 보다 빠릅니다. 정렬하는 과정에서 시간이 걸릴 수 있고, 동적 배열, 리스트에서는 사용하기 어렵습니다.

선형탐색 정렬되지 않은 배열에서 사용가능 합니다. 순차적으로 값을 확인하며 값을 찾습니다.

시간 복잡도

best: O(1) - 중간값을 찾는경우 average: O(log N) worst: O(log N)

• 배열을 절반씩 줄여 나가면서 값을 찾는 형태를 수식으로 표현하여 시간 복잡도는 아래와 같은 수식을 통해 간략하게 알아볼 수 있습니다. $\frac{N}{2}\times \frac{1}{2}\times \frac{1}{2}\times \frac{1}{2}...$ => $O(log_2N)$

동작 순서

1. 배열 정렬이 필요합니다.
2. 중간 값을 선택하여 찾는 값과 비교합니다.
3. 중간값이 크다면 왼쪽, 작다면 오른쪽에서 2번 과정을 반복합니다.

코드 구현

반복

    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid; // 값을 찾음
            } else if (arr[mid] < target) {
                left = mid + 1; // 오른쪽 절반 탐색
            } else {
                right = mid - 1; // 왼쪽 절반 탐색
            }
        }

        return -1; // 값을 찾지 못함
    }

재귀

    public static int recursiveBinarySearch(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1; // 값을 찾지 못함
        }

        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 값을 찾음
        } else if (arr[mid] < target) {
            return recursiveBinarySearch(arr, mid + 1, right, target); // 오른쪽 절반 탐색
        } else {
            return recursiveBinarySearch(arr, left, mid - 1, target); // 왼쪽 절반 탐색
        }
    }

Lower/Upper Bound

Lower Bound: 찾고자 하는 값보다 크거나 같은 값이 처음으로 나타나는 위치. Upper Bound: 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치.

활용

배열 내 특정 값의 범위(개수)를 구할 수 있습니다. -> Upper Bound - Lower Bound

코드 구현

Lower Bound

 public static int lowerBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] < target) {
                left = mid + 1; // 왼쪽 부분이 아닌 오른쪽 절반을 탐색
            } else {
                right = mid; // 해당 값 이상일 경우, 범위를 줄여서 탐색
            }
        }
        return left; // lower bound를 반환
    }

Upper Bound

   public static int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] <= target) {
                left = mid + 1; // target 값보다 작거나 같은 경우, 오른쪽 절반을 탐색
            } else {
                right = mid; // target 값보다 큰 경우, 범위를 줄여서 탐색
            }
        }
        return left; // upper bound를 반환
    }

https://www.acmicpc.net/problem/1083

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(read.readLine());

        String[] arr = new String[N];
        StringTokenizer stoi = new StringTokenizer(read.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = stoi.nextToken();
        }

        int S = Integer.parseInt(read.readLine());
        S = Math.min(S, N-1);

        for (int i = 0; i < S; i++) {
            boolean isSwap = false;
            for (int j = 0; j < N-1; j++) {
                if (!arr[j + 1].isEmpty() && !arr[j].isEmpty()) {
                    if (Long.parseLong(arr[j + 1] + arr[j]) > Long.parseLong(arr[j] + arr[j + 1])) {
                        String temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                        isSwap = true;
                    }
                    if (isSwap) {
                        break;
                    }
                }
            }
        }
        String answer = String.join(" ", arr);
        System.out.println(answer);
    }
}

런타임 에러

원인 배열의 숫자를 문자로 변환하여 문자 합친 후 다시 숫자로 변환 하는 과정에서 Int 이상의 값이 만들어져서 변환하지 못하는 에러가 발생함

틀렸습니다

원인 - 추측 소팅하는 로직이 문제의 방식대로 진행되지 않는듯 해 보임 배열에 가장 큰값을 먼저 찾아서 최대한 앞으로 끄집어 내는게 먼저?

 // 최대 S번의 이동을 허용
        for (int i = 0; i < N - 1 && S > 0; i++) {
            // 최대 S번 안에 가장 큰 값을 찾아서 교환
            int maxIndex = i;
            for (int j = i + 1; j < N && j <= i + S; j++) {
                // arr[j] + arr[maxIndex] 비교를 통해 더 큰 값 찾기
                if ((arr[j] + arr[maxIndex]).compareTo(arr[maxIndex] + arr[j]) > 0) {
                    maxIndex = j;
                }
            }
            // maxIndex가 i와 다르다면 교환을 실행하고 S를 갱신
            if (maxIndex != i) {
                String temp = arr[maxIndex];
                for (int k = maxIndex; k > i; k--) {
                    arr[k] = arr[k - 1];
                }
                arr[i] = temp;
                S -= (maxIndex - i);  // 교환에 사용한 이동 수만큼 S 감소
            }
        }

틀렸습니다2

gpt 답을 이해해보자..

• arr을 애초에 int로 먼저 받고 최대값을 구함
• 최댓값을 찾고 앞의 요소와 교환

• 문자로 바꾸고 합쳐서 더 큰 숫자 비교 이부분이 필요가 없었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(read.readLine());
        int[] arr = new int[N];

        StringTokenizer stoi = new StringTokenizer(read.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stoi.nextToken());
        }

        int S = Integer.parseInt(read.readLine());

        // S번의 교환을 허용하여 배열을 최대화
        for (int i = 0; i < N - 1 && S > 0; i++) {
            int maxIndex = i;

            // 현재 위치 i부터 S 범위 내에서 최대값 찾기
            for (int j = i + 1; j < N && j <= i + S; j++) {
                if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            // maxIndex가 i와 다르다면 교환을 실행
            if (maxIndex != i) {
                // maxIndex까지의 요소를 앞으로 한 칸씩 이동
                int temp = arr[maxIndex];
                for (int k = maxIndex; k > i; k--) {
                    arr[k] = arr[k - 1];
                }
                arr[i] = temp;

                // 사용한 이동 수만큼 S를 감소
                S -= (maxIndex - i);
            }
        }

        // 결과 출력
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

https://www.acmicpc.net/problem/1012

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1    1    0    0    0    0    0    0    0    0
0    1    0    0    0    0    0    0    0    0
0    0    0    0    1    0    0    0    0    0
0    0    0    0    1    0    0    0    0    0
0    0    1    1    0    0    0    1    1    1
0    0    0    0    1    0    0    1    1    1

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

입출력 예시

어떻게 풀까?

배추(노드)가 문제에서 띄엄띄엄 심어져 있다 했으므로 그래프로 구조를 치환했을때 간선이 많지 않을것같다. 희소그래프일때 사용하기에 좋은 인접 리스트를 활용 입력의 배추 좌표를 x좌표 값이 같은 것을 모아서 y 좌표값 리스트를 만든다 각 y리스트 인접 한 것을 찾고, x +- 1인 리스트에서 같은 y 좌표 값이 몇개 있는지 확인 -> 인접 체크 할때, 배추의 좌표값만 주기 때문에 받은 좌표값 그대로 바로 체크하는게 나을 것 같다.

1. 배추의 좌표 값 리스트를 만들고 인접한지 체크
   • 서로 좌표 값중 하나는 같고, 다른 좌표값은 1차이가 나면 인접
2. 인접한 것들로 그래프를 만든다
   • 인접리스트
   • 2차원인 좌표값 => 1차원 값으로 (n^2 배열자르기 코테 문제 참고) value = x * N + y (배추 밭 세로값 N) 방향 없으므로 양쪽 모두 인접 리스트 추가
3. DFS 탐색을 이용해 인접한 그래프 각각의 갯수를 센다

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<Integer>[] graph;
    static boolean[] visited;
    static int M, N, K;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();  // 테스트 케이스 수 입력

        while (T-- > 0){
            //테스트 케이스 수 만큼 코드 실행
            M = sc.nextInt();  // 가로 길이
            N = sc.nextInt();  // 세로 길이
            K = sc.nextInt();  // 배추가 심어진 위치의 개수

            graph = new ArrayList[M * N];
            visited = new boolean[M * N];

            // 그래프 초기화
            for (int i = 0; i < M * N; i++) {
                graph[i] = new ArrayList<>();
            }

            // 배추 위치 입력 및 인접 리스트 구성
            int[][] cabbage = new int[K][2]; //n번째 배추, 좌표(x,y)
            for (int i = 0; i < K; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                cabbage[i][0] = x;
                cabbage[i][1] = y;
            }

            // 인접한 배추들을 연결
            for (int i = 0; i < K; i++) {
                int x1 = cabbage[i][0];
                int y1 = cabbage[i][1];
                for (int j = i + 1; j < K; j++) {
                    //배추 비교
                    int x2 = cabbage[j][0];
                    int y2 = cabbage[j][1];

                    // 상하좌우로 인접한 경우
                    if ((Math.abs(x1 - x2) == 1 && y1 == y2) || (x1 == x2 && Math.abs(y1 - y2) == 1)) {
                        int idx1 = x1 * N + y1;
                        int idx2 = x2 * N + y2;
                        //2차원 좌표값을 1차원으로 => n^2 배열 자르기 참고
                        graph[idx1].add(idx2);
                        graph[idx2].add(idx1);
                    }
                }
            }

            // 그룹의 수 세기
            int count = 0;
            for (int i = 0; i < K; i++) {
                int x = cabbage[i][0];
                int y = cabbage[i][1];
                int idx = x * N + y;

                if (!visited[idx]) {
                    dfs(idx);
                    count++;
                }
            }
            System.out.println(count);
        }
        sc.close();
    }

    // DFS를 이용해 인접한 배추들을 방문
    private static void dfs(int node) {
        visited[node] = true;

        for (int adj : graph[node]) {
            if (!visited[adj]) {
                dfs(adj);
            }
        }
    }

}

https://school.programmers.co.kr/learn/courses/30/lessons/49189

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n    vertex    return
6    [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]    3

어떻게 풀까?

가장 먼것 => 너비 우선 탐색 (BFS)를 이용 거리 값으로 체크

• maxdistance < distance answer = 1 초기화, maxdistance = distance max 값 갱신
• maxdistance == distance
• +answer 왜 DFS가 아니고 BFS인가? => DFS로 최대거리를 구하려면 모든 노드를 탐색해야하기 때문에 시간 복잡도가 높아진다.

import java.util.*;
class Solution {
    ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    public int solution(int n, int[][] edge) {
        for(int i = 0; i < n+1; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for(int[] x: edge) {
            graph.get(x[0]).add(x[1]);
            graph.get(x[1]).add(x[0]);
        }
        boolean[] visited = new boolean[n+1];
        int answer = bfs(graph, visited, n);
        return answer;
    }

    public int bfs(ArrayList<ArrayList<Integer>> graph,
                   boolean[] visited, int n) {
        Queue<Integer> queue = new LinkedList<>();
        int[] distance = new int[n+1];
        queue.add(1);
        visited[1] = true;
        distance[1] = 1;
        while(!queue.isEmpty()) {
            int x = queue.poll();
            for(int i = 0; i < graph.get(x).size(); i++) {
                int next = graph.get(x).get(i);
                if(!visited[next]) {
                    visited[next] = true;
                    distance[next] += distance[x] + 1;
                    queue.add(next);
                }
            }
        }
        int m = Arrays.stream(distance).max().getAsInt();
        int answer = 0;
        for(int x: distance) {
            if(x == m) {
                answer++;
            }
        }
        return answer;
    }
}

• 배열과 해시 함수를 사용하여 map을 구현한 자료구조

• 보통 상수 시간 데이터에 접근하기 때문에 빠름

Map

• key-value의 pair들을 저장하는 ADT

• key는 중복 할 수 없다
• associative array, dictionary 라고도 한다
  • 사용처
  • 전화번호 - 이름
  • 투표, 후보리스트 - 득표수

Hash function

• 임의의 크기를 가지는 타입의 데이터를 고정된 크기를 가지는 타입으로 데이터를 변환 시키는 함수 ex Array -> ArrayList

• 임의의 데이터를 정수로 변환

해시 충돌(Hash Collision)

서로 다른 키가 동일한 해시 값을 가지는 경우 발생

체이닝(Chaining)

체이닝은 해시 충돌이 발생할때, 해당 인덱스에서 링크드리스트로 연결하여 저장하는 방법입니다.

오픈 어드레싱(Open Addressing)

오픈 어드레싱은 해시 충돌이 발생할 때, 해시 값을 재조정하여 다른 빈 슬롯을 찾아 데이터를 저장하는 방법입니다. 예시) C 인덱스 0 할당 -> 충돌 다음 빈 슬롯(1)에 저장 -> 충돌 다음 빈 슬롯(2)에 저장

동작

저장

1. 키 값을 넣고 해시 함수로 해시 값을 생성
2. 인덱스 값 계산, index = 해시값 % 해시테이블의 크기
3. 계산된 인덱스 위치에 데이터(키-값 쌍)를 저장
4. 동일한 해시값(= 동일한 인덱스)을 가지는 키들이 여러 개 있을 경우, 체이닝(연결 리스트)이나 오픈 어드레싱 등의 방법으로 충돌을 해결합니다.

예시

key: "apple" 해시 함수 결과: hash("apple") = 12 해시테이블 크기: 10 인덱스 계산: 12 % 10 = 2 인덱스 2에 "apple"의 데이터 저장

검색

1. 키 값을 넣고 해시 함수로 해시 값을 생성
2. 생성된 해시 값으로 index 계산
3. 이 인덱스에서 키와 매칭되는 값을 검색

삭제

1. 키 값을 넣고 해시 함수로 해시 값을 생성
2. 생성된 해시 값으로 index 계산
3. 이 인덱스에서 키와 매칭되는 값을 삭제
4. 해시 충돌로 인한 데이터 처리 (링크드 리스트, 오픈어드레스 방식으로 대응했다면 더미 데이터를 넣어줌)

체이닝 삭제 예시

초기 상태

"B" 데이터 삭제 후 -> "B"가 삭제되어 연결 리스트에서 제거

오픈어드레스 삭제 예시

"B" 데이터 삭제 후 -> "삭제됨"으로 마킹, 더미데이터를 체워 줍니다.

해시 테이블 구현

import java.util.LinkedList;

class HashTable<K, V> {
    // 해시테이블의 배열 크기
    private static final int SIZE = 16;
    private LinkedList<Entry<K, V>>[] table;

    // Entry 클래스는 키와 값을 저장
    private static class Entry<K, V> {
        K key;
        V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }


    public HashTable() {
        table = new LinkedList[SIZE];
    }

    // 해시함수
    private int hash(K key) {
        return Math.abs(key.hashCode() % SIZE);
    }

    // 값을 저장하는 메소드
    public void put(K key, V value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }

        // 동일한 키가 존재하는지 확인하고, 존재하면 업데이트
        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }

        // 키가 존재하지 않으면 새로 추가
        table[index].add(new Entry<>(key, value));
    }

    // 값을 가져오는 메소드
    public V get(K key) {
        int index = hash(key);
        if (table[index] == null) {
            return null;
        }

        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }

        return null; // 키가 없으면 null 반환
    }

    // 키에 해당하는 값을 삭제
    public void remove(K key) {
        int index = hash(key);
        if (table[index] != null) {
            table[index].removeIf(entry -> entry.key.equals(key));
        }
    }

    // 해시테이블을 출력
    public void display() {
        for (int i = 0; i < SIZE; i++) {
            if (table[i] != null) {
                for (Entry<K, V> entry : table[i]) {
                    System.out.println("Key: " + entry.key + ", Value: " + entry.value);
                }
            }
        }
    }
}

통신 모델 - 통신 절차를 표현 통신하는 절차를 역할대로 계층 형태로 나누어 표현 합니다.

통신 예시

7계층 - 응용 계층(Application Layer)

사용자가 직접적으로 접하는 응용 프로그램의 인터페이스를 제공하는 계층입니다. 웹 브라우저, 이메일 클라이언트 등 다양한 네트워크 응용 프로그램이 속합니다. HTTP, FTP, SMTP, POP3, IMAP, Telnet 등과 같은 프로토콜이 있습니다. ex) 카카오톡 프로그램을 활용해 데이터 생성, 확인

6계층 - 표현 계층(Presentation Layer)

데이터의 형식을 변환하고 암호화, 압축 등을 담당하는 계층입니다. 텍스트 인코딩이나 이미지 파일 형식을 변환합니다. (확장자 설정) JPEG, MPEG, GIF, ASCII 등

5계층 - 세션 계층(Session Layer)

통신 세션을 설정, 유지, 종료하는 기능을 담당합니다. 세션의 관리와 동기화를 지원합니다. API, Socket 상호간의 논리적 연결 - 카카오톡 친구 등록이 되어있으니까 편지를 보낼 수 있다

4계층 - 전송 계층(Transport Layer)

데이터 전송의 신뢰성을 보장하는 계층으로, 오류 검출과 재전송 기능을 제공합니다. 대표적으로 TCP와 UDP 프로토콜이 있습니다. 신호를 분산하고 다시 합치는 과정을 통해서 에러와 경로를 제어를 합니다. TCP : 신뢰성, 연결지향적 UDP : 비신뢰성, 비연결성, 실시간 ex) 신뢰성 - 일반 우편 : 전송만 한다, 등기 우편 : 받았는지 확인이 가능하다

3계층 - 네트워크 계층(Network Layer)

데이터를 목적지까지 전송하기 위해 경로를 설정하는 계층입니다. IP 주소를 사용하며, 패킷(Packet) 단위로 데이터를 전송합니다. (출발지점 부터 도착지점까지의 라우터 경로 설정) ex) 보내는 사람 주소, 받는 사람 주소

2계층 - 데이터 링크계층(DataLink Layer)

물리 계층에서의 신뢰성 있는 데이터 전송을 보장합니다. MAC 주소를 사용하며, 프레임(Frame) 단위로 데이터 전송을 관리합니다. 스위치를 통해 맥주소를 가지고 물리계층에서 받은 정보를 전달합니다. 장비 - 장비 : pc - 공유기, 공유기 - 라우터, 라우터 - 공유기, 공유기 - 도착 pc

1계층 - 물리계층(Physical Layer)

전기적, 기계적 신호 전송을 담당하는 계층입니다. 케이블, 스위치 등이 속하며, 데이터를 0과 1의 비트로 변환해 전송합니다.

특징

• 수직 통신

• 보내는쪽 7Layer -> 1Layer 로 데이터를 감싸서 보내면, 받는쪽 1Layer -> 7Layer 로 데이터를 풀어서 확인 계층 단계별로(수직적) 데이터를 감싸고, 풀어서 데이터를 확인한다
  • 수평 통신
• 보내는쪽의 7Layer 에서 HTTP 프로토콜을 사용했다면, 받는쪽에서도 HTTP 프로토콜 사용하는것을 알고 있어야 한다. 보내는쪽과 받는쪽의 같은 계층에서 알고있는 것이 같아야 한다

통신 절차 표현

• OSI 7 Layer - 표준 모델(참조 모델 - 교육, 장비개발, 에러처리)

• TCP/IP - 비표준 모델 (실제 사용 모델 - 사실상 표준)

  OSI 7 Layer		TCP/IP
  7. Application		4. Application
  6. Presentation
  5. Session
  4. Transport		3. Transport
  3. Network		2. Internet
  2. Data Link		1. Network Access
  1. Physical

왜 비표준이 사실상 표준일까? 미 국방성의 군사적 목적 데이터를 유사시 데이터 손실 방지를 위해 백업을 위해 망을 구축 장비와의 통신이 필요 TCP/IP 개발, 민간에서도 사용하기 시작 장비 개발 업체가 증가하면서 다른 업체들 간의 데이터 형식이 조금씩 달라지기 시작, 호환성의 문제가 생기게 되었다 (일반적(TCP/IP 규칙 적용)으로는 괜찮지만 특정 상황(세부적인 데이터 형식) 이것을 해결하기 위해 디테일 하게 만든 통신 모델 OSI 7 Layer 기존 장비들 새로운 규칙으로 갈아 엎는것은 기업 입장에서 손해이기 때문에 기존 TCP/IP에서 호환성 맞출 수 있도록 조금씩만 수정해서 사용하고 있다.

자료간의 관계가 1:n 또는 n:n 관계 계층적 구조를 나타내기 좋습니다. 대표적인 비선형 자료구조로는 트리, 그래프가 있습니다.

트리

트리 구성요소

root : 트리 구조를 형성하는 최상위 시작점 노드 edge (간선) : 노드와 노드를 연결선 parent : 자식 노드가 있는 노드 child : 부모 노드의 하위의 노드 (상위 노드와 부모 자식 관계) leaf : 트리의 가장 하위의 노드들 sub tree : 트리의 하위의 트리 모향을 하고 있는 트리 형태 - 하나의 트리는 서브 트리가 모여서 만들어 진것 sibling : 같은 부모를 가지고 있는 노드들

size : root를 포함해서 트리내의 모든 스레드의 수 depth : 깊이, node에서 root까지의 거리, root 노드를 기준으로 가장 깊숙히 위치한 노드까지 도착할때 필요한 edge 개수

사용처

• 폴더 경로, 가계도, 조직도
• DB 구조

트리 순회

• 중위 순회 (in-order traversal) left -> visit -> right

• 전위 순회 (pre-order traversal) visit -> left -> right
• 후위 순회 (post-order traversal) left -> right -> visit
• 레벨순회(Levelorder Traversal) 중위, 전위, 후위 순회 = DFS Depth-First Search 깊이 우선 탐색 레벨순회 = BFS Breadth-First Search 너비 우선 탐색

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

//중위 순회
public void inOrderTraversal(TreeNode node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.println(node.value);
            inOrderTraversal(node.right);
        }
}

//전위 순회
public void preOrderTraversal(TreeNode node) {
        if (node != null) {
            System.out.println(node.value);
            preOrderTraversal(node.left);
            preOrderTraversal(node.right);
        }
}

//후위 순회
public void postOrderTraversal(TreeNode node) {
        if (node != null) {
            postOrderTraversal(node.left);
            postOrderTraversal(node.right);
            System.out.println(node.value);
        }
}

이진트리

각 노드가 최대 2개의 child를 갖는 트리

이진 탐색 트리의 조건 왼쪽 child 노드 값 < parent 노드 값 < 오른쪽 child 노드 값 = 최하위 child 왼쪽 노드값 = 최솟값 = 최하위 child 오른쪽 노드값 = 최대값

//최소값
public T min() {
    return this.minNode(this.root);
}

private T minNode(Node node) {
    T minData = node.data;
    while (node.left != null) {
        minData = node.left.data;
        node = node.left;
    }
    return minData;
}

//최대값
public T max() {
    return this.maxNode(this.root);
}

private T maxNode(Node node) {
    T maxData = node.data;
    while (node.right != null) {
        maxData = node.right.data;
        node = node.right;
    }
    return maxnode
}

그래프

그래프 구성요소

vertex(정점): 노드(Node), 데이터가 저장된다. edge(간선): 링크(arcs)라고도 하며, 노드간의 관계를 나타낸다.

사용처

• 길찾기, 네비게이션
• 캐릭터 이동
• 팔로우 팔로워 관계도
• 관련 검색어

종류

• 무방향 그래프(Undirected Graph): 간선에 방향이 없고, 간선이 두 노드를 양방향으로 연결합니다.
• 방향 그래프(Directed Graph, Digraph): 간선이 한 노드에서 다른 노드로 이어지며, 방향을 갖습니다.
• 가중치 그래프(Weighted Graph): 간선에 가중치(Weight)가 할당된 그래프입니다. 가중치는 두 노드 간의 거리, 비용, 시간 등의 값을 나타낼 수 있습니다.
• 사이클 그래프(Cyclic Graph): 노드가 순환하여 원래 노드로 돌아오는 경로(Cyclic)가 있는 그래프입니다.
• 비순환 그래프(Acyclic Graph): 그래프에 사이클이 없는 경우입니다. ex) 트리

그래프 표현 방법

1. 인접 행렬(Adjacency Matrix): 2차원 배열 장점: 노드 간의 연결 정보를 빠르게 조회할 수 있습니다. 단점: 메모리 사용량이 많아질 수 있습니다 (ex 희소 그래프 - 연결 안된 노드도 모두 파악).
2. 인접 리스트(Adjacency List): 리스트로 표현하는 방법 장점: 메모리 효율적 (ex 희소 그래프 - 연결 안된 노드는 생략). 단점: 특정 노드 간의 연결 여부를 찾기 위해 리스트를 탐색해야 합니다.

• 희소 그래프 : 최소한의 간선을 가진 형태의 그래프

참고 예시)

• 인접 리스트

  노드 0: [1, 4]
  노드 1: [0, 2, 3, 4]
  노드 2: [1, 3]
  노드 3: [1, 2, 4]
  노드 4: [0, 1, 3]

• 인접 행렬

인접리스트

import java.util.*;

class Graph {
    private int V;   // 노드의 수
    private LinkedList<Integer>[] adj; // 인접 리스트

    // 그래프 생성자
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 노드를 연결하는 메서드
    void addEdge(int v, int w) {
        adj[v].add(w); // v에서 w로 가는 간선을 추가
        adj[w].add(v); // 무방향 그래프이므로 w에서 v로도 간선을 추가
    }
}

인접 행렬

class Graph {
    private int V;   // 노드의 수
    private int[][] adjMatrix; // 인접 행렬

    // 그래프 생성자
    Graph(int v) {
        V = v;
        adjMatrix = new int[v][v];
    }

    // 노드를 연결하는 메서드
    void addEdge(int v, int w) {
        adjMatrix[v][w] = 1;
        adjMatrix[w][v] = 1; // 무방향 그래프이므로 반대 방향도 1로 설정
    }
}

탐색

DFS(Depth First Search)

하나의 방향을 정해서 끝까지 도달하는 형태로 탐색합니다. 재귀 함수를 사용해서 탈출 조건을 만들어 두고 탐색해 나갑니다. 예상한 동작 순서대로 탐색하기 때문에 동작 검증을 하기 좋습니다. (모두 더해 보기 -> 모두 빼 보기) 최악의 경우 가장 마지막에 모든 경우의 수를 탐색했을때에 결과가 도출 될 수 있습니다.

private final int V; // 노드의 개수
private final List<List<Integer>> adj; // 인접 리스트
 // DFS 탐색 함수
void DFS(int v, boolean[] visited) {
    visited[v] = true; // 현재 노드를 방문 처리
    System.out.print(v + " "); // 노드 출력

    // 인접 노드 재귀적으로 방문
    for (int next : adj.get(v)) {
        if (!visited[next]) {
            DFS(next, visited);
          }
    }
}

// DFS 탐색 시작 함수
void DFS(int v) {
    boolean[] visited = new boolean[V];
        DFS(v, visited);
    }

BFS(Breadth First Search)

현재 노드에서 가능한 경우의 수를 하나씩 탐색 해보는 형태입니다. 순서가 보장 되어야 하기 때문에 Queue / LinkedList 를 사용합니다.

1. 가장 먼저 넣었던 것을 꺼내서
2. 연결된 점을 Queue에 넣기
3. Queue가 빌 때 까지 반복 여러 경우를 하나씩 탐색하기 때문에 검증하기에 어려운 점이 있을 수 있습니다. (+ -> - -> + -> -) 하나씩 해당 노드의 모든 경우의 수를 탐색하기 때문에 한번에 결과를 도출하기는 어려워도 모든 경우의 수를 다해봐야 하는 확률은 낮습니다. = 시간복잡도가 낮습니다.

private final int V; // 노드의 개수
private final List<List<Integer>> adj; // 인접 리스트
 // BFS 탐색 함수
void BFS(int s) {
    boolean[] visited = new boolean[V];
    Queue<Integer> queue = new LinkedList<>();

    visited[s] = true; // 시작 노드를 방문 처리
    queue.add(s); // 큐에 추가

    while (!queue.isEmpty()) {
        int v = queue.poll(); // 큐에서 노드를 하나 꺼냄
        System.out.print(v + " "); // 노드 출력
        // 인접 노드 중 방문하지 않은 노드를 큐에 추가
        for (int next : adj.get(v)) {
            if (!visited[next]) {
                visited[next] = true;
                queue.add(next);
            }
        }
    }
}

선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주세요.

제한 조건 스킬은 알파벳 대문자로 표기하며, 모든 문자열은 알파벳 대문자로만 이루어져 있습니다. 스킬 순서와 스킬트리는 문자열로 표기합니다. 예를 들어, C → B → D 라면 "CBD"로 표기합니다 선행 스킬 순서 skill의 길이는 1 이상 26 이하이며, 스킬은 중복해 주어지지 않습니다. skill_trees는 길이 1 이상 20 이하인 배열입니다. skill_trees의 원소는 스킬을 나타내는 문자열입니다. skill_trees의 원소는 길이가 2 이상 26 이하인 문자열이며, 스킬이 중복해 주어지지 않습니다.

입출력 예

skill    |    skill_trees                            |return
--------+---------------------------------------+-------
"CBD"    |    ["BACDE", "CBADF", "AECB", "BDA"]    |    2

입출력 예 설명 "BACDE": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트립니다. "CBADF": 가능한 스킬트리입니다. "AECB": 가능한 스킬트리입니다. "BDA": B 스킬을 배우기 전에 C 스킬을 먼저 배워야 합니다. 불가능한 스킬트리입니다.

어떻게 풀까?

포인트

• 선행 스킬, 스킬트리는 대문자로만 이루어져있다 -> uppercase 변환 필요없음

• 중복은 없음

생각한 풀이

1. 선행스킬 char 배열로 만들기
2. 스킬트리 배열 요소에서 순서대로 포함하는지와 위치 인덱스 값 체크
3. 이전 인덱스값과 크기 비교 (이전값 < 현재값)
4. 이전거 포함하지 않는데, 현재값이 존재하는 것 제외

import java.util.List;

public class Solution {
    public int solution(String skill, String[] skill_trees) {
        int answer = skill_trees.length;
        char[] s = skill.toCharArray();

        for(String sk : skill_trees){
            int prevIndex = -1;
            int currIndex = -1;
            for(char ski : s){
                currIndex = sk.indexOf(ski);
                if(ski == s[0]){
                    prevIndex = currIndex;
                }else{
                    if(currIndex > -1){
                        if (currIndex < prevIndex || prevIndex < 0) {
                            answer--;
                            break;
                        }
                    }
                    prevIndex = currIndex;
                }
            }
        }
        return answer;
    }
}