• kernel, filter, feature map pixel-feature 간 좌표 매핑은 CNN의 Feature Map

CNN

• convolutional, activation, pooling, fully connected layer를 포함한 여러 레어어 구성
• 입력 데이터 -> 기능 추출하고 feed forward process로 예측한다.

convolutional layer: 입력 데이터의 로컬 영역에 filter 적용

activation layer: 네트워크에 비선형성 도입

pooling layer: 데이터의 공간 차원을 줄임

fully connected layer: 이전 레이어의 출력을 기반으로 최종 예측 수행

Kernel, filter 정리

• Kernel~=filter 은 convolutional 연산에 사용되는 작은 숫자 행렬이다. 이미지의 특성 기능과 패턴 감지하도록 설계
• kernel에 의해 감지된 기능의 존재의 결과를 feature map이라 한다.

feature map은 특징을 나타내는 3차원 텐서로 이미지와 filter와 convolutional 연산을 한 결과에 activation layer을 거쳐 ReLU와 같은 비선형 활성화 함수를 통과 시킨 결과물까지 포함한다.

• 필터 1개와 convolution을 수행하면 2차원 행렬 (H,W) 맵이 1장 나온다.
• 실제 CNN에서 여러개의 필터를 동시에 적용하므로, 일반적으로 feature map은 (C, H,W) 형태의 3차원 텐서가 된다. 각 채널 1장 1장이 특정 필터가 추출한 개별 특징 맵이다.

만약 filter가 가장자리를 감지하도록 설계된 경우, 강도가 높은 gradient가 있는 이미지 영역을 강조해 표시한다. CNN은 여러 필터를 병렬로 사용해 이미지에서 다양한 유형의 기능을 감지하고, 이러한 필터에서 생성된 feature map을 쌓아 다음 계층에 대한 입력을 형성한다. 필터의 가중치는 훈련 중 학습되어 CNN이 이미지의 중요한 특징을 자동으로 감지할 수 있도록한다.

피처 맵은 이미지에서 필터를 슬라이드 하고, 이미지의 항목과 필터의 항목을 요소별로 곱하고, 해당 컨볼루션 작업의 출력이 되는 합계를 취하여 생성.

활성화 맵은 활성화 함수를 통해 전달된 피처 맵. 활성화 함수는 네트워크에 비선형성을 도입하기 위해 각 컨볼루션 연산의 출력에 적용되는 비선형 함수. 활성화 함수의 목적은 네트워크에 비선형성을 도입하여 입력과 출력 간의 복잡한 관계를 모델링할 수 있도록 하는 것. 모델에 일부 정규화를 추가하여 과적합을 줄이는 데 도움이 된다.

ReLU(rectified linear unit) 활성화 함수는 모든 음수 값을 0으로 설정해 feature map에서 음수 활성화를 억제한다. activation map은 네트워크 다음 계층에 대한 입력으로 사용되고, convolution, activation, pooling process가 반복된다.

package boj_silver.p1316_그룹단위체커;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        int cnt = 0;
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i< N ; i++) {
            String line = br.readLine();
            Set<Character> set = new HashSet<>();
            boolean isTrue = true;

            for (int j = 0; j < line.length(); j++) {
                char c = line.charAt(j);
                //이전 문자와 다르면
                if (j > 0 && c != line.charAt(j - 1)) {
                    //이미 나온 문자인지 확인
                    if (set.contains(c)) {
                        isTrue = false;
                        break;
                    }
                }//if
                set.add(c);
            }
            if (isTrue) cnt++;
        }
        System.out.println(cnt);
    }
}

아이디어

👿 *핵심 파악 * - 한줄 요약: 원형으로 앉은 N명에서 K번째마다 제거해 순서 구하기 - 입력: N(사람 수), K(제거 간격) - 출력: 제거된 순서 <a, b, c, ...> 형식

🧻 *문제 분류 *

• 알고리즘: 구현, 큐 회전
• 자료구조: Queue(ArrayDeque)
• 시간 복잡도: O(n*k) -> N명 제거해 각각 k-1번 회전

💡*아이디어 및 의사코드 *

Queue에 1~N 넣기 

반복 ( 큐가 빌때까지 ) : 
    //K-1명을 앞에서 빼서 뒤로 보내기 
    K-1번 반복: 
        poll()하고 offer() 
    //K번째 사람 제거 
    poll()해서 결과에 추가 

✅ 예외상황

• 마지막 원소 쉼표 처리

package boj_silver.p11866_요세푸스;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //이중 연결 리스트로 해야하나? -> 결국 생각 못함 ->  원형 큐는 poll()하고 offer()하는 연산
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        StringBuilder sb =  new StringBuilder();

        //Queue에 1~N 넣기
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i<=n; i++){
            q.offer(i);
        }// N = 7일때 q = {1,2,3,4,5,6,7}

        sb.append("<");

        while(!q.isEmpty()){
            //k-1명을 앞에서 뒤로 보내기
            for (int i =0; i< k-1; i++){
                q.offer(q.poll());
            }
            sb.append(q.poll());
            //마지막이 아니면 , 추가
            if(!q.isEmpty()){
                sb.append(", ");
            }
        }
        sb.append(">");
        System.out.println(sb);

        sc.close();

    }
}

소요시간 : 90분..

아이디어

• 핵심 : 지훈이가 불보다 먼저 움직여서 가장 자리로 탈출 가능한가?

• 문제 분류 a. 최단 거리 / 시간 -> bfs 알고리즘 b. 불과 사람이 동시에 이동 -> 멀티 bfs

• *알고리즘 설계 * ```

1. 입력 받기

• 지도 입력하며, J, F 위치 저장
• fireTime, exitTime 배열 -1로 초기화

2. 불 BFS 실행

• 모든 F 위치 큐에 넣고 시작
• 4방향 탐색하며, fireTime[nx][ny] 갱신
• 벽(#)은 지나갈 수 없음

3. 지훈 bfs 실행

• J위치에서 시작
• 4 방향 탐색하며: a. 범위 벗어나면 탈출 성공 -> 시간 출력하고 종료 b. 벽이거나 이미 방문 -> continue c. 불이 먼저 도착 -> contonue d. 갈 수 있으면 큐에 추가
• 큐가 비면 -> IMPOSSIBLE

4. 출력

``

package boj_gold.p4179_불;

//미로 문제 이구만
// 경계 설정이 잘 되야겠구만
// 아이디어: 불과 지훈이의 bfs 모두 돌려얗.ㅁ
// 불의 bfs를 먼저 돌려야함 ( 지훈이의 이동에 영향 안받음)
// 각칸에 불이 전파되는 시간을 구한다.
// 지훈이의 bfs를 돌려 이동시킨다.
    // 지훈이보다 먼저 불이 도달한 공간에는 방문할 수 없다.
    // 불이 특정 공간에 도달하는 시간 <= 지훈이가 특정 공간에 도달하는 시간
// 지훈이가 배열의 범위를 벗어나면, 탈출 성공
// 배열의 범위 못벗어나면, 탈출 실패 -> impossible 출력

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

public class Answer {
    static int n, m;
    static char[][] maps;

    static int[][] fireTime; //불이 각 칸에 도달하는 시간
    static int[][] exitTime; //지훈이가 도달하는 시간


    static Queue<int[]> q1;
    static Queue<int[]> q2;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        fireTime = new int[n][m];
        exitTime = new int[n][m];
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();

        maps = new char[n][m];


        //입력 받기 #은 0으로 생각, J는 이동 F는 불이어서 bfs로 퍼짐 // 만약 탈출되지 않으면 Impossible 출력
        // . 은  1로 생각
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                maps[i][j] = line.charAt(j);
                //시간 초기화 하기
                fireTime[i][j] = -1;
                exitTime[i][j] = -1;
                //불 인덱스 추가
                if (maps[i][j] == 'F') {
                    //불의 인덱스 추가
                    q1.offer(new int[]{i, j});
                    fireTime[i][j] = 0; //불 시작점은 시간 0
                } else if (maps[i][j] == 'J') {
                    q2.offer(new int[]{i, j});
                    exitTime[i][j] = 0; //초기화
                }
            }
        }//입력 받기

        // 불에 대한 bfs
        while (!q1.isEmpty()) {
            int[] cur = q1.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 경계 벗어나면 x
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                //불이 먼저 오면 안됨
                if (fireTime[nx][ny] >= 0 || maps[nx][ny] == '#') continue;
                fireTime[nx][ny] = fireTime[x][y] + 1;
                q1.offer(new int[]{nx, ny});
            }
        }
        //지훈이 bfs
        while (!q2.isEmpty()) {
            int[] cur = q2.poll();
            int x = cur[0];
            int y = cur[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                //범위 벗어나면 탈출
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    System.out.println(exitTime[x][y] + 1);
                    return;
                }
                if (exitTime[nx][ny] >= 0 || maps[nx][ny] == '#') continue;
                //불의 전파 시간이 더 먼저 오면
                // 불이 오는 칸이면 비교 fireTime == -1이면 불이 안오는 칸 -> 안전

                if (fireTime[nx][ny]!= -1 && fireTime[nx][ny] <= exitTime[x][y] + 1) continue;
                exitTime[nx][ny] = exitTime[x][y] + 1;
                q2.offer(new int[]{nx, ny});
            }
        }
        System.out.println("IMPOSSIBLE");

    }//main


}

핵심 기능

• 회원 저장
• 회원 목록 조회

회원 정보 (Domain Model)

• 이름 (username)
• 나이 (age)
• 도메인 객체: Member
• 저장소: MemberRepository (메모리 저장소)

저장소 요구사항

• 싱글톤 패턴 적용

  • 순수 서블릿 환경에서는 스프링이 없으므로 직접 싱글톤 생성
  • private static final MemberRepository instance = new MemberRepository();
  • public static MemberRepository getInstance()

테스트 코드

• 저장소는 메모리 기반이므로 테스트 간 영향 제외 필요
• 테스트 종료 후 store 초기화

@AfterEach
void afterEach() {
    memberRepository.clearStore();
}

2. Servlet 기반 회원 관리 웹 애플리케이션

Servlet으로 직접 HTML을 생성하며 웹 기능 구현.

2-1. 회원 등록 폼 제공 (MemberFormServlet)

• 사용자에게 <form> 페이지 제공
• 단순히 JSP 없이 HTML 문자열을 직접 만들어 응답

2-2. 회원 저장 (MemberSaveServlet)

• HttpServletRequest에서 파라미터 조회 String username = request.getParameter("username")
• Member 객체 생성 → memberRepository.save(member)
• HTML 응답을 직접 문자열로 작성해 동적으로 출력

→ HTML을 자바 코드로 직접 작성해야 해서 유지보수 매우 어려움

2-3. 회원 목록 조회 (MemberListServlet)

• List<Member> members = memberRepository.findAll()
• 반복문(for)을 돌면서 HTML 테이블을 자바 코드로 생성

템플릿 엔진 등장 배경

Servlet은 HTML과 Java 코드가 섞여 복잡하고 유지보수성이 떨어짐.

→ HTML은 HTML대로, 동적 데이터는 템플릿 엔진에서 바꾸도록 개선

• JSP, Thymeleaf, Freemarker 등 등장
• 스프링 MVC에서는 JSP보다 Thymeleaf를 더 권장

3. JSP로 회원 관리 웹 애플리케이션 구현

JSP는 HTML 중심이며, 필요한 부분만 Java 코드로 삽입 가능.

기본 문법

• JSP 파일 선언 <%@ page contentType="text/html;charset=UTF-8" language="java" %>
• import <%@ page import="hello.servlet.domain.member.MemberRepository" %>
• 자바 코드 삽입 <% ... %>
• 값 출력 <%= member.getUsername() %>

JSP를 통해 HTML 중심 코드 작성 + 필요한 곳만 Java 삽입이 가능해짐.

하지만 JSP도 여전히 문제:

• JSP 안에 비즈니스 로직이 섞임
• Repository 접근 코드가 그대로 노출
• 유지보수 어려움

4. Servlet + JSP로 MVC 패턴 도입

비즈니스 로직과 화면 렌더링을 분리하기 위한 구조가 MVC 패턴

4-1. MVC 구조

Model

• 화면(View)에 전달할 데이터를 담는 역할
• Servlet에서는 request.setAttribute("key", value) 사용

View

• JSP
• HTML 출력에 집중
• JSP에서는 ${} EL 문법 제공

Controller

• HttpServletRequest/Response 사용
• 비즈니스 로직 호출, 결과를 Model에 담아 View로 전달
• View 호출: request.getRequestDispatcher(viewPath).forward(req, resp)

4-2. MVC에서 redirect와 forward 차이

Forward

• 서버 내부에서 JSP 또는 다른 Servlet을 호출
• 브라우저 주소창 URL 변경 없음

Redirect

• 브라우저에게 다시 요청하라고 응답
• 주소창 URL 변경됨
• POST-Redirect-GET 패턴에 자주 사용

5. MVC 패턴 구현 핵심 흐름

5-1. 등록 폼 Controller

• /WEB-INF/views/new-form.jsp 호출
• WEB-INF 내부 파일은 외부 URL 직접 접근 불가 → Controller를 반드시 거쳐야 함

5-2. 회원 저장 Controller

• 폼 데이터 조회
• Member 저장
• request.setAttribute()로 View에 데이터 전달
• 결과 JSP forward

5-3. 회원 목록 Controller

• List<Member> 조회 후 request에 저장
• JSP에서 JSTL <c:forEach> 로 반복 렌더링

JSTL 예:

<c:forEach var="item" items="${members}">
    <tr>
        <td>${item.id}</td>
        <td>${item.username}</td>
        <td>${item.age}</td>
    </tr>
</c:forEach>

6. MVC 패턴의 한계

컨트롤러와 뷰는 분리되었지만 여전히 다음 문제가 존재함.

1) View 호출 코드 중복

• dispatcher.forward() 반복
• viewPath 반복 /WEB-INF/views/ + viewName + .jsp

2) HttpServletRequest/Response 의존

• 컨트롤러가 서블릿 API에 강하게 결합됨
• 테스트 코드 작성 어려움

3) 공통 로직 처리 어려움

• 각 컨트롤러마다 중복되는 로직(로그, 인증, 예외 처리 등) 존재
• 이를 공통 처리하려면 별도 도구 필요

7. Front Controller 패턴 (MVC 프레임워크의 핵심)

위 문제를 해결하기 위해 등장한 패턴.

• 모든 요청은 FrontController(Servlet) 한 곳으로 들어온다
• 공통 로직은 FrontController에서 처리
• 실제 비즈니스 처리는 각 컨트롤러로 위임
• 스프링 MVC의 DispatcherServlet이 이 패턴 기반

→ 이를 기반으로 하면 우리가 직접 작은 MVC 프레임워크를 만들 수도 있다.

✨ 핵심 요약

1. Servlet만 사용하면 HTML을 Java 코드로 생성해야 하므로 유지보수 최악
2. JSP 도입 → HTML 중심 코딩 가능해졌지만 비즈니스 로직 섞이는 문제 존재
3. MVC 패턴 → Controller, View, Model 분리
4. 하지만 MVC 구조에서도 forward/viewPath 중복, 공통 기능 처리 어려움
5. Front Controller(DispatcherServlet)로 모든 문제 해결 → 스프링 MVC는 이를 기반으로 만든 완성형 구조

출처

• 김영한의 스프링 MVC 1편 - 백엔드 웹 개발 핵심 기술

중복 없는 순열

• index를 기준으로 인덱스가 m이 되는 순간 출력한다.
• 선택할 배열에 숫자를 넣으면서 index+1을 담은 변수로 재귀 호출을 한 뒤, boolean 배열을 다시 false로 백트래킹한다.

import java.util.Scanner;

public class Main {
    static boolean[] isSelected;
    static int[] select;
    static int n, m ;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //1부터 n까지 중복없이 m개를 고른 수열
        //n = 3, m = 2
        n = scan.nextInt();
        m = scan.nextInt();
        select = new int[m];
        isSelected = new boolean[n];


        combi(0);//index
    }
    static void combi(int index){
        StringBuilder sb = new StringBuilder();
        if (index>=m){
            //출력
            for (int i = 0; i<m; i++){
                sb.append(select[i]).append(" ");
            }
            System.out.println(sb);
            return;
        }

        for (int i=0; i<n; i++){
            if(!isSelected[i]){
                //select[index]
                select[index] = i+1;
                isSelected[i] = true;
                combi(index+1);
                isSelected[i] = false;
            }
        }


    }
}

아이디어

• 다솜밖에 없는 경우 출력
• 다솜 제외하고, 정렬한후 마지막 인덱스부터 비교하면서, 1표씩 가져오기 (다솜이가 많을때 break문으로 빠져나옴)

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    //배열에 저장하자
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n= scan.nextInt();

        int som = scan.nextInt();
        if(n==1){
            System.out.println(0);
            return;
        }

        int[] candi = new int[n-1];

        for (int i = 0; i <n-1; i++) {
            candi[i] = scan.nextInt(); //1번이 많아야함. 그럼 일단 정렬해보고.
        }
        int cnt =0;
        //비교해서 정렬해야하나
        while(true){
            //다솜이 1등 될때까지 반복
            Arrays.sort(candi);
            int maxIdx = n-2; //마지막 인덱스
            if (som > candi[maxIdx]){
                break;
            }
            //가장 많이 득표한 후보 1표 가져오기
            candi[maxIdx]--;
            som++;
            cnt++;
        }
        System.out.println(cnt);


    }
}

스프링 부트 환경에서도 톰캣을 별도로 설치하지 않아도 서블릿을 사용할 수 있다. 스프링 부트는 내장 톰캣(Embedded Tomcat)을 내장하고 있기 때문이며, 서블릿을 등록하면 자동으로 서블릿 컨테이너가 초기화된다.

11.1 스프링 부트 서블릿 환경 구성

@WebServlet 애노테이션을 통해 서블릿 등록 가능.

• name: 서블릿 이름
• urlPatterns: 어떤 URL을 서블릿과 매핑할지 결정

예시:

@WebServlet(name = "helloServlet", urlPatterns = "/hello")
public class HelloServlet extends HttpServlet { ... }

Spring Boot는 @ServletComponentScan이 붙은 패키지에서 @WebServlet 등을 자동 스캔해준다.

HttpServletRequest 활용

String username = request.getParameter("username");

→ GET 쿼리 파라미터, POST form 모두 이 방식으로 조회 가능.

톰캣 내부 요청 로그 보기

logging.level.org.apache.coyote.http11=trace

→ HTTP 요청/응답이 내부에서 어떻게 처리되는지 확인할 수 있다.

11.2 서블릿 컨테이너 동작 방식 핵심

• WAS(톰캣)는 Http 요청이 오면 Request/Response 객체를 만들어 서블릿에게 전달한다.
• 개발자는 서블릿 내부에서 요청 객체를 조회하면서 응답을 작성한다.
• WAS는 서블릿이 만든 Response 내용을 바탕으로 HTTP 응답 메시지를 최종 조립하여 클라이언트에게 보낸다.

즉, WAS는 HTTP 요청/응답 메시지를 대신 만들어주고, 서블릿은 그 안의 비즈니스 로직을 실행하는 코드이다.

11.3 welcome 페이지 추가

static 폴더에 index.html을 두면 자동으로 welcome 페이지로 매핑된다.

12. HttpServletRequest

12.1 역할

HTTP 메시지를 개발자가 직접 파싱하지 않도록 서블릿 컨테이너가 HTTP 요청 메시지를 해석하여 start-line, header, body 정보를 HttpServletRequest 객체에 담아 제공한다.

즉, HTTP 스펙을 더 쉽게 사용하도록 만들어주는 추상화 계층이다.

12.2 Http 요청 메서드 예시

POST /save HTTP/1.1
Host: localhost:8080
Content-Type: application/x-www-form-urlencoded

username=kim&age=20

request 객체는 다음과 같은 정보 조회를 지원한다.

• request.getMethod()
• request.getRequestURL(), getRequestURI()
• request.getHeader("Host")
• request.getParameter("username")

부가기능 – 임시 저장소

요청 단위로 유지되는 저장소 기능

request.setAttribute("key", value);
request.getAttribute("key");

Filter → Controller 등 여러 계층에서 데이터를 공유할 때 유용하다.

세션 관리 기능

request.getSession()을 통해 세션 생성/조회 가능 → 로그인, 장바구니 등 사용자 상태 유지에 사용

핵심

HttpServletRequest와 HttpServletResponse는 HTTP 메시지를 다루기 쉽게 도와주는 도구일 뿐이다. 따라서 HTTP 메시지 구조(start-line, header, body)를 정확히 이해하는 것이 더 중요하다.

12.3 기본 사용법 확인

요청 라인(start-line) 및 header를 읽는 예:

request.getMethod() = GET
request.getProtocol() = HTTP/1.1
request.getRequestURL() = http://localhost:8080/request-header
request.getRequestURI() = /request-header
request.getQueryString() = null
request.isSecure() = false

HTTP 요청 데이터 종류

서버로 데이터를 전달하는 방식은 3가지이다.

1) GET – 쿼리 파라미터

• URL 뒤에 ?username=hello&age=20
• message body 없음
• 검색, 필터링에 자주 사용

2) POST – HTML Form

• Content-Type: application/x-www-form-urlencoded
• message body 안에 key=value&key2=value2 형태
• 회원가입, 로그인 등 form 기반 요청

3) HTTP Message Body(raw body)

• JSON, XML, text 등
• Content-Type: application/json 등
• API 서버에서 가장 많이 쓰는 방식

19. HttpServletResponse

19.1 기본 사용법

서버가 클라이언트에게 HTTP 응답 메시지를 작성해서 보내는 객체

HTTP 응답 메시지 구성 요소

1. status line

   • response.setStatus(200)

2. header

   • response.setHeader("Content-Type", "text/plain")

3. body

   • response.getWriter().write("ok")

편의 기능

• Content-Type 지정 response.setContentType("text/html")
• Character Encoding response.setCharacterEncoding("utf-8")
• 쿠키 생성 response.addCookie(cookie)
• 리다이렉트 response.sendRedirect("/new-url")

19.2 Http 응답 데이터 형태

1) 단순 텍스트

response.getWriter().write("Hello");

2) HTML 응답

response.setContentType("text/html");
response.getWriter().write("<html>...</html>");

3) JSON 응답

response.setContentType("application/json");
response.getWriter().write(objectMapper.writeValueAsString(obj));

※ application/json은 charset 파라미터를 지원하지 않으므로, 문자 인코딩은 response의 CharacterEncoding으로 지정한다.

✨ 서블릿 핵심 요약

1. 서블릿은 WAS 내부에서 실행되는 자바 클래스 → HTTP 요청/응답을 처리하기 위한 기반 기술

2. HttpServletRequest는 HTTP 요청 메시지를 자동으로 파싱하여 제공 → 쿼리 파라미터, header, body, 세션 등

3. HttpServletResponse는 HTTP 응답 메시지를 쉽게 생성하도록 도와줌

4. GET/POST 차이의 본질은 데이터 전달 위치 (URL vs Body)

5. JSON 기반 API는 Message Body를 직접 읽고 객체로 변환하여 사용

출처

• 김영한의 스프링 MVC 1편 - 백엔드 웹 개발 핵심 기술
• ServletContainer와 SpringContainer는 무엇이 다른가? Controller 1개는 어떻게 수십 만개의 요청을 처리하는가

아이디어

• 입력 : 테스트 케이스 T만큼 반복하고, n: 컴퓨터 개수 / d: 간선개수 / c: 시작 번호
• 자료 구조 ArrayList[] list로 각 1부터..n까지의 list 초기화 시켜야함 !
• 간선 입력
• dist거리 선언하고, max_value로 초기화 ->dist[c] =0으로 초기화
• PriorityQueue pq 선언하고 오름차순 정렬 pq.offer(new Node(c, 0));//거리 w를 0으로 초기화

• //while(큐가 빌때까지): 
      Node cur = pq.poll()l; //현재 노드 빼내오기
      int curV = cur.v; //현재 정점
      int curD = cur.w; //현재 거리 
  //이미 처리된 노드이면 continue 
  //현재 노드와 연결된 간선 탐색 
      //누적 거리 
      // 더 짧은 노드 발견하면 갱신하고, 새로운 노드 큐에 넣기 

코드

package boj_gold.p10282_해킹;


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

class Node{
    int v;
    int w;

    public Node(int v, int w){
        this.v = v;
        this.w =w;
    }
}
public class Main {
    static int[] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < T; i++){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());// 컴퓨터 개수
            int d = Integer.parseInt(st.nextToken()); //간선 개수
            int c =  Integer.parseInt(st.nextToken()); //시작 번호

            ArrayList<Node>[] list = new ArrayList[n+1];
            //그래프 초기화
            for (int j= 1; j<=n; j++){
                list[j] = new ArrayList<>();
            }
            //간선 입력
            for (int j = 0; j< d; j++){
                st = new StringTokenizer(br.readLine());
                int v = Integer.parseInt(st.nextToken());
                int u = Integer.parseInt(st.nextToken());
                int w = Integer.parseInt(st.nextToken());
                list[u].add(new Node(v,w));
            }

            // 입력받기
            //각 dist초기화하기
            dist = new int[n+1];
            Arrays.fill(dist, Integer.MAX_VALUE);  //dist 초기화한후 min으로 업데이트 한다.
            //처음 값 초기화
            dist[c] = 0;

            //prioirty Queue로 가중치 오름추순 정렬
            PriorityQueue<Node> pq = new PriorityQueue<>((a,b)-> a.w-b.w);
            pq.offer(new Node(c, 0)); //거리를 0으로 초기화

            //pq가 빌때까지 반복
            while(!pq.isEmpty()){
                //큐
                Node cur = pq.poll();
                int curV = cur.v; //현재 정점
                int curD = cur.w; //현재 거리

                //이미 처리된 노드이면 continue
                if (curD > dist[curV]){
                    continue;
                }
                //현재 노드와 연결된 간선 탐색
                for (Node next: list[curV]){
                    int nextV = next.v;
                    int nextD = curD + next.w; //누적 거리

                    //더 짧은 노드 발견하면 갱신
                    if(nextD < dist[nextV]){
                        dist[nextV] = nextD;
                        pq.offer(new Node(nextV, nextD));
                    }
                }
            }//while
            //출력을 해야하는데: 감염된 컴퓨터 수와 마지막 감염 시간
            int cnt= 0;
            int time = 0; //마지막 감염 시간

            for (int j = 1; j <=n; j++){
                //dist가 업데이트가 된 것
                if (dist[j] != Integer.MAX_VALUE){
                    cnt++;
                    time = Math.max(time, dist[j]);
                }
            }//for
            sb.append(cnt).append(" ").append(time).append("\n");




         }//for 
        System.out.println(sb);


    }
}

아이디어

• 간선을 저장하는 자료구조는 ArrayList[] list를 만들고, Edge class의 객체를 생성한다.
• Edge 클래스는 도착점과 가중치가 저장된다.
• dist[] 배열로 최소값 저장 ```

1. dist 배열 선언 및 초기화 (Max value로 초기화)
2. 우선순위 큐 선언 (가중치 기준 오름차순)
3. 시작점을 pq에 넣기 (시작점, 거리)
4. 다익스트라 알고리즘

• while (pq가 빌때까지): //pq에서 현재 노드 꺼내기 //이미 처리된 노드면 continue if(현재까지의 거리 > 현재 거리) continue; //현재 노드와 연결된 모든 간선 탐색 //더 짧으면 갱신

```java
    static int V, E, K;
    static ArrayList<Edge>[] graph; //전역 변수
    static StringBuilder sb;

    public static void main(String[] args) throws IOException{
        input();
        solution(K);

    }
    static void solution(int start){//bfs처럼 생각
        //1. 거리 배열 선언 및 초기화
        int[] dist = new int[V+1];
        //dist를 무한대로 초기화
        Arrays.fill(dist, Integer.MAX_VALUE);
        //dist[start] = 0
        dist[start] =0;

        //2. 우선순위 큐 선언( 가중치 기준 오름차순)
        PriorityQueue<Edge> pq = new PriorityQueue<>((a,b)-> a.w- b.w);

        //시작점 pq에 넣기
        pq.offer(new Edge(start, 0)); //번호: start, 거리: 0

        //출력
        while(!pq.isEmpty()){
            Edge cur = pq.poll();
            int curN = cur.v; //현재 정점
            int curD = cur.w; //현재 거리
            //이미 처리된 노드이면 continue ( 더 짧은 경로로 이미 갱신)
            if (curD > dist[curN]){
                continue;
            }
            //현재 노드와 연결된 간선 탐색
            for (Edge next: graph[curN]){
                int nextN = next.v;
                int nextD = curD + next.w;
                //더 짧은 경로 발견하면 갱신
                if(nextD < dist[nextN]){
                    dist[nextN] = nextD;
                    pq.offer(new Edge(nextN, nextD));
                }

            }
        }//while
        //출력
        sb = new StringBuilder();
        for (int i = 1; i <= V; i++){
            if(dist[i] ==Integer.MAX_VALUE){
                sb.append("INF\n");
            }else{
                sb.append(dist[i]).append("\n");
            }
        }
        System.out.println(sb);

    }

아이디어

• 처음에 이분탐색인지 모르겠음.
• 의사코드

  left = 1, right = max(랜선들) 
  while(left <=right): 
    mid = (left+right) / 2
    if(mid로 잘랐을때 개수가 N이상이면): //길이를 늘려야함 
        answer = mid; //저장 
        left = mid+1; 
    else: 
        right= mid -1; 

package boj_silver.p1654_랜선자르기;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int ans;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int k = scan.nextInt(); int n = scan.nextInt();
        //k개 입력 받기
        //랜선 길이가 최대 2^32 - 1이므로 long 사용
        long[] arr = new long[k];
        for (int i = 0; i < k; i++) {
            arr[i] = scan.nextLong();
        }
        long left = 1;
        long right = 0;
        //최댓값
        for (int i = 0; i < k; i++) {
            right = Math.max(right, arr[i]);
        }
        long ans = 0;

        while(left<=right){
            long mid = (left+right)/ 2;
            //돌면서
            long sum = 0;
            for (int i = 0; i< k; i++){
                sum += arr[i] / mid;
            }
            if(sum>=n){
                ans = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }//while
        System.out.println(ans);

    }
}

아이디어

• dp[n]까지 점화식 만들고, dp[n]출력
• 점화식: dp[i] = Math.max(dp[i-3] + stairs[i-1] + stairs[i] , dp[i-2] + stairs[i]);

package boj_silver.p2579_계단오르기;

import java.util.Scanner;

public class Review1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] stairs = new int[n+1];
        for (int i = 1; i<=n; i++){
            stairs[i] = scan.nextInt();
        }
        //dp 초기화
        int [] dp = new int[n+1];
        //만약 계단이 적다면 !
        dp[0] = 0;
        if (n>=1){
            dp[1] = stairs[1];
        }
        if(n>=2){
            dp[2] =  stairs[1] + stairs[2];
        }
        if (n>=3){
            //dp 식
            for (int i = 3; i<=n; i++){
                dp[i] = Math.max(dp[i-3] + stairs[i-1] + stairs[i], dp[i-2] + stairs[i]);
            }

        }
        System.out.println(dp[n]);


    }
}

Bottom-Up DP (내 방식 개선)

int[] dp = new int[n+1]; 
dp[1] =stairs[1]; 
if(n>=2) dp[2] = stairs[1] + stairs[2];
for (int i = 3; i<=n;i++){
    dp[i] = Math.max(
        dp[i-2] + stairs[i], //2칸 점프 
        dp[i-3] + stairs[i-1] + stairs[i] //1칸씩 2번 
    );
}//for     

*일반적이고 이해하기 쉽다. 단점은 배열 사용으로 메모리가 O(n) *

Top-Down DP (재귀 + 메모이제이션)

static Integer[] dp; //null 체크 위해 Integer 사용 
public static void main(String[] args) {
    dp[0]= 0; 
    dp[1] = stairs[1]; 
    if(n>=2) dp[2]= stairs[1] + stairs[2]; 
    System.out.println(solve(n)); 
}//main

static int solve(int n){
    //이미 계산된것 건너뛰기 
    if(dp[n]!=null) return dp[n]; 

    dp[n]= Math.max(
        solve(n-2) + stairs[n], 
        solve(n-3)+ stairs[n-1] + stairs[n]
    ); 
    return dp[n]; 
}//solve: 재귀 

2. 백준 1259 팰린드롬수

아이디어

• 처음에는 queue로 해서 앞에 있는것과 peek를 비교해서 양 옆을 제거하고 싶었으나 마지막에 들어온 것 제거하는 방법 모름 => //Deque 사용하면 양쪽 삽입 삭제 가능
• 그래서 그냥 배열로 받아 양쪽 비교하고, 안맞는 즉시 flag = false로 하고 바로 break함.

  package boj_bronze.p1259_팰린드롬수;
  

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

public class Main { public static void main(String[] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while(true){ String str = br.readLine(); //종료 if(str.equals("0")){ return; } //char로 바꾸기 ! Character[] chars = new Character[str.length()]; for (int i = 0; i < str.length(); i++) { chars[i] = str.charAt(i); } int n = chars.length; boolean flag = true;

        for(int i = 0; i< n; i++){
            if (chars[i]  != chars[n-i-1]){
                //하는 순간 바로 flag = false
                flag = false;
                break;
            }
        }
        if(flag){
            System.out.println("yes");
        }else{
            System.out.println("no");
        }



    }//while 입력 받기


}

}

** 내방법의 시간 복잡도와 공간 복잡도는 O(n)이다. 투 포인터로 사용하면 공간 복잡도는 O(1)로 효율적으로 구현할 수 있다. 추가 메모리 없이 charAt()만 사용한다. 
```java
//main 메서드 
while(true){
    String str = br.readLine(); 
    if(str.equals("0")) break; //0들어오면 바로 입력 종료 

    //함수 적용해서 팰린드롬수가 맞으면, yes 아니면 no출력한다. 
    sb.append(isPalindrom(str) ? "yes" :"no").append("\n");     
}//while 
//출력 
System.out.print(sb); 

//isPalindrom함수 
static boolean isPalindrome(String s){
    int l = 0; int r = s.length()-1; 

    while(l<r){
        if(s.charAt(l++) !=s.charAt(r--)){
            return false; 
        }
    }//whie
    return true; 
}

아이디어

• 정렬 -> Comparator를 람다식으로 표현하기 -> ```Arrays.sort(xy, (a, b) -> { if (a[0] != b[0]) {

    return a[0] - b[0];

  } else {

    return a[1] - b[1];

  } });```
• 추가적 방법 (삼항 연산자) Arrays.sort(xy, (a,b)-> a[0] !=b[0] ? a[0]- b[0] : a[1]-b[1] (Compator 메서드 체이닝) Arrays.sort(xy, Comparator.comparingInt(int[] a) -> a[0]).thenComparingInt(a-> a[1]));

package boj_silver.p11650_좌표정렬;
import java.io.*;
import java.util.*;

//좌표정렬: x-> y
public class Review2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        int[][] xy = new int[n][2];

        for (int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            xy[i][0] = a;
            xy[i][1] = b;
        }
        Arrays.sort(xy, (a,b) -> {
            if (a[0] !=b[0]) {
                return a[0] - b[0];
            }else{
                return a[1] - b[1];
            }
        });
        for (int[] num: xy){
            int a = num[0];
            int b = num[1];
            System.out.println(a + " " + b);
        }
        br.close();
        //정렬

    }

}

2. 프로그래머스 lv1. k번째 수

아이디어 문제: array의 i번째~j번째 까지 자르고 정렬하고 k번째 있는 수 구하기

• 배열 복사 후 정렬해야함. int[] tmp = Arrays.copyOfRange(array, s-1, e);
• 리스트에 tmp[k-1] 추가한다.
• 리스트를 Array로 바꿈 list.stream().mapToInt(Integer::intValue).toArray();

Stream() 기초 문법 및 예시 코드

Stream API는 collection, array등의 데이터를 다루기 위한 함수형 프로그래밍 방식을 제공한다. 기능을 구현하지 않고, 선언형으로 컬랙션 형을 처리할 수 있다. (반복문, 조건문)

문법 구조

생성하기 - 가공하기 - 결과 만들기

List<String> fruits = Arrays.asList("apple", "banana", "apple" "orange", "kiwi", "watermelon"); 

//1. filter()로 원하는요소 출력하기 
fruits.stream() //stream 생성 
    .filter(fruit-> fruit.startwiith("a")) //가공하기 
    .forEach(System.out::println);  //결과 만들기 
    // 출력: apple apple 

// 2. map(): 매핑처리로 리스트 내 모든 값을 키_값 형태로 처리한다. 
fruits.stream()
        .map(fruit -> fruit.toUpperCase())
        .forEach(System.out::println); 
        // 출력: APPLE BANANA APPLE ORANGE KIWI WATERMELON

//3. sorted() 
fruits.stream()
        .sorted()
        .forEach(System.out::println); 
        // 출력: apple apple banana kiwi orange watermelon

//4. reduce()
String result = fruits.stream()
                        .reduce("", (s1, s2)-> s1+s2); 
System.out.println(result); 

//5. distinct() 
fruits.stream()
        .distinct()
        .forEach(System.out::println);
        // 출력: apple banana orange kiwi watermelon
//6. limit()
fruits.stream()
        .limit(3) 
        .forEach(System.out::println);
        // 출력: apple banana apple

//7. skip()
fruits.stream()
              .skip(2)
              .forEach(System.out::println);
        // 출력: apple orange kiwi watermelon

//8. count()
long count = fruits.stream()
                    .count(); 
System.out.println(count);  //출력: 6

Stream 중간 연산에서 자주 쓰이는 가공 메서드

• filter() : 특정 조건에 부합하는 stream 전개
• map(): 매핑처리로 리스트내 모든 값을 키/값 형태로 처리한다.
• sorted(): 알파벳 순으로 정렬
• reduce(): 모든 과일을 하나의 문자열로 연결한다.
• distinct(): 중복된 값을 제거하고 출력
• limit(long maxSize): 처음부터 maxSize개의 값을 출력한다.
• skip(long n): 처음 n개의 값을 제외한 나머지값 출력

Stream 최종연산에서 자주 쓰이는 메서드

• forEach(Consumer action): 각 요소에 대해 주어진 action을 실행한다
• count(): 스트림의 요소 수를 반환
• collect(Collector<T, A, R> collector): 스트림의 요소를 수집하여 Collection, List, Set, Map 등의 컬렉션에 저장하는 최종 연산
• toArray(): 스트림의 요소를 배열로 반환하는 최종 연산
• reduce(T identity, BinaryOperator accumulator): 스트림의 요소를 identity로 초기화한 후, accumulator 연산을 반복하여 값을 줄여나가는 최종 연산 예시코드에서는 더하기연산으로 문자열을 이어쓰는 형태로 활용하였다
• min(Comparator comparator): 스트림에서 최소값을 반환
• max(Comparator comparator): 스트림에서 최대값을 반환
• anyMatch(Predicate predicate): 스트림에서 predicate 조건을 만족하는 요소가 하나라도 있는지 확인
• allMatch(Predicate predicate): 스트림의 모든 요소가 predicate 조건을 만족하는지 확인

3. 백준 2750 수 정렬하기

4. 백준 1181 단어 정렬

아이디어

• TreeSet으로 중복 제거 + 자동 정렬 => sb.append()로 출력

TreeSet<String> set = new TreeSet<>((a, b) -> {
    if(a.length() != b.length()){
        return a.length() - b.length();
    }
    return a.compareTo(b); 
})

for (String word: set){
    sb.append(word).append("\n"); 
}

package boj_silver.p1181_단어정렬;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class Review2_treeset {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder();
        int n = Integer.parseInt(br.readLine());


        //treeset: 중복 제거 + 자동 정렬
        TreeSet<String> set = new TreeSet<>((a,b) -> {
            if(a.length() != b.length()){
                return a.length() - b.length();
            }
            return a.compareTo(b);
        });
//        for (int i = 0; i < strArr.length; i++) {
//            sb.append(strArr[i] + "\n");
//        }
        for (int i = 0; i<n; i++){
            set.add(br.readLine());
        }
        for (String word: set){
            sb.append(word).append("\n");
        }

        System.out.println(sb);
        br.close();
    }
}

정렬 코테 총 정리

1. 배열 Array 정렬

1-1 기본 타입 배열 오름차순

int[] arr1 = {5,2,8,1,9}; 
//오름차순 
Arrays.sort(arr1); // 1,2,5,8,9
//범위 지정 정렬 (0~2번 인덱스만 정렬 
Arrays.sort(arr1, 0, 3); // 2,5,8,1,9

1-2 Wrapper 클래스 배열 내림차순

Integer[] arr = {5,2,8,1,9}; 
Arrays.sort(arr, Collections.reverseOrder()); 

1-3 String 배열 (사전순)

String[] strArr = {"banana", "apple", "cherry"};
Arrays.sort(strArr); //apple, banana, cherry

1-4 람다식 정렬

Integer[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr, (a, b)-> a-b); //오름차순 
Arrays.sort(arr, (a,b)-> b-a); //내림차순 

1-5 복잡한 조건 정렬 (홀수 우선, 같으면 오름차순)

Integer[] arr = {5, 2, 8, 1, 9};
Arrays.sort(arr, (o1, o2)-> {
    if(o1 %2 !=0 && o2%2 ==0) return -1; //o1이 홀수 일때 우선 
    if (o1 % 2 == 0 && o2 % 2 != 0) return 1; 
    return o1-o2; //오름 차순 
}); 

2. List 정렬

2-1 Collections.sort() 사용

List<Integer> list = new ArrayList<>(Arrays.asList(5,2,8,1,9)); 
//오름차순 
Collections.sort(list); 
//내림차순 
Collections.sort(list, Collections.reverseOrder()); 

2-2 list.sort() 사용 (java 8+)

list.sort(Comparator.naturalOrder()); 

list.sort(Comparator.reverseOrder()); 

2-3 람다식

//오름차순 
list.sort((a,b)-> a-b);  

3. 객체 정렬 - Comparable 인터페이스

Person Class에서 compareTo 메서드 오버라이드

Class Person implements Comparable<Person>{
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override 
    public int compareTo(Person other){
        return this.age - other.age; //나이 기준 오름 차순 
    }

    @Override 
    publis String toString(){
        return name + "(" + age + ")"; 
    }

}

main 메서드

List<Person> people = new ArrayList<>(); 
people.add(new Person("김철수", 25));
people.add(new Person("이영희", 20));
people.add(new Person("박민수", 30));

Collections.sort(people); //compareTo()기준 정렬 
//역순 정렬 
Collections.sort(people, Collections.reverseOrder()); 

4. 객체 정렬 - Comparator 인터페이스

Student class

class Student {
    String name;
    int score;
    int age;

    public Student(String name, int score, int age) {
        this.name = name;
        this.score = score;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + "(" + score + "점, " + age + "세)";
    }
}

main 메서드

List<Student> students = new ArrayList<>();
        students.add(new Student("김철수", 85, 20));
        students.add(new Student("이영희", 90, 22));
        students.add(new Student("박민수", 85, 21));
//1. 점수 기준 내림차순
students.sort((s1, s2)-> s2.score - s1.score); 

//2. 점수가 같으면 나이 오름차순    
students.sort((s1,s2) -> {
    if(s1.score!=s2.score){
        return s2.score- s1.score; //점수 내림차순
    }
    return s1.age - s2.age; //나이 오름차순 
} 

//3. Comparator 메서드 체이닝 !! 
students.sort(Comparator.comparingInt((Student s) -> s.score).reversed()
                                                    .thenComparingInt(s-> s.age); 

// 4. 이름 기준 사전 순 
students.sort(Comparator.comparing(s-> s.name)); 

5. 2차원 배열 정렬

int[][] arr = {{3, 5}, {1, 2}, {5, 3}, {1, 7}};

//1. 첫번째 원소 기준 오름차순 
Arrays.sort(arr, (a, b)-> a[0]- b[0]); 

//2. 첫번째 같으면 두번째 기준 
Arrays.sort(arr, (a, b)-> {
    if(a[0] !=b[0]) return a[0] - b[0]; //첫번째 오름차순 
    return a[1]- b[1]; //두번째 오름차순 
}); 

//3. 두번째 원소 기준 내림차순 
Arrays.sort(arr, (a, b)-> b[1]- a[1]); 

6. 특수 자료 구조 정렬

Priority Queue 정렬

// 1. 최소 힙
PrioriyQueue<Integer> minHeap = new PrioriyQueue<>(); 
minHeap.addAll(Arrays.asList(5,2,8,1,9)); 
//출력- 최소 힙 
while(!minHeap.isEmpty()){
    System.out.print(minHeap.poll() + " " ); 
}

// 2. 최대힙 
PrioriyQueue<Integer> maxHeap = new PrioriyQueue<>(Collections.reverseOrder()); 
maxHeap.addAll(Arrays.asList(5,2,8,1,9)); 
while(!minHeap.isEmpty()){
    System.out.print(minHeap.poll() + " " ); 
}

TreeSet- 자동 정렬 + 중복 제거

TreeSet<Integer> treeSet = new TreeSet<>(Arrays.asList(5, 2, 8, 1, 9, 2));
System.out.println("TreeSet (중복 제거): " + treeSet);

TreeMap- key자동 정렬

TreeMap<String, Integer> treeMap = new TreeMap<>(); 
treeMap.put("banana", 3);
treeMap.put("apple", 1);
treeMap.put("cherry", 2);
System.out.println("TreeMap: " + treeMap);

7. 문자열 정렬 특수 케이스

String[] words = {"apple", "pie", "banana", "cat"};

//1. 길이 기준 정렬 
Arrays.sort(words, (a,b) -> a.length() - b.length()); 

//2. 길이 같으면 사전순 
Arrays.sort(words, (a, b)-> {
    if(a.length() != b.length()) return a.length()- b.length(); 
    return a.compareTo(b); 
}); 

//3. 대소문자 구분 없이 정렬 
String[] words3 = {"Apple", "banana", "Cherry"};
Arrays.sort(words3, String.CASE_INSENSITIVE_ORDER); 

8. 코테용 자주 쓰는 정렬 패턴

Integer[] arr1 = {-5, 2, -8, 1, 9};

절댓값 기준 정렬

Arrays.sort(arr1, (a,b)-> Math.abs(a)- Math.abs(b));

특정 값과의 거리 기준 정렬

int target = 5; 
Integer[] arr2 = {1, 3, 7, 9, 2};
Arrays.sort(arr2, (a, b)-> Math.abs(a-target)- Math.abs(b-target)); 

빈도수 기준 정렬

Integer[] arr3 = {1, 1, 2, 2, 2, 3};
Map<Integer, Integer> freqMap =  new HashMap<>(); 
for (int num: arr3){
    freqMap.put(num, freqMap.getOrDefault(num, 0) +1); 
}
//빈도수 내림차순 
Arrays.sort(arr3, (a,b)-> freqMap.get(b) - freqMap.get(a)); 

9. 정렬 주의사항 및 시간 복잡도

시간 복잡도

• Arrays.sort()

- 기본 타입(int[]): O(n log n) - Dual-Pivot Quicksort”

- 객체 타입(Integer[]): O(n log n) - TimSort”

주의사항

• int[] 배열은 Comparator 사용 불가 → Integer[] 사용
• 람다식 (a, b)→ a-b 오버플로우 주의
  • 안전한것은 Integer.compare(a,b)
• 내림차순 Collections.reverseOrder()또는 (a,b)→ b-a

Comparable vs Comparator

• Comparable: 클래스 내부에 compareTo() 구현 (기본 정렬)
• Comparator: 외부에서 compare() 구현 (사용자 정의 정렬)

stable sort

• Arrays.sort(객체 배열), Collections.sort() : 안정 정렬 o
• Arrays.sort(기본 타입) : 안정 정렬 x

웹서버 & WAS, 서블릿, 멀티 쓰레드, CSR/SSR, 자바 벡엔드 역사 정리

1. 웹 서버(Web Server)와 웹 애플리케이션 서버(WAS)

1-1. 모든 것이 HTTP 기반

브라우저 ↔ 서버 간의 모든 통신은 HTTP 프로토콜을 기반으로 한다. 정적/동적 리소스 제공 방식은 서버 종류에 따라 다르다.

1-2. 웹 서버(Web Server)

정적 리소스를 제공하는 서버. (HTML, CSS, JS, 이미지, 영상 파일 등)

• 요청이 오면 파일 그대로 전달
• 실행 로직 없음 → 가볍고 빠르고 잘 안 죽음
• 예: NGINX, Apache

1-3. 웹 애플리케이션 서버(WAS)

정적 리소스 제공 + 애플리케이션 로직 실행이 가능한 서버.

• 동적으로 HTML 생성 (JSP, Thymeleaf)
• REST API(JSON) 응답
• 서블릿, JSP, 스프링 MVC 처리
• 예: Tomcat

1-4. 웹 서버 vs WAS (핵심 정리)

자바 기반에서 서블릿 컨테이너 기능을 제공하면 WAS로 분류됨.

1-5. 웹 시스템 구성 방식

✔ WAS + DB

• 단독 구성 가능
• 하지만 정적 리소스까지 WAS가 떠맡으면 과부하 발생
• WAS 장애 시 에러 페이지도 제공할 수 없음

✔ Web Server + WAS + DB (권장)

• 정적 리소스: Web Server

• 동적 로직: WAS

• 장점

  • 효율적인 리소스 분리
  • Web Server는 안정성이 높음
  • 장애 시 Web Server가 에러 페이지 응답 가능

• REST API만 사용하는 시스템은 Web Server 생략해도 됨

2. 서블릿(Servlet)

2-1. HTML Form 데이터 전송

• 브라우저 → 서버로 데이터 전달 시 POST 요청 사용
• 이를 처리하는 것이 서블릿

(예: /hello 주소 호출 → HelloServlet 실행)

2-2. 서블릿의 역할

• HttpServletRequest → 요청 데이터 조회 (request.getParameter() 등)

• HttpServletResponse → 응답 메시지 생성 (HTML, JSON 등)

HTTP 스펙을 개발자가 직접 다룰 수 있게 설계된 API라고 보면 됨.

2-3. 서블릿 요청/응답 흐름

1. 클라이언트가 HTTP 요청
2. WAS가 Request/Response 객체 생성
3. 해당 URL 매핑된 서블릿 호출
4. 개발자가 request/response에 데이터를 읽고 쓰기
5. WAS가 Response 내용을 기반으로 최종 HTTP 응답 생성

→ 개발자는 HTTP 처리 복잡성을 크게 줄일 수 있음.

2-4. 서블릿 컨테이너(=WAS의 핵심 기능)

WAS 내부에서 서블릿을 관리하는 기능을 말함.

• 서블릿 객체 생성·초기화·종료 관리
• 싱글톤으로 관리 (한 번만 만들고 재사용)
• 멀티쓰레드 환경 제공 → 동시 요청 처리
• JSP는 서블릿으로 변환되어 실행됨

주의: 싱글톤 객체이므로, 공유 변수 사용 시 동시성 문제에 유의해야 한다.

3. 멀티쓰레드 & 쓰레드 풀(Thread Pool)

3-1. 쓰레드(Thread)

• 코드 흐름을 수행하는 실행 단위
• 동시 처리가 필요하면 여러 쓰레드가 사용됨

3-2. 요청마다 쓰레드 생성 방식의 문제

• 쓰레드 생성 비용이 매우 크다
• 동시 요청 폭주 → 쓰레드 무제한 생성 → CPU/메모리 초과 → 서버 다운

3-3. WAS의 해결책: 쓰레드 풀(Thread Pool)

WAS는 내부적으로 쓰레드 풀을 운영한다.

특징

• 미리 쓰레드를 만들어 두고 재사용

• 요청 → 쓰레드 대여

• 처리 완료 → 쓰레드 반납

• 최대 쓰레드 개수 존재

  • Tomcat 기본 200개

장점

• 많은 요청도 안정적으로 처리 가능
• 개발자는 멀티쓰레드 코드를 직접 구현할 필요가 없음 → 싱글 쓰레드 코딩하듯 개발해도 됨

3-4. 실무 팁

• 쓰레드 수가 너무 적으면 → CPU는 남는데 처리량 부족
• 너무 많으면 → 서버가 오히려 장애
• 적정 숫자는 서비스마다 다르므로 성능 테스트 필수

테스트 도구

• Apache ab
• JMeter
• nGrinder

4. HTML, HTTP API, CSR, SSR 정리

4-1. 정적 리소스

• 변경되지 않는 HTML, CSS, JS 파일

4-2. HTML 페이지

• JSP/Thymeleaf처럼 서버가 HTML을 만들어 전달하는 방식

4-3. HTTP API

• HTML이 아닌 데이터(JSON) 전달
• 앱, 웹, 서버 간 통신에 널리 사용

4-4. SSR (Server-Side Rendering)

서버가 HTML 완성본을 만들어 클라이언트에 전송

• 정적인 화면에 적합
• JSP, 타임리프
• 백엔드 중심 구조

4-5. CSR (Client-Side Rendering)

HTML을 클라이언트(브라우저)에서 JS로 동적으로 생성

• React, Vue.js
• Gmail, Google Maps처럼 인터랙션이 많은 UI에 적합

SSR + CSR 혼합 방식도 가능 (Next.js 등)

5. 자바 백엔드 기술 역사

5-1. 과거

Servlet

• 동적 화면 생성 어려움 (HTML 출력 코드를 직접 작성해야 함)

JSP

• HTML 렌더링은 편하지만
• 로직 + 렌더링이 뒤섞여 유지보수 어려움

→ MVC 패턴 도입 → 화면과 비즈니스 로직 분리

5-2. 현재: Spring MVC & Spring Boot

Spring MVC

• 애노테이션 기반 (@Controller, @RequestMapping)
• MVC 아키텍처를 표준으로 자리 잡음

Spring Boot

• 내장 WAS 제공 → Jar 파일만으로 실행 가능
• 복잡한 설정 자동화
• 배포 간소화

5-3. 최신 기술: Spring WebFlux

WebFlux (Reactive)

• 비동기 논블로킹 처리
• 적은 쓰레드로 높은 성능
• 함수형 프로그래밍 스타일

→ 고성능 & 실시간 스트리밍 시스템에서 유용 → 하지만 실무 채택률은 아직 낮음

5-4. 뷰 템플릿의 역사

🔎 전체 흐름 요약

• Web Server는 정적 파일 제공, WAS는 로직 처리
• 서블릿은 HTTP 요청을 처리하는 핵심 기반 기술
• WAS는 멀티쓰레드 + 쓰레드풀로 동시 요청 처리
• Rendering 방식은 SSR, CSR로 나뉨
• 자바 백엔드는 Servlet → JSP → MVC → Spring MVC → Spring Boot → WebFlux로 발전 중

출처

김영한의 스프링 MVC 1편 - 백엔드 웹 개발 핵심 기술

아이디어

• 입력받는문제: scan.next()로 String 한줄을 입력받고, 문자열 길이만큼 순회하면서 char ch = str.charAt(j)를 입력받는다.
• flage로 한번만 출력되게 한다.( ')'가 들어왔는데 비어있으면, no표시만 flag = false로 하고, 마지막 출력때 flag && stack.isEmpty()조건으로 "YES"를 출력하도록 한다.

package boj_silver.p9012_괄호;
import java.util.*;

public class Review1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();


        for (int i = 0; i < T; i++) {
            Stack<Character> stack = new Stack<>();
            //Character ch = scan.next().charAt(0);

            //입력 처리
            String str = scan.next(); //문자열 전체를 받음
            boolean isValid = true;

            //문자 하나씩 순회하기 !!
            for (int j = 0; j<str.length(); j++){
                char ch = str.charAt(j);  //하나씩 입력받기
                if (ch =='('){
                    stack.push(ch);
                }else if(ch ==')'){
                    if(stack.isEmpty()){
//                        System.out.println("NO");
                        //no표시만
                        isValid = false;

//                        return; //main 종료 -> 전체 종료
                        break; //for문 탈출
                        //continue는 다음 반복으로 건너뛰기
                    }else{
                        stack.pop();
                    }
                }
            }

            //stack에 남아있다면
            if (isValid && stack.isEmpty()) {
                System.out.println("YES");
            } else {
                System.out.println("NO"); //또 출력되는 문제가 있네-> flag 사용
            }

        }//for
    }//main

}//class

2. 백준 21736 헌내기는 친구가 필요해

아이디어

• I를 만나는 좌표를 저장함 ! -> bfs를 I부터 시작함
• 범위 조건& 탐색 조건을 map[nx][ny] !='X'로 하고, 'P'라면 cnt++하는 방식으로 cnt를 셈.

package boj_silver.p21736_헌내기는친구가;

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

//미로 탐색이다.
//nxm의 크기으 ㅣ캠퍼스가 있고,
// O : 빈공간 / X: 벽 / I: 도연이 / P: 사람
//범위 조건에 O, X를 쓰고, P를 만날때 ++ 해서 출력

//도연이가 만날수 있는 사람의 수를 출력 -> 아무도 못만난 경우 TT 출력
public class Main {
    static int n,m, cnt ;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static char[][] map;
    static boolean[][] visited;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        visited= new boolean[n][m];

        int sx =0, sy = 0;
        //map 입력 받기
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < m; j++) {
                map[i][j] = line.charAt(j);

                //I를 만나면 bfs 시작
                if (map[i][j] == 'I'){
                    sx = i;
                    sy = j;
//                    bfs(i, j);//바로 시작하면 전부다 입력이 안됨,.
                }
            }
        }
        bfs(sx, sy);

        //System.out.println(Arrays.deepToString(map));
        if(cnt>=1){
            System.out.println(cnt);
        }else{
            System.out.println("TT");
        }
    }
    static void bfs(int x, int y){
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x,y});
        visited[x][y] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            for (int i = 0; i<4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];

                if(nx>=0 && ny>=0 && nx<n && ny<m){//가장자리 범위
                    if(!visited[nx][ny] && map[nx][ny]!='X'){
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx,ny});
                        if (map[nx][ny] == 'P'){
                            cnt++;
                        }
                    }
//                    if(!visited[nx][ny] && map[nx][ny] == 'P'){
//                        //P를 만났을때 처리 !!!! -> 큐에 추가해야함
//                        q.offer(new int[]{nx,ny});
//                        visited[nx][ny] = true;
//                        cnt++;
//                    }
//                    if(!visited[nx][ny] && map[nx][ny] == 'O'){
//                        q.offer(new int[]{nx,ny});
//                        visited[nx][ny] = true;
//
//                    }
                }
            }
        }

    }
}

3. 백준 7576 토마토

아이디어

• 익은 토마토(1)가 여러개 있을 수 있다 -> list로 좌표 입력 받고 , bfs에 한꺼번에 표시하기
• 벽: -1, 안익은 토마토: 0, 익은 토마토: 1 -> visited 배열 필요 없다.
• 출력은 만약 map에 0이 남아있으면, flag = flase, 아니면, max 변수에, 가장 큰 값을 넣는다. !flag이면 -1출력 / max -1 출력
• bfs) queue에 list에 있는 int[] 배열을 동시 추가한다. 큐가 빌때까지 4방향 탐색을 한다. 범위: 안익은 토마토만 & 벽이 있으면 안됨. map[nx][ny] ==0 && map[nx][ny]!= -1

package boj_gold.p7576_토마토;

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

public class Review1 {
    static int n,m;
    static int[][] map;
//    static boolean [][] visited;
    static int[] dx ={-1,1,0,0};
    static int[] dy ={0,0,-1,1};
    static List<int[]> list;

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

        map = new int[n][m];
//        visited = new boolean[n][m];

        //list에 1인 좌표를 큐에 넣기
        list = new ArrayList<>();

        //map 받기
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 1){
                    list.add(new int[]{i,j});
                }
            }
        }
        bfs(list);
//        System.out.println(Arrays.deepToString(map));
        int max= 0;
        boolean flag = true;

        //만약 0이 남아있으면 ?
        for (int i =0; i<n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    flag = false;
                }
                max = Math.max(map[i][j], max);
            }
        }
        if(!flag){
            System.out.println(-1);
        }else{
            System.out.println(max-1);
        }


    }
    static void bfs(List<int[]> list){
        Queue<int[]> q= new ArrayDeque<>();
        //동시 추가
        for (int[] pos: list){
            q.offer(pos);
        }

        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];

            //4방향 탐색
            for(int i =0; i< 4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                if (nx >=0 && ny>=0 && nx<n && ny<m){ //범위 체크
                    //안익은 토마토만
                    if(map[nx][ny] ==0 && map[nx][ny]!= -1){
                        map[nx][ny] = map[cx][cy] + 1;
                        q.offer(new int[]{nx,ny});
                    }

                }
            }

        }
    }
}

4. 백준 1874 스택수열

아이디어

• Stack자료구조 쓰고, flag로 한꺼번에 출력 (StringBuilder)
• 입력받는 동시에 로직 작성 ! (target은 들어오는 숫자)
• cur = 1부터 시작해서, cur<=target까지 push(cur) cur++
• target이 stack.peek()과 같고, stack이 비지 않았다면, pop(); -> else flage = false break;

package boj_silver.p1847_스택수열;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

//push 하는 순서는 반드시 오름차순 ->
public class Review1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        StringBuilder sb = new StringBuilder();

        //배열 입력받기
//        int[] numbers = new int[n]; // -> 입력받는 동시에 비교하기
//        for (int i = 0; i<n; i++){
//            numbers[i] = scan.nextInt();
//        }

        Stack<Integer> stack = new Stack<>();
        int cur = 1;
        boolean possible = true;
        //while(cur<=target)

        for (int i = 0; i < n; i++) {
            int target= scan.nextInt();
            while(cur<=target){
                stack.push(cur);
                sb.append("+\n");
                cur++;
            }
            if(!stack.isEmpty() && target ==stack.peek()){
                stack.pop();
                sb.append("-\n");
            }else{
                possible = false;
                break; //for문 탈출
            }
        }
        if(possible){
            System.out.println(sb);
        }else{
            System.out.println("NO");
        }


    }
}

5. 백준 10773 제로

아이디어

• stack에 있는 것 다 더하기 로직 (while(!stack.isEmpty()){int num = stack.pop(); sum+= num; }

package boj_silver.p10773_제로;

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {
            int num = scan.nextInt();
            if(num !=0){
                stack.push(num);
            }else if(num ==0){
                stack.pop();
            }
        }
        //stack에 있는 것 다 더하기
        int sum = 0;
        while(!stack.isEmpty()){
            int num = stack.pop();
            sum += num;
        }

        System.out.println(sum);
    }
}

1. 백준 2164 카드2

아이디어

• 처음에는 Stack으로 구현하였으나, 맨 아래로 넣는 작업에서 FIFO인 Queue로 구현하는것이 맞음.
• 맨 앞에서 빼기: poll() / 맨 뒤에 추가하기 : offer (), add()
• 구현 클래스는 LinkedList가 구현한다.

package boj_silver.p2164_카드2;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //스택
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        Queue<Integer> q = new LinkedList<>();

        //q에 1부터 ,,N까지 넣기 
        for(int i = 1; i<=n; i++){
            q.offer(i);
        }
        //
        while(true){
            //큐에 있는 개수가 1이 될때 poll하기 -> break 
            if (q.size() ==1){
                int num = q.poll();
                System.out.println(num);
                break;
            }//if

            //맨 첫번째 빼기
            q.poll();
            //맨 위에 있는것 맨 뒤로 보내기
            q.offer(q.poll());
        }
        scan.close();
    }
}

2. 백준 2178 미로탐색

*아이디어 *

• map[n][m] 배열에 거리를 담자! (map[nx][ny] = map[cx][cy] + 1)
• 주의! 범위 체크! map[nx][ny] ==1 인것만 탐색

1. bfs로 풀기

package boj_silver.p2178_미로탐색;
import java.util.*;
import java.io.*;

public class Review4 {
    static int n,m;
    static int[][] map;
    static boolean[][] visited;

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

    //1,1에서 출발하여, N, M의 위치로 갈때 지나야하는 최소 칸의 개수
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);


        n = scan.nextInt(); m = scan.nextInt();
        scan.nextLine();
        map= new int[n+1][m+1];
        visited = new boolean[n+1][m+1];

        for (int i= 1; i<=n;i++){
            String line = scan.nextLine();
            for (int j =1; j<=m;j++){
                map[i][j] = line.charAt(j-1)-'0';
            }
        }//for
//        System.out.println(Arrays.deepToString(map));
        bfs(1,1); 
        System.out.println(map[n][m]);
    }

    static void bfs(int x, int y){

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{x,y});
        visited[x][y] = true;

        while (!q.isEmpty()){
            int[] cur = q.poll();
            int cx= cur[0];
            int cy= cur[1];
            //4방향 탐색 
            for (int i = 0; i<4; i++){
                int nx = cx+dx[i];
                int ny = cy+dy[i];
                //범위 조건: 가장 자리 조건 
                if(nx>0 && ny>0 && nx<=n && ny<=m){
                //범위 조건: 탐색하지 않은것, 배열안이 1인것만 탐색 
                    if(!visited[nx][ny] && map[nx][ny] ==1){
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx,ny});
                        map[nx][ny] = map[cx][cy] +1;
                    }
                }
            }
        }

    }

}

2. dfs로 풀기

static void main(String[] args){
    visited[1][1]= true; 
    System.out.println(minDistance); 
}//main

static void dfs(int x, int y, int distance){
    //도착 
    if (x==n && y==m){
        minDistance = Math.min(minDistance, distance); 
        return; 
    }
    //탐색 
    for (int i = 0; i<4; i++){
        int nx = x+dx[i]; 
        int ny = y+ dy[i]; 

        if (nx>0 && nx<=n && ny>0 && ny<=m){
            if (!visited[nx][ny] && map[nx][ny] ==1){
                visited[nx][ny]= true; 
                dfs(nx, ny, distance+1); 
                visited[nx][ny] = false; //백트래킹 
            }

        }
    }

}

3. 백준 1260 dfs와 bfs

아이디어

• LinkedList<Integer>[] list 배열로 받기
• 간선 입력 받고, 정렬하기 (Collections.sort(list[i]))
• dfs -> bfs로 바꿀때, visited 초기화
• dfs) 현재 정점 방문 처리-> 출력 -> 인접 정점 탐색 (재귀)
• bfs) Queue 선언 -> Q offer -> q가 빌때까지 인접 정점 출력

  package boj_silver.p1260_dfs와bfs;

import java.io.*;
import java.util.*;

public class Review1 {
    static int V;
    static boolean[] visited;
    static LinkedList<Integer>[] list;
    //정점 번호가 작은 것 먼저 방문, 더 이상 방문 x-> 종료
    public static void main(String[] args) throws IOException {
        //Linked List<Integer>[] 로 하고, 우선순위 큐
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        //n개 생성
        list = new LinkedList[N+1];
        //모든 리스트 초기화
        for (int i = 1; i<=N; i++){
            list[i] = new LinkedList<>();
        }
        //M개 입력 받기
        for (int i = 1; i<= M; i++){
            st = new StringTokenizer(br.readLine());
            //list 초기화 하기
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            //양방향 입력-> 정렬하기 작은 것 부터 방문해야한다.
            list[a].add(b);
            list[b].add(a);
        }
        //정렬하기
        for (int i = 1; i<=N; i++){
            Collections.sort(list[i]); //모두 정렬하기
        }
        //첫번째 dfs
        visited = new boolean[N+1];
        dfs(V);
        System.out.println();
        visited = new boolean[N+1];
        bfs(V);
    }
    static void dfs(int v){
        //현재 정점 방문 처리 -> 현재 정점 출력
        visited[v] = true;
        System.out.print(v + " ");

        //인접 정점 탐색 -> 방문 안한 정점 재귀 호출
        // list[v]의 인점 정점 돌면서
        for (int next: list[v]){
            if(!visited[next]){
                dfs(next); // 재귀
            }
        }//
    }

    static void bfs(int v){
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(v);
        visited[v] = true;
        while(!q.isEmpty()){
            int cur = q.poll();
            System.out.print(cur + " ");
            //인접 정점
            for (int next: list[cur]){
                if(!visited[next]){
                    q.offer(next);
                    visited[next] = true;
                }
            }
        }
    }
}

4. 백준 1012 유기농 배추

아이디어

1. 배추 있는 좌표 리스트에 {y,x}순으로 저장함.

package boj_silver.p1012유기농배추;
//몇개의 bfs가 호출되는지 !
import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] visited;
    static int m,n;
    static int[][] map;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int T = Integer.parseInt(bf.readLine());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(bf.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());//배추의 개수

            ArrayList<int[]> list = new ArrayList<>();
            map = new int[n][m];

            visited = new boolean[n][m]; //초기화
            //k의 줄에 배추의 위치가 저장
            for (int j = 0; j< k; j++){
                st = new StringTokenizer(bf.readLine());
                int x = Integer.parseInt(st.nextToken()); //가로 좌표
                int y = Integer.parseInt(st.nextToken());//세로 좌표
                list.add(new int[]{y,x});
                map[y][x] = 1;
            }// list에 있는 것 돌면서 !

            //boolean[] listVisited = new boolean[list.size()];

            int sum = 0;
            for (int[] cur: list){
                if (!visited[cur[0]][cur[1]]){
                    bfs(cur[0], cur[1]);
                    sum++;
                }

            }
            System.out.println(sum);
        }

        bf.close();
    }//main
    static void bfs(int x, int y){
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{x,y});
        visited[x][y] = true;
        while(!q.isEmpty()){
            int [] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            for (int i = 0; i < 4; i++) {
                int nx = cx+ dx[i];
                int ny = cy+ dy[i];
                if (nx>=0 && nx<n && ny>=0 && ny<m){
                    if(!visited[nx][ny] && map[nx][ny]==1 ) {
                        q.offer(new int[]{nx,ny});
                        visited[nx][ny] = true;
                    }

                }

            }//for
        }

    }
}

2. 리스트 없이 2중 for문

** 아이디어**

** 1번** 입력받을때 리스트에 좌표를 저장한다. (가로, 세로)로 주어짐 -> list.add(new int[] {y,x}) 로 저장 map[y][x] = 1; -> 리스트에 있는 배추만 확인 2번: 2중 for문 입력받을때 map에만 저장한다. map[y][x] = 1; 전체 map을 순회하면서 배추를 찾는다. ==> 둘다 괜찮으나, 리스트를 사용하는 경우는, K가 훨씬 작을때 사용하고, 2중 for문은 코드 간결성과 K가 nxm에 가까울때

//map 전체를 돌면서, 
package boj_silver.p1012유기농배추;
//몇개의 bfs가 호출되는지 !

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

public class Main_effi {
    static boolean[][] visited;
    static int m,n;
    static int[][] map;
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st ;

        int T = Integer.parseInt(bf.readLine());
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(bf.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());//배추의 개수

            //ArrayList<int[]> list = new ArrayList<>();
            map = new int[n][m];
            visited = new boolean[n][m]; //초기화

            //k의 줄에 배추의 위치가 저장
            for (int j = 0; j< k; j++){
                st = new StringTokenizer(bf.readLine());
                int x = Integer.parseInt(st.nextToken()); //가로 좌표
                int y = Integer.parseInt(st.nextToken());//세로 좌표
                //list.add(new int[]{y,x});
                map[y][x] = 1;
            }// list에 있는 것 돌면서 !

            //boolean[] listVisited = new boolean[list.size()];
            //전체 맵 탐색
            int cnt =0;
            for (int x =0; x<n;x++){
                for (int y =0; y<m;y++){
                    if(map[x][y] ==1 && !visited[x][y]){
                        bfs(x,y);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);


//            int sum = 0;
//            for (int[] cur: list){
//                if (!visited[cur[0]][cur[1]]){
//                    bfs(cur[0], cur[1]);
//                    sum++;
//                }
//
//            }
//            System.out.println(sum);
        }

        bf.close();
    }//main
    static void bfs(int x, int y){
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{x,y});
        visited[x][y] = true;
        while(!q.isEmpty()){
            int [] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];
            for (int i = 0; i < 4; i++) {
                int nx = cx+ dx[i];
                int ny = cy+ dy[i];
                if (nx>=0 && nx<n && ny>=0 && ny<m){
                    if(!visited[nx][ny] && map[nx][ny]==1 ) {
                        q.offer(new int[]{nx,ny});
                        visited[nx][ny] = true;
                    }

                }

            }//for
        }

    }
}

**아이디어

• 처음에 bfs로 했을때 안풀림!!!
• 인구 이동이 발생하는 동안 while문으로 접근해서 이동이 발생하면, day추가하는 방식으로 함.

 javapackage boj_gold.p16234_인구이동;

import java.io.*;
import java.util.*;

public class Review1 {
    // 전역 변수 선언
    static int[][] map;           // N x N 크기의 땅 (각 칸의 인구수)
    static boolean[][] visited;   // BFS 방문 체크 배열
    static int[] dx = {-1, 1, 0, 0};  // 상하좌우 x
    static int[] dy = {0, 0, -1, 1};  // 상하좌우 y 
    static int N, L, R;           //  입력 받기 
    static boolean isMoved;       // 인구 이동 발생 여부 플래그

    public static void main(String[] args) throws IOException {
        // 입력 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        // 맵 초기화 및 입력
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int day = 0;  // 인구 이동이 며칠 동안 발생하는지 카운트

        // 인구 이동이 없을 때까지 반복
        while (true) {
            // 매일 visited 배열 초기화
            visited = new boolean[N][N];
            // 이동 발생 여부 초기화 (false부터 시작)
            isMoved = false;

            // 전체 맵을 순회하면서 연합 찾기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // 아직 방문하지 않은 칸이면 BFS로 연합 찾기
                    if (!visited[i][j]) {
                        bfs(i, j);
                    }
                }
            }

            // 인구 이동이 발생했으면 day 증가
            if (isMoved) {
                day++;
            } else {
                // 인구 이동이 발생하지 않았으면 종료
                break;
            }
        }

        // 결과 출력 (인구 이동이 며칠 동안 발생했는지)
        System.out.println(day);
    }

    /**
     * BFS를 이용해 (x, y)에서 시작하는 연합을 찾고 인구 이동 처리
     */
    static void bfs(int x, int y) {
        Queue<int[]> q = new ArrayDeque<>();        // BFS 탐색용 큐
        List<int[]> union = new ArrayList<>();      // 연합에 속한 칸들을 저장

        // 시작 칸을 큐와 연합에 추가
        q.offer(new int[]{x, y});
        union.add(new int[]{x, y});
        visited[x][y] = true;

        int sum = map[x][y];  // 연합의 총 인구수 (시작 칸의 인구수로 초기화)

        // BFS 탐색 시작
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cx = cur[0];  // 현재 x 좌표
            int cy = cur[1];  // 현재 y 좌표

            // 상하좌우 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];  // 다음 x 좌표
                int ny = cy + dy[i];  // 다음 y 좌표

                // 경계 체크 및 방문 체크
                if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny]) {
                    // 현재 칸과 다음 칸의 인구 차이 계산
                    int diff = Math.abs(map[cx][cy] - map[nx][ny]);

                    // 인구 차이가 L 이상 R 이하이면 연합 형성 가능
                    if (diff >= L && diff <= R) {
                        q.offer(new int[]{nx, ny});      // 큐에 추가 (BFS 계속)
                        union.add(new int[]{nx, ny});    // 연합에 추가
                        visited[nx][ny] = true;          // 방문 처리
                        sum += map[nx][ny];              // 연합의 총 인구수에 더하기
                    }
                }
            }
        }

        // 연합이 2개 이상의 칸으로 이루어진 경우에만 인구 이동 발생
        if (union.size() >= 2) {
            // 연합의 평균 인구수 계산
            int avg = sum / union.size();

            // 연합에 속한 모든 칸의 인구수를 평균값으로 업데이트
            for (int[] pos : union) {
                map[pos[0]][pos[1]] = avg;
            }

            // 인구 이동이 발생했음을 표시
            isMoved = true;
        }
    }
}

package boj_gold.p16234_인구이동;
//인구 이동이 얼마나 걸리는지 .
//인구이동이 일어나는 조건: 두 나라의 인구 차이가 L명 R명 이하 ->
//visited[] -> bfs 사용
// 방향 둘러가면서, 차이가 L, R 사이면 -> bfs 호출 -> count + 1
// 인구 이동 안하면 바로 0 출력 -> return
//count 출력

import java.io.*;
import java.util.*;

public class Review1 {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0,0};
    static int[] dy = {0,0,-1,1};
    static int N, L, R;
    static Queue<int[]> q;
    static boolean isMoved;
    static int sum;


    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        //
        for (int i = 0; i< N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j =0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int day = 0;
        //인구이동이 발생하는 동안
        while(isMoved) {
            //visited 초기화
            visited = new boolean[N][N];
            //이동 발생 여부
            isMoved = false;
            //전체 맵 순회하면서
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (!visited[i][j]) {
                        //bfs로 연합 찾기
                        bfs(i, j);

                        isMoved = true;
                    }
                }
            }//for

            //만약 이동이 발생하면
            if(isMoved){
                day++;
            }else break;
        }//while
        System.out.println(day);

//        System.out.println(Arrays.deepToString(map));

        //일단 (0,0부터 시작하기)
        //만약 호출을 안하면 넣어줘야 함...........
//        int count =0;
//        q = new ArrayDeque<>();
//        for(int i = 0; i< N; i++){
//            for (int j = 0; j< N; j++){
//                if(!visited[i][j]){
//                    q.offer(new int[] {i,j});
//                    int sum = bfs(i, j, 0);
//                    count++;
//                }
//            }
//        }
//        System.out.println(count);


    }//main
    static void bfs(int x, int y){
        //돌면서 찾기
        Queue<int[]> q = new ArrayDeque<>();
        //연합에 속한 칸 저장
        List<int[]> union = new ArrayList<>();

        q.offer(new int[]{x,y});
        union.add(new int[]{x,y});
        visited[x][y] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            int cx = cur[0];
            int cy = cur[1];

            for(int i =0; i<4; i++){
                //이동하면서 차이가 L, R사이이면,
                int nx = cx+ dx[i];
                int ny = cy + dy[i];

                if (0<=nx && nx <N && 0<=ny && ny<N && !visited[nx][ny]){
                    int diff = Math.abs(map[cx][cy] - map[nx][ny]);
                    if (diff>=L && diff<=R){
                        //이동
                        q.offer(new int[]{nx,ny});
                        union.add(new int[]{nx,ny});
                        visited[nx][ny] = true;
                        sum += map[nx][ny];
                        //bfs(nx, ny, sum+map[cx][cy]);
                    }
                }
            }
        }//while
        //현재
        //union이 2개이상이라면 ?

        if(union.size()>1){
            //평균 계산
            int avg  = sum/union.size();
            for (int[] pos: union){
                map[pos[0]][pos[1]] = avg;//map 업데이트
            }
            isMoved = true;
        }


    }


//    static int bfs(int x, int y, int sum){
//        q.offer(new int[] {x,y});
//        visited[x][y] = true;
//        //현재
//        int[] cur = q.poll();
//        int cx = cur[0];
//        int cy = cur[1];
//
//        cnt =0;
//        for (int i = 0; i< 4; i++){
//            //이동하면서 차이가 L이상 R이하라면, 일단 더함
//            int nx = x+ dx[i];
//            int ny = y+ dy[i];
//            if (0<=nx && nx <N && 0<=ny && ny<N && !visited[nx][ny]){//경계선
//                int diff = Math.abs(map[cx][cy] - map[nx][ny]);
//                if (diff>=L && diff<=R){
//                    //이동
//                    bfs(nx, ny, sum + map[cx][cy]);
//                    cnt++;
//                }
//
//            }
//        }//for
//        return sum;
//    }
}

package boj_bronze.p3040_백설공주와일곱난쟁이;
import java.util.*;

public class Review1 {
    // 아이디어: 9개의 요소를 다 더한 후 100을 빼면, 제거해야할 2명의 난쟁이가 남는다. 
    static int[] nums; //9개 숫자 넣을 배열 

    public static void main(String[] args) {
        //입력 받기
        Scanner scan = new Scanner(System.in);
        nums = new int[9];

        int sum  =0;
        for (int i = 0; i < 9; i++){
            nums[i] = scan.nextInt();
            sum+= nums[i];
        }
        //100에서 sum을 뺀 값이 난쟁이가 아닌 두 수를 더한 후보이다.
        int target_num = sum - 100;
        int n1  = -1, n2 = -1;
        // 두 숫자 찾기
        //두숫자를 더해 target_num이면 제거를 하는것
        for (int i = 0; i< 9; i++){
            //nums배열에서 두 값을 더해서 target_num인 두 값을 찾기
            for (int j = i+1; j < 9; j++){
                if (nums[i] + nums[j] == target_num){
                    n1 = i;//인덱스 저장
                    n2 = j; //인덱스 저장
                    break;
                }
            }
        }//for
        //출력
        for (int i = 0; i< 9; i++){
            if (i!=n1 && i !=n2){
                System.out.println(nums[i]);
            }
        }
        scan.close();
    }
}

아이디어

• 입력을 받는게 은근 쉽지 않네
• 공백없이 숫자 받기 -> ?
• 그냥 String으로 받아서 charAt()-'0'으로 받기

나의 문제 풀이 과정

• scanner로 입력을 받을때, scan.nextInt()로 받으면 '\n'의 개행문자가 남아 입력부분이 잘 처리가 안되었음.

• scan.nextLine()으로 받기

public class Review1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = Integer.parseInt(scan.nextLine());

        //배열 생성
        int[] array = new int[N];

        String line = scan.nextLine();

        //N개만큼 받기
        for (int i = 0; i< N ; i++) {
            array[i] = line.charAt(i) - '0';
        }

        for (int i = 0; i< N ; i++) {
            System.out.println(array[i]);
        }
    }
}

코테에서 입력 꿀팁

1. N개의 정수 한줄에

//입력: 5 5 4 3 2 1 
int n = scan.nextInt(); 
int[] arr = new int[n]; 
for (int i=0; i<n; i++){
    arr[i] = scan.nextInt(); 
}

2. 공백으로 구분된 숫자 -> BufferedReader + StringTokenizer

//입력: 1 2 3 4 5
String[] input = bf.readLine().split(" "); 
int[] arr = new int[input.length]; 
for (int i = 0; i< input.length; i++){
    arr[i] = Integer.parseInt(input[i]); 

//또는 String Tokenizer
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
 StringTokenizer st = new StringTokenizer(bf.readLine()); 
 int N = Integer.parseInt(st.nextToken()); 
}

3. 붙어 있는 숫자들

//입력: 12345
String line = bf.readine(); 
int[] arr = new int[line.length()]; 
for (int i = 0; i< line.length(); i++){
    arr[i] = line.charAt(i)- '0'; 
}

4. 2차원 배열 받기

// 입력: 
// 3 4
// 1 2 3 4
// 5 6 7 8
// 9 10 11 12

int n = scan.nextInt(); 
int m - scan.nextInt(); 
int[][] arr = new int[n][m]; 
for (int i = 0; i< n; i++){
    for(int j = 0; j< m; j){
            arr[i][j] = scan.nextInt(); 
    }
}

5. 끝까지 읽기 (EOF까지 읽기)

//scanner 
while(scan.hasNext()){
    int n = scan.nextInt(); 
    //처리 
}

6. 빠른 출력

StringBuilder sb = new StringBuilder(); 
for (int i =0; i< n; i++_){
    sb.append(i).append("\n"); 
}
System.out.print(sb);