문제 링크

문제 설명

노드끼리 연결되어있는지를 확인하는 문제로 일반적으로 Union-find를 생각해볼 수 있다. 일반적인 Union-find문제와 다르다고 생각한 점은 크게 2가지가 있었다.

• 일반 배열이 아닌 Map을 사용해서 부모의 정보를 저장(Map<String, String>)
• 연결된 노드의 개수를 확인하는 것

Map을 사용한 정점 노드 확인(실패)

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

public class Main {
    static Map<String, String> parent;
    static Map<String, Integer> nameCnt;
    static int cnt;

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

        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int F = Integer.parseInt(br.readLine());
            parent = new HashMap<>();
            nameCnt = new HashMap<>();
            for (int i = 0; i < F; i++) {
                st = new StringTokenizer(br.readLine());
                String name1 = st.nextToken();
                String name2 = st.nextToken();

                if(!parent.containsKey(name1)){
                    parent.put(name1, name1);
                }
                if(!parent.containsKey(name2)){
                    parent.put(name2, name2);
                }

                union(name1, name2);
                sb.append(cnt).append("\n");
            }
        }
        System.out.println(sb);
        br.close();
    }
    static String find(String name){
        if(parent.get(name).equals(name)){
            return name;
        }
        return parent.put(name,find(parent.get(name)));
    }

    static void union(String name1, String name2){
        name1 = find(name1);
        name2 = find(name2);

        if(!name1.equals(name2)){
            if(!nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
                parent.put(name2, name1);
                nameCnt.put(name1, 2);
                cnt = 2;
            }else if(nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
                parent.put(name2, name1);
                cnt = nameCnt.get(name1) + 1;
                nameCnt.put(name1, cnt);
            }else if(!nameCnt.containsKey(name1) && nameCnt.containsKey(name2)){
                parent.put(name1, name2);
                cnt = nameCnt.get(name2) + 1;
                nameCnt.put(name2, cnt);
            }else{
                parent.put(name2, name1);
                cnt = nameCnt.get(name1) + nameCnt.get(name2);
                nameCnt.put(name1, cnt);
            }
        }
    }
}

Map을 사용한 부모 정보 저장

for (int i = 0; i < F; i++) {
    st = new StringTokenizer(br.readLine());
    String name1 = st.nextToken();
    String name2 = st.nextToken();

    if(!parent.containsKey(name1)){
        parent.put(name1, name1);
    }
    if(!parent.containsKey(name2)){
        parent.put(name2, name2);
    }
    ...
}

• 처음 등장한 친구의 이름이라면 자기 자신을 부모로 설정하여 Map<String, String> parent 저장한다.

find

static String find(String name){
    if(parent.get(name).equals(name)){
        return name;
    }
    return parent.put(name,find(parent.get(name)));
}

• 재귀 호출을 통해 정점인 노드를 찾기 위한 함수로, return시에 값을 변경해주면서 경로를 압축해준다.

union

static void union(String name1, String name2){
    name1 = find(name1);
    name2 = find(name2);

    if(!name1.equals(name2)){
        if(!nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
            parent.put(name2, name1);
            nameCnt.put(name1, 2);
            cnt = 2;
        }else if(nameCnt.containsKey(name1) && !nameCnt.containsKey(name2)){
            parent.put(name2, name1);
            cnt = nameCnt.get(name1) + 1;
            nameCnt.put(name1, cnt);
        }else if(!nameCnt.containsKey(name1) && nameCnt.containsKey(name2)){
            parent.put(name1, name2);
            cnt = nameCnt.get(name2) + 1;
            nameCnt.put(name2, cnt);
        }else{
            parent.put(name2, name1);
            cnt = nameCnt.get(name1) + nameCnt.get(name2);
            nameCnt.put(name1, cnt);
        }
    }
}

• Map<String, Integer> nameCnt 는 해당 정점이 몇개의 노드와 연결이 되어있는지 확인하는 것으로, 코드가 많지만 이유는 간단하다. 순서대로 다음과 같다.
  • 두 이름이 모두 처음 등장했을 때 → 왼쪽을 기준으로 부모 값을 설정
  • 두 이름 중 하나가 현재 누군가로부터 정점일 때 → 해당 노드를 기준으로 부모를 설정
  • 둘다 정점인 노드일때 → 왼쪽을 기준으로 두 그룹을 합쳐준다.

결론

• 경로를 압축하는 find 함수에서 put 메소드의 오버헤드라고 판단하여 이를 단순히 부모 값을 리턴하는 코드를 작성했지만 이번에는 메모리 초과가 아닌 틀렸다는 결과를 볼 수 있었다.

정답 코드

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

public class Main {
    static Map<String, Integer> cnt;
    static Map<String, String> parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            int num = Integer.parseInt(br.readLine());
            parent = new HashMap<>();
            cnt = new HashMap<>();
            for (int j = 0; j < num; j++) {
                String[] name = br.readLine().split(" ");

                for (int z = 0; z < 2; z++) {
                    if (!parent.containsKey(name[z])) {
                        parent.put(name[z], name[z]);
                        cnt.put(name[z], 1);
                    }
                }
                union(name[0], name[1]);

                bw.write((cnt.get(find(name[1]))) + "\n");
            }
        }

        bw.flush();
        bw.close();
        br.close();

    }

    static String find(String x){
        if (!x.equals(parent.get(x))) {
            parent.replace(x, find(parent.get(x))); 
        }
        return parent.get(x);
    }
    static void union(String x, String y){
        x = find(x);
        y = find(y);

        if(!x.equals(y)){
            parent.replace(y, x);
            cnt.replace(x, cnt.get(x) + cnt.get(y));
        }
    }
}

find

static String find(String x){
    if (!x.equals(parent.get(x))) {
        parent.replace(x, find(parent.get(x))); 
    }
    return parent.get(x);
}

크게 2가지를 변경했다.

• 자기 자신이 정점이 아닐 때 로 조건문을 수정해서 parent.get(x) 로 리턴하도록 수정
• put이 아닌 replace 를 사용

⭐ put vs replace

이미 존재하는 key의 value값을 업데이트 할때, replace를 사용하는 것이 당연할 수 있겠지만 왜 그런건지 내부 동작을 보면서 살펴봤다.

put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    if (table == null || table.length == 0) resize();

    int i = (n - 1) & hash;

    if (table[i] != null) {
        ...
    }

    table[i] = newNode(hash, key, value, null);

    if (++size > threshold) resize();

    return oldValue;
}

...

final Node<K, V>[] resize() {
      Node<K, V>[] oldTab = this.table;
      int oldCap = oldTab == null ? 0 : oldTab.length;
      int oldThr = this.threshold;
      int newThr = 0;
      int newCap;
        ...
}

• resize를 통한 배열 크기 확인
  • 크기가 threshold를 넘었을 때, resize를 호출해서 배열의 크기를 늘리면서 모든 노드를 재배치 하는 과정이 발생
• 중복 키라도 값비교 없이 항상 덮어 씌우기 때문에, 연산 비용이 증가 된다.

replace

public V replace(K key, V value) {
    Node e;
    if ((e = this.getNode(key)) != null) {
        V oldValue = e.value;
        e.value = value;
        this.afterNodeAccess(e);
        return oldValue;
    } else {
        return null;
    }
}

• 반면에, replace 는 탐색을 수행하고 새로운 값으로 변경하기 때문에 메모리 관점에서 훨씬 유리하게 작용하는 것이다.

union

static void union(String x, String y){
    x = find(x);
    y = find(y);

    if(!x.equals(y)){
        parent.replace(y, x);
        cnt.replace(x, cnt.get(x) + cnt.get(y));
    }
}

• 정점을 따로 구분하지 않고 Map<String, Integer> cnt 에 x 값을 기준으로 cnt를 더해서 저장한다.
• 여기서 x 값은 인풋값을 기준으로 왼쪽에 있는 노드를 무조건 부모로 사용한 것인데, 이럴 경우 모두 연결되었을 때 한명의 부모 값을 가지지 못하는 상황이 발생할 수 있다.

1
2
Fred Barney
Betty Fred

{Barney=Fred, Betty=Betty, Fred=Betty}

• 하지만 결국 연결된 노드들의 개수만 파악하면 되기 때문에 이전처럼 관계를 복잡하게 코드로 구현할 필요가 없었다.

소켓(Socket), 웹소켓(WebSocket)은 정확히 어떤 것이고, 어떤 차이를 가지고 있는가?

결론부터 말하면 다음과 같다.

• 소켓은 파일이며, OS 커널에 구현되어 있는 추상화된 인터페이스
• 웹소켓은 소켓을 기반으로하는 양방향 통신 프로토콜

차이점을 얘기하기에는 본질적으로 다른 개념이라는 것을 알게 되었고, 이 소켓(Socket)에 대해 더 자세히 알아보고자 한다.

소켓(Socket)이란?

소켓은 파일이다: 파일의 입출력(I/O) 관점에서 소켓 이해하기

위에서 언급한 것과 같이 소켓은 파일이며, OS 커널에 구현되어 있는 추상화된 인터페이스이다.

OS 커널?

운영체제의 핵심 부분으로, 하드웨어와 소프트웨어 사이에서 중재 역할을 하는 프로그램으로 복잡한 하드웨어 동작을 간단한 함수 호출로 사용할 수 있도록 제공되는 표준화된 인터페이스

즉, 응용 프로그램을 수행하는데 필요한 여러가지 서비스(중에 소켓이 존재), 컴퓨터의 자원(CPU, 메모리)를 관리하는 역할이다.

유저 모드 (User Mode)

• 애플리케이션이 동작하는 모드로, 커널에 직접 접근하지 않고, 커널이 제공하는 시스템 콜(system call)을 통해 작업 요청.
• 소켓 API(추상화된 인터페이스)를 사용해 네트워크 통신 요청을 전달

시스템 콜이란?

• 유저 모드와 커널 모드 간의 인터페이스
• 유저 모드에서 커널에 서비스를 요청하는 방법이로, 파일 입출력, 메모리 관리 등 작업에 사용

커널 모드 (Kernel Mode)

• 운영 체제의 핵심적인 기능(TCP/IP 스택 처리, 파일 시스템 접근 등)을 수행.
• TCP 프로토콜, IP 프로토콜의 동작을 직접 제어하고, 데이터를 처리함.
• 네트워크 계층에서 캡슐화:
  1. TCP 헤더 추가 → 데이터 세그먼트 생성.
  2. IP 헤더 추가 → 패킷 생성.

추가 : OS 커널

• 추상화란 복잡한 시스템의 내부 구현을 감추고, 간단하고 이해하기 쉬운 인터페이스만 제공하는 것을 의미한다.
• socket() - 소켓 생성, connect() - 소켓(cli)연결, 3-way handshake 과정 수행
• 위 함수와 같이 에플리케이션에서는 단순한 함수 호출하면, 시스템 콜을 통해 커널 모드에서 작업이 처리된다.

프로세스: 파일에 대한 주체

여기서 프로세스는 응용 프로그램 실행파일, 예를 들어 클라이언트-서버 모델에서 서버의 실행파일이 될 수 있는데 이러한 프로세스가 소켓(파일)에 대한 주체가 된다.

프로세스는 파일처럼 소켓을 열고(open) 닫으며(close), TCP/IP 프로토콜을 사용하는 TCP 소켓일 경우

• write -> send : 데이터를 네트워크로 보냄 (서버 자원을 네트워크를 통해 보냄)
• read -> receive : 네트워크에서 데이터를 읽음(네트워크를 통해 들어온 데이터를 읽음)

요약

• 소켓(Socket)은 애플리케이션의 프로세스가 네트워크를 사용하기 위한 통로이다.
• 파일로써, 데이터 입출력(I/O)과정을 통해 역할을 수행한다.

Q: 모든 클라이언트가 80번 포트를 통해 연결되는가?

• NO
  • 80번 포트는 초기 연결 시에만 사용
  • 클라이언트가 서버와 연결된 이후, 서버는 클라이언트와의 통신을 위해 새로운 동적 포트(49152~65535)를 할당
  • 따라서 80번 포트는 "들어오는 요청의 진입점" 역할

WWW란?

• World Wide Web은 인터넷에 연결된 사용자들이 서로의 정보를 공유할 수 있는 공간으로, 정확히 말해 인터넷 상의 인기 있는 하나의 서비스이다.
• 웹 서버는 HTTP 프로토콜을 사용하며 클라이언트(웹 브라우저)는 TCP 포트 번호 80번을 이용해 서버와 연결을 시도한다.

Port

• 0 - 1023 : well -known port
  • 특정 서비스, 프로토콜이 표준화된 포트 번호
  • ex) 80 - HTTP, 443 - HTTPS
• 1024 - 49151 : registered port
  • 특정 애플리케이션이나 서비스가 사용하기 위해 IANA(Internet Assigned Numbers Authority) 에 의해 등록된 포트를 말한다.
  • ex ) 8080 - 웹 프록시 서버, 3306 - MySQL 데이터베이스
• 49152 - 65535 : dynamic port
  • 클라이언트가 서버와 통신을 위해 임시로 할당하는 포트를 말한다.

클라이언트 - 서버 모델

1. 사용자가 웹 브라우저에서 서버 이름을 입력한다. (GET)

2. DNS 서버를 통해 해당 도메인에 등록된 IP 주소를 응답받는다.

이 과정에서는 UDP 통신을 사용한다.

3. 서버는 들어온 요청에 대한 정적 파일을 클라이언트에게 응답한다. (POST)

• Remote Address를 보면 www.korean.go.kr의 IP 주소가 124.137.201.220인 것을 알 수 있다. 또한, port 번호를 443을 사용하기 때문에 HTTPS 프로토콜이라는 것을 알 수 있다.

• Response Headers에 Content-Type 을 보면 text/html 것을 확인할 수 있다.

실제로 응답된 html

HTTP 프로토콜

HTTP란?

• HyperText Transfer Protocol으로 분산 하이퍼미디어 환경에서 빠르고 간편하게 데이터를 전송하는 프로토콜.
• 서버는 80번 포트에서 대기하고, 클라이언트는 TCP를 사용해 연결을 설정

State vs Stateless

Q. 상태가 있는 시스템이 확장이 어려운 이유?

• 서버간 세션 동기화
  • A에서 저장된 세션 정보를 B서버에서도 사용할 수 있어야한다.
  • 세션 데이터를 동기화하려면 네트워크 비용, 지연이 발생하며 서버 수가 늘어날 수록 동기화가 어려워지고 성능 저하가 발생한다.

Q. JWT 기반 인증 방식은 State일까 Stateless일까?

• Stateless이다. 표를 보면 다음과 같이 구분할 수 있다.

요청 메세지와 응답 메세지

멱등성이란?

• 동일한 작업을 여러 번 수행해도 그 결과가 처음 한번 수행 했을 때와 동일한 상태를 유지하는 성질
• GET, PUT, DELETE, HEAD
• 반면에 POST는 멱등성을 가지지 않는다.

GET 요청 후 응답 예시

DNS

IP 주소 클래스

네트워크 주소는 장치들을 그룹화하고, 호스트 주소는 해당 그룹 내에서 개별 장치를 식별한다.

Q. 유니캐스팅 vs 멀티캐스팅

유니캐스팅은 1대1 통신 방식으로 단일 수신자를 대상으로 데이터 전송하기 때문에 특정 IP 주소를 기반으로 특정 host에게만 데이터를 전달한다.

멀티캐스팅은 1대다 통신 방식으로 특정 그룹에 속한 수신자에게 동시에 데이터를 전송한다. 그래서 전부 네트워크 주소로 이루어진 D클래스가 해당 통신방식을 지원한다.

추가 A,B,C 클래스는 단일 호스트 통신에 최적화 되어있는 경우로, 네트워크와 호스트를 명확하게 구분하기 때문에 멀티캐스팅을 지원하기에는 부적합하다.

DNS가 필요한 이유?

IP주소의 문자 표현

• IPv4에서 32bit의 주소를 8비트 씩 10진수로 바꿔 표현한다. 하지만 이러한 주소 표현도 사용자 입장에서 특정 호스트 서버에 접근하는데 어려움이 있기 때문에 문자로 된 호스트 이름을 추가로 정의했다.

초기 DNS 관리 방법

• 문자로된 호스트 이름을 추가로 정의했기 때문에 특정 IP와 매칭시킨 정보가 필요.
• 컴퓨터 시스템이 전체 호스트의 명칭 정보를 관리했지만 호스트가 증가하면서 모든 호스트의 정보를 유지하기가 불가능해졌다.
• 이로 인해, DNS 서비스가 등장했다.

DNS 서비스의 동작과정

DNS 서비스란?

• 도메인 이름에서 IP주소를 얻을 수 있는 분산 데이터베이스 시스템.
• 해석기는 UDP를 이용해 자신이 위치한 지역의 DNS 네임 서버에 변환을 요청하여 IP주소를 얻을 수 있다.

DNS 서비스의 계층 구조 - 네임스페이스

• 도메인 이름을 체계적으로 관리하고 구분하는 계층적 구조를 말한다.
• 최상위에 이름이 없는 Root가 존재하고, Root 바로 밑에 위치한 호스트인 TLD(Top Level Domain) 이 있다.
  • 보통, TLD는 com, net 처럼 기구의 이름이나 kr, us와 같이 일반 도메인과 별도로 국가 코드를 정의한다.

Spring boot에서 엿보는 DNS

Spring boot 프로젝트를 생성 시, 볼 수 있는 인터페이스인데 이와 같이 Group, Package name으로 네임스페이스와 같은 계층 구조로 프로젝트를 생성하는 것을 알 수 있다.

동작과정

동작과정을 설명하기 전에 네임 서버와 DNS 서비스가 분산된 데이터베이스 시스템이라는 것을 알고 있어야한다.

네임 서버와 존

위 사진과 같이 네임 서버 즉, 실제 도메인 이름과 IP 주소 간의 매핑 정보를 제공하는 곳은 존에 따라 분류된다.

네임 서버의 종류

1. 루트 네임 서버
   • 도메인 네임스페이스의 최상위 레벨을 관리한다.
   • ex) .com, .org, .net과 같은 TLD에 대한 정보를 제공한다.
2. TLD 네임 서버
   • 각 최상위 도메인(TLD)에 대한 정보를 관리한다.
   • ex) .com에 속한 모든 도메인의 정보를 관리한다.
3. 권한 네임 서버
   • 특정 도메인에 대한 최종 정보를 제공한다.
   • ex) example.com의 IP 주소에 대한 정확한 매핑 정보를 제공한다.
4. 캐시 네임 서버
   • 자주 요청된 DNS 정보를 캐싱하여 저장하고, 빠르게 응답한다.
   • ex) 사용자가 이전에 방문한 사이트의 DNS 정보를 임시로 저장한다.

동작과정 1. (비)재귀적 처리

1. 해석기에서 가장 가까운 네임 서버(로컬 네임 서버)와 접촉해 IP 주소를 요청하고 다른 네임서버에 요청을 재귀적으로 수행하면서 IP주소를 응답받는다.
   • 해석기 : 도메인 이름과 호스트 주소의 변환 정보를 원하는 네트워크 응용 프로그램
2. 로컬 네임 서버가 보관하고 있는 캐시 정보를 회신함으로써 재귀적인 호출 없이 IP주소를 응답받을 수 있다.

• 만약에 내가 www.naver.com 의 대한 IP주소를 원한다면 com을 관리하는 네임서버(존으로 분류)에 요청을 하고 해당 존은 naver를 관리하는 네임 서버에 요청을 반복하면서 최종적으로 www.naver.com의 IP주소를 응답 받을 수 있는 것이다.

동작과정 2. 반복적 처리

재귀적인 처리 방법과는 다르게 로컬 네임 서버가 반복적으로 직접 여러 네임서버에 접촉해서 부족한 정보를 모두 채워나가 IP주소를 응답하는 방식이다.

Q. 서버가 도메인 주소로 IP주소를 얻는 과정에 대해서 설명하시오.

DNS 서비스를 이용해 IP 주소를 얻을 수 있다. 클라이언트가 웹 브라우저에서 도메인 주소로 요청을 보내면 DNS 서버에 해석기가 요청을 보내 재귀적 처리 혹은 반복적 처리를 통해 IP 주소를 응답 받을 수 있다.

추가 일반적으로 재귀적 처리는 웹사이트 접근 시 사용된다.

• 클라이언트가 단순히 요청만 하기 때문에 간편하다
• DNS 해석기가 주간 결과를 캐시해서 재사용이 가능하다.

반면에 반복적 처리는 네트워크 디버깅, DNS 테스트에서 사용된다.

• 각 네임 서버가 자신의 역할만 수행하기 때문에 특정 서버에 과도한 부하가 걸리지 않는다.

Q. 그럼 재귀적 호출은 각 네임 서버가 자신의 역할만 수행하는게 아닌건가?? => 재귀적 호출은 최종 IP주소를 찾을 때까지 모든 과정을 처리하는데, 자신이 요청받은 도메인의 IP주소를 모를 경우 자신 영역 외의 요청도 처리하며, 답을 찾아 클라이언트에게 전달하기 때문이다.

출처: 캡쳐된 사진을 출처는 "쉽게 배우는 데이터 통신과 컴퓨터 네트워크 - 박기현"에서 인용한 자료입니다.

코딩 테스트 문제를 풀다가 다음과 같은 코드를 작성했는데 내가 예상하지 못하는 결과가 나왔다.

코드

...

List<Set<Integer>> pCard = new ArrayList<>();  
for (int i = 0; i < 3; i++) {  
    pCard.add(new HashSet<>());  
}

... // 대충 pCard.get(num).add 하는 코드


while(true){
    ...

    Set<Integer> temp = pCard.get(i);

    for (int j = 0; i + j * 3 < N; j++) {  
        if (temp.contains(card[i + j * 3])) {  
            temp.remove(card[i + j * 3])
        }  
    }
    ...
}

코드를 보면 Set<Integer> 를 List로 여러개 만들고 확인되는 값이 있으면 지워서 중복으로 되는 경우를 제거할 수 있도록 했다.

하지만, 반복문을 돌면서 원래 pCard의 Set이 remove가 되어 제대로 결과를 출력하지 못하게 되는데..

예시 코드

Set<Integer> init = new HashSet<>();  
init.add(1);  
init.add(2);  
init.add(3);  

System.out.println("init = " + init);  

Set<Integer> test = init;  
test.remove(3);  

System.out.println("init = " + init);  


출력 결과
init = [1, 2, 3]
init = [1, 2]

결과를 보면 분명 test의 있는 3을 remove했는데 init에도 결과가 반영된 것을 볼 수 있다. 그렇다면 왜 그런걸까?

객체 참조

문제에 대한 답은 객체 참조에서 알 수 있다. 객체 참조에 대해서 설명하기 전에 용어에 대해서 짚고 넘어가자

객체(Object)

Heap 메모리에 저장되는 실제 데이터를 말한다. 예를 들어, new String("Hello") 와 같은 명령어는 Heap 메모리에 "Hello"라는 문자열 객체를 생성한다.

참조(Reference)

객체가 Heap 메모리에 저장된 위치를 가리키는 변수를 말한다. 참조는 객체의 메모리 주소를 저장하지만, Java에서는 직접 주소를 다룰 수 없고 참조 변수를 통해서만 접근이 가능하다.

String greeting = new String("Hello");

즉, 다음과 같은 코드에서 greeting은 위치(주소), "Hello"는 Heap 메모리에 있는 데이터인 것이다.

이유는?

Set<Integer> init = new HashSet<>();  
init.add(1);  
init.add(2);  
init.add(3);  

System.out.println("init: " + init);  
System.out.println("init hash: " + System.identityHashCode(init));  

Set<Integer> test = init;  
System.out.println("test hash before modification: " + System.identityHashCode(test));  

test.remove(3);  

System.out.println("init after modification: " + init);  
System.out.println("test hash after modification: " + System.identityHashCode(test));


출력 결과
init: [1, 2, 3]
init hash: 288665596
test hash before modification: 288665596
init after modification: [1, 2]
test hash after modification: 288665596

객체가 참조하는 주소값을 출력해보면 다음과 같다. 288665596으로 test는 init과 같이 같은 주소를 참조하고 있는 것을 확인할 수 있다.

그래서 test를 수정하더라도 실제로 init이 가리키는 heap 메모리에 영역의 데이터를 수정하기 때문에 결과가 반영되는 것이다.

identityHashCode? 객체 고유한 해시 코드를 반환하는 메서드로, 객체의 메모리 참조 기준으로 생성되는 hashCode이다.

new로 새로운 객체를 생성하고 할당하면?

...

Set<Integer> test = new HashSet<>();  
test = init;

...

새로운 객체를 만들고 기존 데이터를 할당하면 어떻게 될까?

결론부터 말하면 Variable 'test' initializer 'new HashSet<>()' is redundant 다음과 같은 메세지를 출력한다. 대충 변수 test 초기화가 중복된다는 의미인데 자세한 이유는 다음과 같다.

1. Set<Integer> test = new HashSet<>();
   • test 라는 변수를 new HashSet<>()으로 초기화한다.
   • 이 시점에서, test는 빈 HashSet을 가리킨다.

2. test = init;
   • 이후 test에 init을 할당한다.
   • 결국, test가 가리키는 객체는 init으로 변경된다.

결론

대학 1학년, 객체 지향 프로그래밍 수업에서 C++ 로 지겹도록 배웠던 개념인데 자바를 계속 사용하면서 기본적인 것을 잊고 있었던 것 같다.😢

문제 링크

문제 설명

구현 문제로, 미세먼지를 확산시키는 과정은 일반적으로 그래프 탐색에서 사용하는 방법으로 코드를 구현하면 된다. 다만, 자신이 확산시키는 것과 인접한 칸에서 확산되어서 오는 값을 합할 때, 현재 누적값으로 확산하는 것이 아닌 원래 가지고 있던 값을 확신시켜야 한다. 이어서, 바람의 방향대로 한칸씩 값을 밀어야 하는데 바람이 처음 나오는 칸이 0이 되기 때문에 역순으로 반복해서 구현했다.

문제 풀이(정답)

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

public class Main {  
    static int[][][] map;  
    static int[][] cleaner = new int[2][2];  

    static Queue<Node> dust = new LinkedList<>();  

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

        StringTokenizer st = new StringTokenizer(br.readLine());  

        int r = Integer.parseInt(st.nextToken());  
        int c = Integer.parseInt(st.nextToken());  
        int t = Integer.parseInt(st.nextToken());  

        map = new int[r][c][2];  

        int temp = 0;  
        for (int i = 0; i < r; i++) {  
            st = new StringTokenizer(br.readLine());  
            for (int j = 0; j < c; j++) {  
                map[i][j][0] = Integer.parseInt(st.nextToken());  
                if (map[i][j][0] == -1) {  
                    // 공기 청정기의 위치  
                    cleaner[temp][0] = i;  
                    cleaner[temp][1] = j;  
                    temp++;  
                } else if (map[i][j][0] != 0) {  
                    dust.add(new Node(i, j));  
                }  
            }  
        }  
        // 공기 청정기 위아래 확인  
        if (cleaner[0][1] < cleaner[1][1]) {  
            temp = cleaner[0][1];  
            cleaner[0][1] = cleaner[1][1];  
            cleaner[1][1] = temp;  
        }  
        // n초 후 새로운 Q를 넣기전 먼지가 확산된 상태 list  

        int[] dr = {-1, 1, 0, 0};  
        int[] dc = {0, 0, -1, 1};  

        int result = 0;  

        for (int i = 0; i < t; i++) {  
            Set<Node> check = new HashSet<>();  
            while (!dust.isEmpty()) {  
                Node current = dust.poll();  
                // 값이 업데이트(먼지) 되야하는 list                int divideValue = map[current.getR()][current.getC()][0] / 5;  
                int cnt = 0;  
                for (int j = 0; j < 4; j++) {  
                    int nr = current.getR() + dr[j];  
                    int nc = current.getC() + dc[j];  

                    if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc][0] != -1) {  
                        map[nr][nc][1] += divideValue;  
                        check.add(new Node(nr, nc));  
                        cnt++;  
                    }  
                }  
                map[current.getR()][current.getC()][0] -= (divideValue * cnt);  
                if (map[current.getR()][current.getC()][0] > 0) {  
                    check.add(new Node(current.getR(), current.getC()));  
                }  
            }  

            for (Node node : check) {  
                int nr = node.getR();  
                int nc = node.getC();  
                map[nr][nc][0] += map[nr][nc][1];  
                map[nr][nc][1] = 0;  
            }  


            // 공기청정기 작동 (상단 반시계방향)  
            int upper = cleaner[0][0];  
            for (int j = upper - 1; j > 0; j--) {  
                map[j][0][0] = map[j - 1][0][0];  
            }  
            for (int j = 0; j < c - 1; j++) {  
                map[0][j][0] = map[0][j + 1][0];  
            }  
            for (int j = 0; j < upper; j++) {  
                map[j][c - 1][0] = map[j + 1][c - 1][0];  
            }  
            for (int j = c - 1; j > 1; j--) {  
                map[upper][j][0] = map[upper][j - 1][0];  
            }  
            map[upper][1][0] = 0;  // 공기청정기에서 나오는 바람  

            // 공기청정기 작동 (하단 시계방향)  
            int lower = cleaner[1][0];  
            for (int j = lower + 1; j < r - 1; j++) {  
                map[j][0][0] = map[j + 1][0][0];  
            }  
            for (int j = 0; j < c - 1; j++) {  
                map[r - 1][j][0] = map[r - 1][j + 1][0];  
            }  
            for (int j = r - 1; j > lower; j--) {  
                map[j][c - 1][0] = map[j - 1][c - 1][0];  
            }  
            for (int j = c - 1; j > 1; j--) {  
                map[lower][j][0] = map[lower][j - 1][0];  
            }  
            map[lower][1][0] = 0;  // 공기청정기에서 나오는 바람  

            for (int j = 0; j < r; j++) {  
                for (int k = 0; k < c; k++) {  
                    if(map[j][k][0] > 0){  
                        if(i == t-1){  
                            result += map[j][k][0];  
                        }else{  
                            dust.add(new Node(j, k));  
                        }  
                    }  
                }  
            }  
        }  

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


    static class Node {  
        int r;  
        int c;  

        public Node(int r, int c) {  
            this.r = r;  
            this.c = c;  
        }  

        int getR() {  
            return this.r;  
        }  

        int getC() {  
            return this.c;  
        }  

    }  

}

미세먼지 확산

...

map = new int[r][c][2];  

...

Set<Node> check = new HashSet<>();  
while (!dust.isEmpty()) {  
    Node current = dust.poll();  
    // 값이 업데이트(먼지) 되야하는 list                
    int divideValue = map[current.getR()][current.getC()][0] / 5;  
    int cnt = 0;  
    for (int j = 0; j < 4; j++) {  
        int nr = current.getR() + dr[j];  
        int nc = current.getC() + dc[j];  

        if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc][0] != -1) {  
            map[nr][nc][1] += divideValue;  
            check.add(new Node(nr, nc));  
            cnt++;  
        }  
    }  
    map[current.getR()][current.getC()][0] -= (divideValue * cnt);  
    if (map[current.getR()][current.getC()][0] > 0) {  
        check.add(new Node(current.getR(), current.getC()));  
    }  
}  

for (Node node : check) {  
    int nr = node.getR();  
    int nc = node.getC();  
    map[nr][nc][0] += map[nr][nc][1];  
    map[nr][nc][1] = 0;  
}  

• 입력받은 row, col의 크기와 한 차원을 추가해 3차원 배열로 선언했다. 이유는 다음과 같다.
  • map[r][c][0] 는 현재 미세먼지 값, 즉 해당 칸이 확산할 때 사용할 미세먼지의 값이다.
  • map[r][c][1] 는 다른 인접한 칸으로 인해 확산된 값을 누적해서 더한 값이다.
• 이전에 입력시, dust에 Node 객체로 미세먼지가 있는 위치를 add 해두었기 때문에 q가 빌때까지 반복한다.
• 4방향으로 미세먼지 확산 연산을 해준 이후, 미세먼지 값이 있는 칸을 hashSet에 넣어
  • map[r][c][1] 확산을 통해 얻은 값과 map[r][c][0] 확산하고 남은 값을 더한다.

공기청정기 동작

// 공기청정기 작동 (상단 반시계방향)  
int upper = cleaner[0][0];  
for (int j = upper - 1; j > 0; j--) {  
    map[j][0][0] = map[j - 1][0][0];  
}  
for (int j = 0; j < c - 1; j++) {  
    map[0][j][0] = map[0][j + 1][0];  
}  
for (int j = 0; j < upper; j++) {  
    map[j][c - 1][0] = map[j + 1][c - 1][0];  
}  
for (int j = c - 1; j > 1; j--) {  
    map[upper][j][0] = map[upper][j - 1][0];  
}  
map[upper][1][0] = 0;  // 공기청정기에서 나오는 바람  

// 공기청정기 작동 (하단 시계방향)  
int lower = cleaner[1][0];  
for (int j = lower + 1; j < r - 1; j++) {  
    map[j][0][0] = map[j + 1][0][0];  
}  
for (int j = 0; j < c - 1; j++) {  
    map[r - 1][j][0] = map[r - 1][j + 1][0];  
}  
for (int j = r - 1; j > lower; j--) {  
    map[j][c - 1][0] = map[j - 1][c - 1][0];  
}  
for (int j = c - 1; j > 1; j--) {  
    map[lower][j][0] = map[lower][j - 1][0];  
}  
map[lower][1][0] = 0;  // 공기청정기에서 나오는 바람

• 공기청정기가 나온 방향은 0이 되기 때문에 공기청정기로 들어오는 쪽부터 연산을 해서 한칸씩 값을 밀어서 미세먼지 값을 업데이트 한다.

결과 출력 및 다음 초 연산 준비

for (int j = 0; j < r; j++) {  
    for (int k = 0; k < c; k++) {  
        if(map[j][k][0] > 0){  
            if(i == t-1){  
                result += map[j][k][0];  
            }else{  
                dust.add(new Node(j, k));  
            }  
        }  
    }  
}   

System.out.println(result);  

• 반복해서 현재 result에 값을 누적해서 저장한다. 현재 실행중인 로직이 마지막 연산일 때는 해당 연산을, 아닐 경우에는 다음 초에서 확인할 미세먼지의 위치를 node객체로 dust(queue)에 추가한다.

결과

정답은 맞았지만 다른 사람들의 제출 결과를 보니 메모리와 시간이 비교적 높은 것을 알 수 있었다. 그래서 다른 코드들을 참고해서 좀 더 개선된 코드를 만들어봤다.

코드 개선

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

public class Main {

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int t = Integer.parseInt(st.nextToken());

        int[][] map = new int[r][c];
        int[][] cleaner = new int[2][2];

        int temp = 0;
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == -1) {
                    cleaner[temp][0] = i;
                    cleaner[temp][1] = j;
                    temp++;
                }
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};


        while (t-- > 0) {
            int[][] check = new int[r][c];

            // 확산 상태 채크
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    if (map[i][j] > 0) {
                        check[i][j] = map[i][j];
                    }
                }
            }
            // 확산
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    if (check[i][j] > 0) {
                        for (int k = 0; k < 4; k++) {
                            int nr = i + dr[k];
                            int nc = j + dc[k];
                            if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc] != -1) {
                                map[nr][nc] = map[nr][nc] + check[i][j] / 5;
                                map[i][j] = map[i][j] - (check[i][j] / 5);
                            }
                        }
                    }
                }
            }
            int upper = cleaner[0][0]; // ex 2
            for (int i = upper - 1; i > 0; i--) {
                map[i][0] = map[i - 1][0];
            }
            for (int i = 0; i < c - 1; i++) {
                map[0][i] = map[0][i + 1];
            }
            for (int i = 0; i< upper; i++){
                map[i][c-1] = map[i+1][c-1];
            }
            for(int i = c-1; i>1; i--){
                map[upper][i] = map[upper][i-1];
            }
            map[upper][1] =0;

            int lower = cleaner[1][0];
            for (int j = lower + 1; j < r - 1; j++) {
                map[j][0] = map[j + 1][0];
            }
            for (int j = 0; j < c - 1; j++) {
                map[r - 1][j] = map[r - 1][j + 1];
            }
            for (int j = r - 1; j > lower; j--) {
                map[j][c - 1] = map[j - 1][c - 1];
            }
            for (int j = c - 1; j > 1; j--) {
                map[lower][j] = map[lower][j - 1];
            }
            map[lower][1] = 0;
        }
        int result = 0;

        for(int i=0; i< r; i++){
            for(int j=0; j< c; j++){
                if(map[i][j] != -1){
                    result += map[i][j];
                }
            }
        }
        System.out.println(result);

        br.close();
    }
}

• 대부분의 연산 과정은 동일하지만 일단 Queue를 사용하지 않고 매번 반복문을 통해 미세먼지가 있는 부분을 찾아서 확산하도록 코드를 변경했다.

if (nr >= 0 && nr < r && nc >= 0 && nc < c && map[nr][nc] != -1) {  
    map[nr][nc] = map[nr][nc] + check[i][j] / 5;  
    map[i][j] = map[i][j] - (check[i][j] / 5);  
}

• 추가로 3차원 배열을 사용하지 않고 매초마다 현재 미세먼지 값을 측정하는 2차원 배열을 만들어, 해당 배열을 사용해 미세먼지가 있는 위치 및 확산에 사용할 미세먼지의 값을 계산하는데 이용해 간결하게 코드를 수정했다.

결론

공기청정기 작동시키는 동작에서 생각보다 오래 시간이 걸렸다. 코드를 개선해보며 결과적으로, 가장 먼저 작성했더 코드에 비해 메모리는 약 1/7배 , 시간은 2000ms 넘게 감소시켰다. 맞은 것도 물론 중요하지만, 좀 더 효율적인 코드를 작성하는 습관을 익혀야겠다.

문제 링크

문제 설명

해시를 사용하는 간단한 문제로 풀기 전 고민했던 부분은 3가지가 있었다.

1. 문자열을 분리해서 이름과 출입 여부에 관한 문자열로 나눠야한다.
2. Set을 통해 동일한 이름의 직원이 중복해서 들어가지 않도록하며, 출입 여부에 따라 삽입, 삭제 해야한다.
3. 출력시, 알파벳 기준 내림차순으로 정렬해야한다.

TreeSet 사용한 풀이 (정답)

코드

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

public class Main {  

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

        Set<String> employees = new TreeSet<>(Collections.reverseOrder());  

        int n = Integer.parseInt(br.readLine());  

        for (int i = 0; i < n; i++) {  
            String temp = br.readLine();  
            String[] employ = temp.split(" ");  

            if(employ[1].equals("enter")){  
                employees.add(employ[0]);  
            }else{  
                employees.remove(employ[0]);  
            }  
        }  

        for (String employee : employees) {  
            System.out.println(employee);  
        }  

    }  

}

TreeSet

Set<String> employees = new TreeSet<>(Collections.reverseOrder());  

• TreeSet은 기본적으로 오름차순으로 순서를 보장해서 저장하기 때문에 Collections.reverseOrder()를 사용하여 내림차순으로 저장되도록 한다.

문자열 분리

String[] employ = temp.split(" ");  

    if(employ[1].equals("enter")){  
        employees.add(employ[0]);  
    }else{  
        employees.remove(employ[0]);  
    }  

• "Baha enter", "Baha leave" 등 공백을 기준으로 이름과 출입 여부에 관한 문자열이 나뉜다.
  • 공백을 기준으로 문자열을 분리해 배열에 저장해서 출입 여부에 따라 add, remove를 결정한다.

출력

// 방법 1
for (String employee : employees) {  
    System.out.println(employee);  
} 

// 방법 2
Iterator<String> iter = employees.iterator();  

while(iter.hasNext()){  
    System.out.println(iter.next());  
}

• 방법 1
  • 이미 순서를 보장한 TreeSet을 사용했기 때문에 요소를 처음부터 하나씩 출력한다.
• 방법 2
  • Iterator 타입으로 변환 후에 hasNext() 즉, 다음 요소가 있을 때까지 반복하며 출력한다.

결론

이전 문제에서 Set의 중요성에 대해서 좀 알 수 있었는데 TreeSet과 정렬 순서를 바꾸는 등, 이와 같은 것을 숙지해두고 실전 상황에서 바로 적용시킬 수 있도록 해야할 것 같다.

문제 링크

문제 설명

시작 단어를 주어진 값을 활용해서 target 단어로 변환하여 단어를 바꾼 횟수를 계산하는 문제이다. 추가로, 한 번에 한 개의 알파벳만 바꿀 수 있다는 조건이 있다. 해당 문제와 조건을 보고 다음과 같은 주요 로직을 생각해봤다.

• 현재 단어와 바꿀 단어가 1개만 차이나는지 확인해야 한다.
• 주어진 단어 중에 target 단어가 없으면 굳이 동작을 수행 할 필요가 없다.
• 깊이, 너비 중 어떤 탐색을 통해 해야하는가?

1. DFS와 백트래킹을 사용한 접근 ( 실패 )

처음에 가장 먼저 떠오른건 DFS와 백트래킹을 사용하여 되는 경우를 찾아보는 것이다. (이전에 풀었던 문제가 백트래킹을 사용했 던 것이라 그런 것 같다.).

코드

class Solution {
    boolean[] visited;
    int answer;
    public int solution(String begin, String target, String[] words) {
        visited = new boolean[words.length];
        answer = 0;
        dfs(begin, target, words, 0);
        return answer;
    }
    void dfs(String word, String target, String[] words, int len){

        if(word.equals(target)){
            answer = len;
            return;
        }

        if(len == words.length){
            return;
        }

        for(int i=0; i < words.length; i++){
            if(!visited[i]){
                visited[i] = true;

                int cnt = 0;
                for(int j=0; j<word.length(); j++){
                    if(word.charAt(j) != words[i].charAt(j)){
                        cnt++;
                    }
                    if(cnt > 1){
                        break;
                    }                    
                }
                if(cnt <= 1){
                    dfs(words[i], target, words, len+1);
                }
            }
            visited[i] = false;
        }
    }
}

• 방문 정보를 확인하며 깊이 우선 탐색을 통해 되는 경우를 확인한다.
• 현재 단어와 비교할 단어의 길이만큼 차이를 비교해서 2개 이상 차이날 경우는 탐색하지 않는다.

결과

3번째 테스트에서 시간 초과가 발생했다. 문제 원인으로는 2가지 정도가 있을 것이라고 추측했다.

1. 단어를 비교하는 로직의 시간 복잡성
2. 깊이 우선 탐색 시, 최악의 경우 연산량이 많아진다.
   • 단어의 개수를 50(최대)개라고 했을 때, 한번 최대 깊이로 갈 때,50 * 49 * 48 * ... * 41 정도의 연산이 필요한데 마지막에 답을 찾을 경우, 너무 많은 연산이 이뤄진다.

3. 주어진 단어 중에 target 단어가 없을 때 확인

• 해당 문제는 없어도 크게 상관 없을 것 같아 고려하지 않았다.

일단, 깊이 우선 탐색이 가장 문제 될 것 같아. Queue를 사용해 너비 우선 탐색으로 풀어봤다.

2. BFS를 사용한 접근 방식 (성공)

코드

import java.util.*;

class Solution {
    class Node{
        String word;
        int len;

        public Node(String word, int len){
            this.word = word;
            this.len = len;
        }
        String getWord(){
            return this.word;
        }
        int getLen(){
            return this.len;
        }
    }
    int answer;
    public int solution(String begin, String target, String[] words) {
        answer = 0;

        Queue<Node> q = new LinkedList<>();

        q.add(new Node(begin, 0));

        while(!q.isEmpty()){
            Node current = q.poll();

            if(current.getLen() > words.length){
                break;
            }
            if(current.getWord().equals(target)){
                answer = current.getLen();
                break;
            }
            for(int i=0; i<words.length; i++){
                boolean check = checkWord(current.getWord(), words[i]);
                if(check){
                    q.add(new Node(words[i], current.getLen()+1));
                }
            }
        }
        return answer;
    }
    boolean checkWord(String a, String b){
        int cnt = 0;
        for(int i=0; i<a.length(); i++){
            if(a.charAt(i) != b.charAt(i)){
                cnt++;
            }
            if(cnt>1){
                break;
            }
        }
        if(cnt < 2){
            return true;
        }else{
            return false;
        }
    }

}

a. Class Node

class Node{
    String word;
    int len;

    public Node(String word, int len){
        this.word = word;
        this.len = len;
    }
    String getWord(){
        return this.word;
    }
    int getLen(){
        return this.len;
    }
}

• 가장 먼저 단어와 현재 깊이를 가질 수 있는 Node 클래스를 선언했다. 여기서 Len이 현재 깊이를 의미하며 최대 깊이는 words의 length일 것이다.

b. Solution

    public int solution(String begin, String target, String[] words) {
        answer = 0;

        Queue<Node> q = new LinkedList<>();

        q.add(new Node(begin, 0));

        while(!q.isEmpty()){
            Node current = q.poll();

            if(current.getLen() > words.length){
                break;
            }
            if(current.getWord().equals(target)){
                answer = current.getLen();
                break;
            }
            for(int i=0; i<words.length; i++){
                boolean check = checkWord(current.getWord(), words[i]);
                if(check){
                    q.add(new Node(words[i], current.getLen()+1));
                }
            }
        }
        return answer;
    }

• 첫번째 단어와, 0(len)을 Queue에 넣고 반복을 시작
• 현재 노드가 최대 깊이(words.length)보다 클 경우, 반복문을 종료
  • 방문 처리를 따로 하지 않기도 했고, words.length보다 더 많이 탐색할 수 없기 때문이다.
• 현재 노드의 단어가 target단어와 같다면 answer에 len을 할당하고 종료 (정답을 추출하는 부분)
• 현재 단어와 바꿀 단어를 비교하는 로직은 그대로 사용했으나 함수로 만들어서 사용했다.
  • 한 글자만 다르다면 Queue에 삽입하고 , len을 1 증가시킨다.

결과

이전에 통과 못했던 테스트 3를 통과해서 정답을 맞췄다. 하지만 여전히 테스트 3의 실행 시간이 다른 테스트에 비해 매우 긴 것을 볼 수 있고 완벽히 최적의 해를 찾은 건 아닌 것 같았다.

Review

친구와 푼 문제를 리뷰화는 과정에서 이전 정답에서 완벽히 해결하지 못했던 부분의 문제를 알 수 있었다. 단어끼리 틀린 개수를 확인하는 로직이 문제였는데, 기존 내가 작성한 정답을 생각해보면 단어의 길이가 10일 때, 대충 다음과 같은 연산 수를 가지게 된다. (단어 개수는 50개) depth 1 일 때, 10 * 50 depth 2 일 때, 10 * 50 * 50 ... 최악의 경우를 생각하면 대략 계산만 해도 마지막 depth 일 때, 10 * 10 * 50 ^ 50 정도 되는 것 같다.. ^^; (정확하지 않을 수 있다.)

코드

import java.util.*;

public class Solution {
    public int solution(String begin, String target, String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        Set<String> visited = new HashSet<>();
        int answer = 0;

        int wordSize = words[0].length();

        // 큐에 시작 단어와 변환 횟수를 담음
        Queue<Pair> queue = new LinkedList<>();
        queue.offer(new Pair(begin, 0));
        visited.add(begin);

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            String word = current.word;
            int count = current.count;

            // 목표 단어에 도달한 경우
            if (word.equals(target)) {
                return count;
            }

            // 단어의 각 문자를 하나씩 바꿔가며 탐색
            for (int i = 0; i < wordSize; i++) {
                for (char j = 'a'; j <= 'z'; j++) {
                    char[] tempArr = word.toCharArray();
                    tempArr[i] = j;
                    String temp = new String(tempArr);

                    // 바꾼 단어가 words 목록에 있고, 아직 방문하지 않은 경우
                    if (wordSet.contains(temp) && !visited.contains(temp)) {
                        queue.offer(new Pair(temp, count + 1));
                        visited.add(temp);
                    }
                }
            }
        }

        return answer; // target에 도달하지 못한 경우
    }

    // 단어와 변환 횟수를 저장할 클래스
    class Pair {
        String word;
        int count;

        Pair(String word, int count) {
            this.word = word;
            this.count = count;
        }
    }
}

변경된 주요 코드를 보면 다음과 같다.

Set<String> wordSet = new HashSet<>(Arrays.asList(words));
Set<String> visited = new HashSet<>();

...

for (int i = 0; i < wordSize; i++) {
    for (char j = 'a'; j <= 'z'; j++) {
        char[] tempArr = word.toCharArray();
        tempArr[i] = j;
        String temp = new String(tempArr);

        // 바꾼 단어가 words 목록에 있고, 아직 방문하지 않은 경우
        if (wordSet.contains(temp) && !visited.contains(temp)) {
            queue.offer(new Pair(temp, count + 1));
            visited.add(temp);
        }
    }
}

• 방문 단어를 다시 탐색하지 않도록 하기 위한 HashSet visited와 words를 HashSet에 넣어 비교할 단어와 확인 할 수 있다.
  • HashSet의 contain은 시간 복잡도가 O(1)이기 때문에 반복해서 찾을 때의 O(n)보다 빠르게 찾을 수 있다.
• 이후, 선택된 단어를 Queue에 넣고 visited를 설정해 너비 우선 탐색 과정을 수행할 수 있다.

결론

이전까지 Array 형태로 반복해서 적절한 값을 찾는 방법으로 해왔는데, Set을 적절하게 사용하면 실행 시간을 많이 단축할 수 있을 것 같다.

프로그래머스에서 알고리즘 문제를 풀던 도중 이해하기 어려운 코드 한줄을 발견했다. Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));

다익스트라 알고리즘을 공부하면서 PriorityQueue를 사용할 때 compareTo를 Override해서 사용한 적이 있는데 명확하게 이해하지 못한 것 같아 짚고 넘어가려 한다.

Arrays.sort()란?

공식 문서를 보면 여러 타입의 배열이 모두 정렬될 수 있도록 정의된 것을 볼 수 있다.

동작과정을 살펴보면 다음과 같다.

// Arrays class
public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, 0, a.length);
}

...
// DualPivotQuicksort class

static void sort(int[] a, int parallelism, int low, int high) {
    int size = high - low;
    if (parallelism > 1 && size > 4096) {
       int depth = getDepth(parallelism, size >> 12);
       int[] b = depth == 0 ? null : new int[size];
       (new Sorter((CountedCompleter)null, a, b, low, size, low, depth)).invoke();
    } else {
        sort((Sorter)null, (int[])a, 0, low, high);
    }
}

static void sort(Sorter sorter, int[] a, int bits, int low, int high) {
        while(true) {
            int end = high - 1;
            int size = high - low;
            if (size < 65 + bits && (bits & 1) > 0) {
                mixedInsertionSort(a, low, high - 3 * (size >> 5 << 3), high);
                return;
            }

            if (size < 44) {
                insertionSort(a, low, high);
                return;
            }

...(생략)

내부적으로 두개의 pivot을 사용하는 Quicksort로 동작하며 시간 복잡도는 O(n log n)으로 좋은 성능을 가지기 때문에 알고리즘을 풀때 사용해도 큰 문제가 없을 것 같다.

매개 변수에는 3가지 정도가 있다.

• fromIndex(시작 인덱스)
• toIndex(마지막 인덱스)
• Comparator<? super T> c

Interface Comparator< T >

주목해야할 매개변수로 인터페이스인 Comparator은 람다 표현식 등을 사용한 비교기를 정렬 방법으로 전달할 수 있다고 명시되어있다.

Example

기본 형태(오름차순)

public static void main(String[] args) {
    String[] words = {"banana", "apple", "orange", "kiwi"};

    Arrays.sort(words);

    System.out.println("문자열 정렬: " + Arrays.toString(words));

    Integer[] numbers = {5, 1, 8, 3, 7};

    Arrays.sort(numbers);

    System.out.println("숫자 정렬: " + Arrays.toString(numbers));
}

// 실행 결과
문자열 정렬: [apple, banana, kiwi, orange]
숫자 정렬: [1, 3, 5, 7, 8]

기본적인 형태로 default는 오름차순으로 정렬한다. sort함수에 정렬할 배열만 넣어 사용할 수 있다. 문자열을 정렬할 때는 알파벳 순서(ASCII code 비교)로 정렬하게 되고 같은 알파벳일 경우 그 다음 문자열을 비교해서 정렬하게 된다.

String[] words = {"aanana", "apple", "orange", "kiwi"};

Arrays.sort(words);

System.out.println("문자열 정렬: " + Arrays.toString(words));

//실행 결과
문자열 정렬: [aanana, apple, kiwi, orange]

내림차순 정렬(Comparator)

public static void main(String[] args) {
    String[] words = {"banana", "apple", "orange", "kiwi"};

    Arrays.sort(words, Comparator.reverseOrder());

    System.out.println("문자열 정렬(내림차순): " + Arrays.toString(words));

    Integer[] numbers = {5, 1, 8, 3, 7};

    Arrays.sort(numbers, Comparator.reverseOrder());

    System.out.println("숫자 정렬(내림차순): " + Arrays.toString(numbers));
}

// 실행 결과
문자열 정렬(내림차순): [orange, kiwi, banana, apple]
숫자 정렬(내림차순): [8, 7, 5, 3, 1]

Comparator.reverseOrder()을 추가해서 내림차순으로 정렬할 수 있다.

public static void main(String[] args) {
    Integer[] numbers = {5, 1, 8, 3, 7};

    Arrays.sort(numbers, (a, b) -> b - a);

    System.out.println("내림차순 정렬: " + Arrays.toString(numbers));
}

람다 표현식으로 a,b를 비교하여 내림차순으로 정렬하는 방법이다.

• b - a가 양수면, b가 a보다 크기 때문에 b가 앞에 와야한다.
• b - a가 음수면, a가 b보다 크기 때문에 a가 그대로 유지된다.

Comparator 응용

이전 내림차순 정렬을 위해 사용한 람다식 표현으로 더 복잡한 정렬기준을 만들어서 정렬을 할 수 있다.

• 2차원 배열에서 첫번째 요소로만 정렬하고 싶을 때
• 이전 값과의 연산을 통해 정렬 기준을 정할 때

상황에 더 따라 다양하게 사용할 수 있는데 실제로 필요했던 예시만 언급했다.

1. 2차원 배열의 정렬 조건

public static void main(String[] args) {
    Integer[][] workers = {{1, 280}, {3, 120}, {2, 150}, {5, 400}, {4, 330}};

    Arrays.sort(workers, (a, b) -> b[1].compareTo(a[1]));

    System.out.println("급여(내림차순) 정렬: " + Arrays.deepToString(workers));

// 실행결과
급여(내림차순) 정렬: [[5, 400], [4, 330], [1, 280], [2, 150], [3, 120]]
}

ID, 급여 정보가 있는 2차원 배열이 있다고 생각해보자. 만약 급여가 높은 순서대로 정렬하고 싶다면 다음과 같이 코드를 작성할 수 있다.

(a, b) -> b[1].compareTo(a[1]) 는 람다 표현식으로, 정렬 기준이 된다.

• a, b배열의 두개의 요소

  • example
  • a는 {1 , 280} , b는 {3 , 120}

• b[1], a[1]로 배열의 두번째(급여)를 사용하여 비교

• 동작과정

  • b[1]가 a[1]보다 크면 양수가 반환되어 b가 a앞에 위치한다.
  • b[1]가 a[1]보다 작으면 음수가 반환되어 순서가 유지된다.
  • b[1]가 a[1]보다 같으면 순서를 바꾸지 않는다.

2. 이전 값과의 연산을 통한 정렬기준

프로그래머스 가장 큰 수 를 풀 때 필요한 솔루션으로 문제 상황은 다음과 같다.

public class Solution {
    public String solution(int[] numbers) {
        String[] arr = new String[numbers.length];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = String.valueOf(numbers[i]);
        }

        Arrays.sort(arr, (a, b) -> (b + a).compareTo(a + b));

          ...
    }
}

주어진 입력 값을 String 배열로 변환 후에 Arrays.sort(arr, (o1, o2) -> (o2 + o1).compareTo(o1 + o2)); 로 정렬을 수행했다.

동작 과정 a = 30 , b = 34 라고 할 때, "3430"이 "3034"보다 크기 때문에 양수가 반환되어 b가 a보다 앞에 위치하게 된다. 이런식으로 내림차순으로 정렬해서 가장 큰 수의 문자열을 만들 수 있다.

문제 설명

주어진 문자열에서 특정 문자가 최소 n개 이상 들어있는지 확인하는 문제로 처음에는 한칸씩 밀면서 문자열을 확인하는 방식으로 접근했다.

for(int i=0; i < S - P + 1; i++){
    String checkString = dna.subString(i, i + P);
     ...
}

이와 같이 문자열을 subString으로 추출하고 특정 로직을 수행하는 방식으로 해당 문자열이 비밀번호로 사용할 문자가 적합한지 판단했다. 반복문을 사용해서 확인하면 시간초과가 발생할 것을 우려해 checkString.length() - checkString.replace("A", " ").length()와 같이 추출한 전체 길이에서 확인하려는 문자를 공백으로 바꾼뒤 빼서 확인했지만 시간초과가 발생하는 것을 알 수 있었는데 이유는 다음과 같다.

public String replace(CharSequence target, CharSequence replacement) {  
    String trgtStr = target.toString();  
    String replStr = replacement.toString();  
    int thisLen = this.length();  
    int trgtLen = trgtStr.length();  
    int replLen = replStr.length();  
    if (trgtLen > 0) {  
        if (trgtLen == 1 && replLen == 1) {  
            return this.replace(trgtStr.charAt(0), replStr.charAt(0));  
        } else {  
            boolean thisIsLatin1 = this.isLatin1();  
            boolean trgtIsLatin1 = trgtStr.isLatin1();  
            boolean replIsLatin1 = replStr.isLatin1();  
            String ret = thisIsLatin1 && trgtIsLatin1 && replIsLatin1 ? StringLatin1.replace(this.value, thisLen, trgtStr.value, trgtLen, replStr.value, replLen) : StringUTF16.replace(this.value, thisLen, thisIsLatin1, trgtStr.value, trgtLen, trgtIsLatin1, replStr.value, replLen, replIsLatin1);  
            return ret != null ? ret : this;  
        }    } else {  
        int resultLen;  
        try {  
            resultLen = Math.addExact(thisLen, Math.multiplyExact(Math.addExact(thisLen, 1), replLen));  
        } catch (ArithmeticException var12) {  
            throw new OutOfMemoryError("Required length exceeds implementation limit");  
        }  
        StringBuilder sb = new StringBuilder(resultLen);  
        sb.append(replStr);  

        for(int i = 0; i < thisLen; ++i) {  
            sb.append(this.charAt(i)).append(replStr);  
        }  
        return sb.toString();  
    }}

해당 코드는 replace 내장 함수로 동작 과정을 보면 마지막에 반복문을 사용해 대체한 String을 다시 할당해서 반환하는 것을 볼 수 있다. 그렇기 때문에 코드상에서 반복문을 사용하는 것과 크게 다를 것이 없다.

for(int i = 0; i < thisLen; ++i) {  
            sb.append(this.charAt(i)).append(replStr);  
}  
return sb.toString(); 

정답 코드

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

public class Main {  


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

        String[] firstLine = br.readLine().split(" ");  
        int S = Integer.parseInt(firstLine[0]);  
        int P = Integer.parseInt(firstLine[1]);  

        String dna = br.readLine();  

        int result = 0;  
        String[] thirdLine = br.readLine().split(" ");  
        int[] minCount = new int[4];  
        for (int i = 0; i < 4; i++) {  
            minCount[i] = Integer.parseInt(thirdLine[i]);  
        }  

        result = answer(dna, minCount, S, P);  
        System.out.println(result);  

        br.close();  
    }  

    static int answer(String dna, int[] minCount, int S, int P) {  
        int result = 0;  
        int[] checkCount = new int[4];  
        boolean check;  
        char before = ' ';  
        for (int i = 0; i < S - P + 1; i++) {  
            if (i == 0) {  
                String checkString = dna.substring(i, i + P);  
                checkCount = initCheck(checkString);  
                before = checkString.charAt(i);  
            } else {  
                char after = dna.charAt(i + P - 1);  
                checkCount = updateCheck(before, after, checkCount);  
                before = dna.charAt(i);  
            }  
            check = checkString(minCount, checkCount);  
            if (check) {  
                result++;  
            }  
        }  
        return result;  
    }  

    static int[] initCheck(String checkString) {  
        int[] result = new int[4];  
        result[0] = checkString.length() - checkString.replace("A", "").length();  
        result[1] = checkString.length() - checkString.replace("C", "").length();  
        result[2] = checkString.length() - checkString.replace("G", "").length();  
        result[3] = checkString.length() - checkString.replace("T", "").length();  
        return result;  
    }  

    static int[] updateCheck(char before, char after, int[] checkCount) {  
        if (before == 'A') {  
            checkCount[0]--;  
        } else if (before == 'C') {  
            checkCount[1]--;  
        } else if (before == 'G') {  
            checkCount[2]--;  
        } else {  
            checkCount[3]--;  
        }  

        if (after == 'A') {  
            checkCount[0]++;  
        } else if (after == 'C') {  
            checkCount[1]++;  
        } else if (after == 'G') {  
            checkCount[2]++;  
        } else {  
            checkCount[3]++;  
        }  
        return checkCount;  
    }  

    static boolean checkString(int[] minCount, int[] checkCount) {  
        if (checkCount[0] < minCount[0]) {  
            return false;  
        }  
        if (checkCount[1] < minCount[1]) {  
            return false;  
        }  
        if (checkCount[2] < minCount[2]) {  
            return false;  
        }  
        if (checkCount[3] < minCount[3]) {  
            return false;  
        }  
        return true;  
    }  
}

메소드를 분리해서 코드가 길지만 동작 과정은 매우 단순하다.

1. 문자열 추출 및 checkCount

가장 처음에는 비밀번호로 사용할 만큼 길이의 문자열을 처음 인덱스부터 추출해서 checkCount를 만들어준다. 여기서 checkCount는 현재 문자열에 포함된 단어를 check하는 배열로 해당 배열로 최소 포함 개수 배열과 비교하며 비밀번호로 적절한지 판단한다.

2. 추가 , 삭제되는 문자를 checkCount에 반영

이후 새로 확인하는 문자가 "AT"라고 할 때 G를 before, T를 After로 설정해 before에 해당하는 count를 1 감소 , after 해당하는 count를 1 증가하여 checkCount를 업데이트 한다.

해당 과정을 반복하며 다음과 같은 checkString을 수행해주며 비밀번호로 적절한 문자열을 판단한다.

static boolean checkString(int[] minCount, int[] checkCount) {  
    if (checkCount[0] < minCount[0]) {  
        return false;  
    }  
    if (checkCount[1] < minCount[1]) {  
        return false;  
    }  
    if (checkCount[2] < minCount[2]) {  
        return false;  
    }  
    if (checkCount[3] < minCount[3]) {  
        return false;  
    }  
    return true;  
}

정리

일반적으로 1억번의 연산이 1초에 진행된다고 가정하고 시간초과가 발생하지 않게 코드를 구현하는 방법에 대해서 좀 더 고민해야겠다.🙃

문제 설명

누적합으로 푸는 아주 간단한 실버 문제이다. 하지만 '당연히 되겠지?' 라는 생각으로 반복문을 두번 돌려서 풀다가 시간초과가 발생하는 것을 발견하고 기억하고자 글을 작성했다.😭

정답 코드

풀이는 굉장히 간단하다. i ~ j 까지 합을 구하는 것이기 때문에 n번째까지 더한 값을 담아두는 sum을 선언하고 sum[j] - sum[i-1]을 해서 결과를 출력하면된다.

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

public class Main {  

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

        String[] firstLine = br.readLine().split(" ");  
        int N = Integer.parseInt(firstLine[0]);  
        int M = Integer.parseInt(firstLine[1]);  

        int[] numbers = new int[N + 1];  // 1-based index 사용  
        String[] secondLine = br.readLine().split(" ");  
        for (int i = 1; i <= N; i++) {  
            numbers[i] = Integer.parseInt(secondLine[i - 1]);  
        }  
        int[] sum = new int[N + 1];  
        for (int i = 1; i <= N; i++) {  
            sum[i] = numbers[i] + sum[i - 1];  
        }  
        for (int i = 0; i < M; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            int start = Integer.parseInt(st.nextToken());  
            int end = Integer.parseInt(st.nextToken());  
            System.out.println(sum[end] - sum[start - 1]);  
        }  
        br.close();  
    }  

}

문제 설명

위상 정렬 문제로 진입차수가 없는(선행 작업이 존재하지 않은) 노드들을 먼저 실행시키고 작업이 완료되면 하위 노드의 차수를 감소시켜 진입차수가 0이 되는 노드의 작업을 시작하는 방식으로 접근했다. 시간 제한이 2초로 나름? 여유가 있어 1시간 단위로 반복문을 실행해 작업중인 노드의 time 값을 감소시켜 0이 되면 위 작업을 실행하도록 코드를 작성했다.

정답 코드(라고 생각했던 것)

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

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

        int n = Integer.parseInt(br.readLine());  

        StringTokenizer st;  

        int[] degree = new int[n + 1];  
        int[] time = new int[n + 1];  

        List<List<Integer>> graph = new ArrayList<>();  
        for (int i = 0; i <= n; i++) {  
            graph.add(new ArrayList<>());  
        }  
        for (int i = 1; i <= n; i++) {  
            st = new StringTokenizer(br.readLine());  

            time[i] = Integer.parseInt(st.nextToken());  
            int cnt = Integer.parseInt(st.nextToken());  
            degree[i] = cnt;  
            for (int j = 0; j < cnt; j++) {  
                int parent = Integer.parseInt(st.nextToken());  
                graph.get(parent).add(i);  
            }  

        }  

        Queue<Integer> q = new LinkedList<>();  
        for (int i = 1; i <= n; i++) {  
            if (degree[i] == 0) {  
                q.add(i);  
            }  
        }  

        int cnt = 0;  
        while (!q.isEmpty()) {  
            for (int i = 0; i < q.size(); i++) {  
                int t = q.poll();  
                time[t]--;  
                if (time[t] == 0) {  
                    List<Integer> nodes = graph.get(t);  
                    for(Integer node: nodes){  
                        degree[node]--;  
                        if(degree[node] == 0){  
                            q.add(node);  
                        }  
                    }  
                } else {  
                    q.add(t);  
                }  
            }  
            cnt++;  
        }  
        System.out.println(cnt);  

    }  
}

주요 알고리즘

       int cnt = 0;  
        while (!q.isEmpty()) {  
            for (int i = 0; i < q.size(); i++) {  
                int t = q.poll();  
                time[t]--;  
                if (time[t] == 0) {  
                    List<Integer> nodes = graph.get(t);  
                    for(Integer node: nodes){  
                        degree[node]--;  
                        if(degree[node] == 0){  
                            q.add(node);  
                        }  
                    }  
                } else {  
                    q.add(t);  
                }  
            }  
            cnt++;  
        }  

queue에 담겨있는(진행중인 작업)을 가져와 time값을 감소시키고 time이 0이 아닐 때는 다시 queue에 넣어 작업을 계속 진행하도록 했다. 최저 시간을 출력하는 문제이지만 어짜피 하위 노드의 작업은 모든 상위 노드가 끝났을 때 진행되기 때문에 별다른 비교연산없이 이상적으로 동시에 작업이 진행된다고 생각했다...결과를 확인하기 전까지

정답 코드

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

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

        int n = Integer.parseInt(br.readLine());  

        StringTokenizer st;  

        int[] degree = new int[n + 1];  
        int[] time = new int[n + 1];  
        int[] cTime = new int[n + 1];  
        List<List<Integer>> graph = new ArrayList<>();  
        for (int i = 0; i <= n; i++) {  
            graph.add(new ArrayList<>());  
        }  
        for (int i = 1; i <= n; i++) {  
            st = new StringTokenizer(br.readLine());  
            time[i] = Integer.parseInt(st.nextToken());  
            int cnt = Integer.parseInt(st.nextToken());  
            degree[i] = cnt;  
            for (int j = 0; j < cnt; j++) {  
                int parent = Integer.parseInt(st.nextToken());  
                graph.get(parent).add(i);  
            }  

        }  

        Queue<Integer> q = new LinkedList<>();  
        for (int i = 1; i <= n; i++) {  
            if (degree[i] == 0) {  
                q.add(i);  
                cTime[i] = time[i];  
            }  
        }  

        while (!q.isEmpty()) {  
            int current = q.poll();  

            for (Integer next : graph.get(current)) {  
                degree[next]--;  
                cTime[next] = Math.max(cTime[next], cTime[current] + time[next]);  
                if(degree[next] == 0){  
                    q.add(next);  
                }  
            }  
        }  
        int result = 0;  
        for (int i = 1; i <= n; i++) {  
            result = Math.max(result, cTime[i]);  
        }  
        System.out.println(result);  
    }  
}

        for (int i = 1; i <= n; i++) {  
            if (degree[i] == 0) {  
                q.add(i);  
                cTime[i] = time[i];  
            }  
        }  

        while (!q.isEmpty()) {  
            int current = q.poll();  

            for (Integer next : graph.get(current)) {  
                degree[next]--;  
                cTime[next] = Math.max(cTime[next], cTime[current] + time[next]);  
                if(degree[next] == 0){  
                    q.add(next);  
                }  
            }  
        }  

cTime이라는 완료시간을 저장하는 배열을 선언하고 정점인 노드 즉, 가장 먼저 작업을 시작하는 노드의 값은 해당 작업이 걸리는 시간을 할당한다. 이후 다음과 같은 연산을 통해 해당 노드가 작업이 완료된 시간을 정한다.

다음과 같은 상황이 있다고 가정하자. (실제로 cTime[3]은 값이 없지만 편의상 해당 작업의 시간이라고 생각한다.)

1,2 작업이 동시에 시작되며 15시간이 걸리는 1작업이 먼저 끝나고 연산을 통해 cTime[3]은 20이 된다.

이후 2작업이 5시간 뒤에 끝나게 되고 이전의 값인 20과 새롭게 계산한 25중에서 큰 값인 25로 설정해서 상위 작업이 전부 끝나고 완료된 시간을 기록하게 된다.

정리

사실 아직 첫번째 만든 코드가 틀린 이유는 잘 모르겠다.(물론 깔끔한 코드라고 생각은 안함 ㅎ) 상위 작업이 끝난 후에 작업이 끝나도록 코드를 작성했기 때문에 예제와 질문 게시판에 있는 반례 몇개를 해봤지만 제대로 정답이 출력되었기 때문이다. 시간초과라고 뜨면 납득이 되겠지만 채점이 틀렸다고 한건 분명 반례가 있다는건데... (있으면 댓글 부탁드림다.) 어쨌든 위상정렬에 대해서 좀 더 확실한 이해가 되었던 문제였다고 생각한다. 🙃

문제 링크

문제 설명

일반적인 DP 문제로 합이 최대가 되는 경로의 수의 합을 출력하는 문제이다. 어떤 경로인지까지는 파악할 필요가 없고 마지막 줄에서 합이 가장 큰 값을 출력하면된다. 맨 윗줄부터 더한 값을 계속 누적해서 마지막 줄에서 가장 큰 값을 출력하는 방식으로 접근했고 가장자리가 아닌 경우는 가로 윗 줄의 두가지 값을 더한 것 중 최대값으로 해야하기 때문에 이에 대한 코드를 조건문으로 구현했다.

정답 코드

# 정수 삼각형  
n = int(input())  

# 정수 삼각형의 값을 2차원 배열로 형태로 입력받음
t = []  
for i in range(n):  
    t.append(list(map(int, input().split())))  

# 입력받은 n의 크키에 맞는 0의 값을 가지는 배열을 선언
dp = [[0] * i for i in range(1, n + 1)] 

for i in range(n):  
    # 가로 첫번째 줄은 값을 그대로 입력
    if i == 0:  
        dp[0][0] = t[0][0]  
        continue  
    # 가로 두번째 줄은 첫번째 줄의 값과의 합으로 입력
    if i == 1:  
        dp[1][0] = dp[0][0] + t[i][0]  
        dp[1][1] = dp[0][0] + t[i][1]  
        continue  

    for j in range(i + 1):  
        # 왼쪽 가장자리인 경우
        if j == 0:  
            dp[i][j] = dp[i - 1][j] + t[i][j]  
        # 오른쪽 가장자리인 경우
        elif j == i:  
            dp[i][j] = dp[i - 1][j - 1] + t[i][j]  
        # 가장자리가 아닌 경우
        # 두가지 값이 생기는데 그 중 최대값으로 설정
        else:  
            dp[i][j] = max(dp[i - 1][j - 1] + t[i][j], dp[i - 1][j] + t[i][j])  

# 마지막 줄에서 가장 큰 값을 출력
print(max(dp[n - 1]))

값 누적 연산

for j in range(i + 1):  
        # 왼쪽 가장자리인 경우
        if j == 0:  
            dp[i][j] = dp[i - 1][j] + t[i][j]  
        # 오른쪽 가장자리인 경우
        elif j == i:  
            dp[i][j] = dp[i - 1][j - 1] + t[i][j]  
        # 가장자리가 아닌 경우
        # 두가지 값이 생기는데 그 중 최대값으로 설정
        else:  
            dp[i][j] = max(dp[i - 1][j - 1] + t[i][j], dp[i - 1][j] + t[i][j])  

가장 자리가 아닌 경우 더한 값에서 최대 값으로 설정해야 하는데 그림에서 3개의 값이 있는 줄을 연산하고 있을 때 1은 10과 15중 더 큰 15와 더한 값인 16으로 값을 누적시켜야한다.

추가

정답은 맞췄지만 이 글을 작성하면서 코드를 다시 봤는데 수정하고 싶은 사항이 너무 많아서 코드를 다시 작성해서 제출해봤다. 수정사항은 다음과 같다.

dp 배열의 필요성

굳이 하나의 배열을 더 선언하지 않고 입력받은 t에 값을 수정하면서 누적하면 될 것 같다. 불필요한 배열때문에 다시 봤을 때 코드가 쓸데없이 복잡하다는 생각이 들었다. t를 그대로 사용하면 반복문의 횟수도 줄어들 것 같다.

누적 값 연산 코드

이전 코드에서는 가장자리가 아닐 경우 값을 더한 후에 max함수에서 최대 값을 추출했는데 굳이 그럴 필요 없이 두개 중 최대값을 뽑아서 더해서 저장하면 될 것 같다.

수정된 코드

n = int(input())  

t = []  
for i in range(n):  
    t.append(list(map(int, input().split())))  

for i in range(1, n):  
    if i == 1:  
        t[1][0] = t[0][0] + t[i][0]  
        t[1][1] = t[0][0] + t[i][1]  
        continue  
    for j in range(i + 1):  
        if j == 0:  
            t[i][j] = t[i - 1][j] + t[i][j]  
        elif j == i:  
            t[i][j] = t[i - 1][j - 1] + t[i][j]  
        else:  
            t[i][j] = max(t[i - 1][j - 1], t[i - 1][j]) + t[i][j]  

print(max(t[n - 1]))

크게 개선된 느낌은 아니지만 코드 상에서 반복되는 부분을 줄이고 굳이 필요하지 않은 배열 선언을 없앤걸로 만족!🙃

해당 글은 '이것이 코딩테스트다 with 파이썬' (나동빈 지음) 책 내용을 정리한 것입니다.

다이나믹 프로그래밍이란?

DP, 동적 계획법이라고도 불리는 이것은 메모리 공간을 더 사용하여 연산 속도를 비약적으로 증가시킬 수 있는 방법이다.

다이나믹 프로그래밍의 조건

다이나믹 프로그래밍을 사용하기위해 다음과 같은 조건이 필요하다.

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

피보나치 수열을 예시로 비교를 해보면 다음과 같다.

예시 : 피보나치 수열

DP를 사용하지 않은 구현 예시

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

print(fibo(4))

일반적인 재귀호출 방법으로 피보나치 수열을 구현한 것이다. 하지만 이와 같이 구현할 경우 몇가지 문제가 발생한다.

시간 복잡도

• f(n) 함수에서 n이 커질 수록 수행 시간이 기하급수적으로 늘어난다.
  • O(2^n)
  • N = 30이면, 약 10억 가량의 연산을 수행한다.

• f(6)을 예시로 그림으로 표현하면 f(3)이 3번 호출되는 것을 볼 수 있다.
• f(n)에서 n이 커질수록 중복 호출되는 경우가 증가하고 f(100)일 경우에는 답을 도출하기 힘들 정도로 많은 시간이 소요된다.

DP 사용한 구현 예시

[Top-Down VS Bottom-UP]

• Top-Down : 재귀 함수를 이용해 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
• Bottom-UP : 반복문을 이용해 작은 문제부터 차근차근 답을 도출하는 방법

1. Top-Down

d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0
        return d[x]
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

한번 푼 문제는 저장해 놨다가 나중에 동일한 문제를 풀어야 할때(여기서 문제는 호출을 의미)이미 저장한 값을 반환하여 반복적으로 호출되는 상황을 막을 수 있다.

• 점선으로 표시한 부분은 호출이 되지 않은 경우로 메모이제이션을 통해 시간복잡도를 줄일 수 있다.
  • O(N)의 시간복잡도를 가진다. 왜냐하면 한번 구한 결과는 다시 구해지지 않기 때문이다.

2. Bottom-UP

d = [0] * 100

d[1] = 1
d[2] = 2
n = 99

for i in range(3, n+1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

[추가]

• 때에 따라 dict 자료형을 이용하여 메모이제이션을 할 수 있다.
• sys.setrecursionlimit()을 사용해 재귀함수 호출 제한을 완화할 수 있다.

이 글은 'HTTP 완벽 가이드' 책을 읽고 정리한 내용입니다.

[이번 장에서]

• 여러 종류의 소프트웨어 및 하드웨어 웹 서버에 대해 조사한다.
• 어떻게 웹 서버가 HTTP 트랜잭션을 처리하는지 단계별로 설명한다.

다채로운 웹 서버

[웹 서버의 역할]

• 웹 서버는 HTTP 요청을 처리하고 응답을 제공한다.
• 웹 서버는 자신이 제공하는 리소스를 관리하고 웹 서버를 설정, 통제, 확장하기 위한 관리 기능을 제공한다.

아파치 톰캣?

• 아파치(Apache)
  • 웹 서버 프로그램 - 오픈 소스 소프트웨어
• 톰캣 WAS(web application server)
  • JSP와 Servlet을 구동하기 위한 서블릿 컨테이너 역할 수행
  • 아파치 서버와는 다르게 DB연결, 다른 응용프로그램과 상호 작용 등 동적인 기능들을 사용할 수 있다.
• 아파치 톰캣이라고 불리는 이유가 뭐지?

• 기본적으로 위처럼 아파치와 톰캣의 기능은 나뉘어져 있지만, 톰캣 안에 있는 컨테이너를 통해 일부 아파치의 기능을 발휘하기 때문에 보통 아파치 톰캣으로 합쳐서 부르곤 한다.
• 참고 블로그

임베디드 웹 서버

• 일반 소비자용 제품에 내장될 목적으로 만들어진 작은 웹 서버(프린터, 가전제품)
• 일반 소바자용 기기를 웹 브라우저 인터페이스로 관리할 수 있게 해준다.

웹 서버가 하는 일

1. 커넥션을 맺는다 : 클라이언트의 접속 허용 및 차단
2. 요청을 받는다 : HTTP 요청 메세지를 읽기
3. 요청을 처리한다 : 요청 메세지 해석 및 처리
4. 리소스에 접근한다 : 메세지에서 지정한 리소스에 접근
5. 응답을 만든다 : HTTP 응답 메세지 생성
6. 응답을 보낸다 : 클라이언트에게 응답 반환
7. 트랜잭션을 로그로 남긴다 : 로그파일에 트랜잭션 완료에 대한 기록

1. 클라이언트 커넥션 수락

웹 서버가 클라이언트의 커넥션을 수락하는 단계

지속적 커넥션이 있다면 해당 커넥션으로 요청이 가능하고 없다면 새로운 커넥션을 열어야 한다.

새 커넥션 다루기

1. 클라이언트의 TCP 커넥션 요청
2. 웹 서버의 TCP 커넥션 수락 및 클라이언트 IP 확인
3. 웹 서버의 데이터 수신 대기

• 웹 서버는 어떤 커넥션이든 마음대로 거절하거나 즉시 닫을 수 있다.
  • 클라이언트 IP 주소 혹은 호스트 명이 인가되지 않은 경우

웹 서버의 클라이언트 식별

역방향 DNS

• 클라이언트의 IP에 해당하는 도메인이 있는지 검사하는 과정으로 호스트 명을 반환하여 확인한다.
• IP -> 도메인 (정방향으로는 도메인 -> IP 이다.)

• 웹 서버는 클라이언트 호스트 명을 구체적인 접근 제어, 로깅을 위해 사용할 수 있다.
• 호스트 명 룩업은 시간이 많이 걸려 트랜잭션을 느력지게 할 수 있다.

IETF ident 프로토콜

• 서버에게 어떤 사용자 이름이 HTTP 커넥션을 초기화 했는지 찾아낼 수 있게 해준다.

한마디로, TCP 커넥션 이후 ident 커넥션을 열어 웹서버가 클라이언트의 정보를 요청하는 과정을 통해 클라이언트 정보를 얻는다.

ident는 조직 내부에서는 잘 사용 가능하지만, 공용 네트워크에서는 여러가지 이유로 잘 동작하지 않는다.

• ident는 HTTP 트랜잭션을 유의미하게 지연시킨다.
• 방화벽이 ident 트래픽이 들어오는 것을 막는 경우가 많다.

2. 요청 메세지 수신

커넥션 데이터를 읽고 파싱하여 요청 메세지를 구성하는 단계

웹 서버의 요청 메세지 파싱

• 요청줄을 파싱하여 요청 메서드, URL, 버전 번호(프로토콜) 정보를 읽는다.
• CRLF를 기준으로 각 헤더와 본문의 내용을 읽는다.

요청 메세지 파싱 과정에서 입력 데이터를 불규칙적으로 받기 때문에 커넥션이 무효화 될 수 있다.

• 웹 서버는 파싱해서 이해 가능한 수준을 확보할때까지 메세지 일부를 메모리에 저장해둘 필요가 있다.

위 사진과 같이 요청 메세지에서 정보를 내부 자료 구조에 따라 저장한다.

• 이는 요청 메세지를 쉽게 다루기 위한 웹 서버의 기능이다.

커넥션 I/O 처리 아키텍처

클라이언트로부터 동시에 들어오는 수많은 커넥션 요청을 처리하기 위해 4가지 아키텍처가 있다.

1. 단일 스레드 웹서버

• 한번에 하나의 요청을 처리하며 트랜잭션 완료후, 다음 커넥션을 처리한다.
• 처리 과정 중 다른 커넥션은 무시된다.

2.멀티 프로세스와 멀티 스레드 웹 서버

• 여러개의 프로세스 혹은 스레드가 여러 요청을 동시에 처리한다.
• 프로세스/스레드는 미리 만들어 질 수 있고 매 커넥션마다 한개를 할당한다.
  • 너무 많이 생성될 경우 리소스를 많이 소비하기 때문에 최대 개수 제한을 건다.
• 3. 다중 I/O 서버*
• 많은 커넥션을 처리하기 위해 대부분의 웹 서버가 해당 아키텍처를 채택
• 모든 커넥션의 활동을 감시해 상태가 바뀔때(데이터 사용가능 및 에러 발생) 작은 양의 처리를 수행한다.
• 처리 완료 후, 상태 변경을 위해 '열린 커넥션 목록'으로 돌아가 다시 차례를 기다린다.

4. 다중 멀티스레드 웹 서버

• 멀티 스레딩과 다중화를 결합한 경우로 여러 개의 CPU의 이점을 살릴 수 있다.

• 여러 개의 스레드가 각 열려있는 커넥션을 감시하고 조금씩 작업을 수행한다.

  3. 요청 처리

  웹 서버가 받은 요청을 메서드, 리소스, 헤더, 본문을 얻어 처리하는 단계

• 요청 메서드에 따라 엔터티 본문이 있을 것을 요구한다.(POST, OPTIONS 등은 허용하되 요구하진 않음)

  4. 리소스의 매핑과 접근

  HTML 페이지, JPEG 와 같은 정적 콘텐츠 및 서버 위에서 동작하는 생성 애플리케이션을 통해 만들어진 동적 콘텐츠를 제공

Docroot

요청 URL을 웹 서버의 파일 시스템 안에 있는 파일 이름으로 사용하는 것으로 웹 콘텐츠를 위해 예약해둔 특별한 폴더를 문서 루트 혹은 docroot라고 한다.

요청 URL : /specials/saw-blade.gif docroot : /usr/local/httpd/files

웹 서버의 반환 : /usr/local/httpd/files/specials/saw-blade.gif

• 서버는 상대적인 url이 docroot를 벗어나 docroot 이외 부분이 노출되는 일이 생기지 않도록 주의해야한다.

가상 호스팅된 docroot

분리된 docroot를 주는 방법으로 하나의 웹 서버 위에 두 개의 사이트가 완전히 분리된 콘텐츠를 갖고 호스팅 되도록 할 수 있다.

요청에 따라 다른 docroot를 통해 다른 파일을 반환할 수 있다. 요청 A : /docs/joe/index.html 요청 B : /docs/marry/index.html

사용자 홈 디렉터리 docroot

사용자들이 하나의 웹 서버에서 개인 웹 사이트를 만들 수 있도록 해주는 것

• **/~(사용자 이름)/index.html"
• 개인 docroot는 주로 사용자의 홈 디렉터리 안에 있는 public_html로 불리는 디렉터리이다.(설정에 따라 다를 수 있다.)

[파일이 아닌 디렉터리를 가리키는 경로에 대한 요청] 일반적으로 서버는 다음과 같은 행동을 취한다.

1. 에러 반환
2. 디렉터리 대신 특별한 '색인 파일' 반환
3. 디텍터리 탐색 후 그 내용을 담은 HTML 페이지 반환

• 아파치에선 DirectoryIndex 설정을 통해 기본 디렉터리 파일로 사용될 파일 이름 집합을 설정할 수 있다.
  • 이에 따라 나열된 파일 중 하나를 반환하게 되는 것
• 하지만, 2,3번과 같이 할 경우, 일반적으로 발견할 수 없는 파일이 드러날 수 있기 때문에 해당 기능을 끌 수 있다.

[동적 콘텐츠 리소스 매핑] 웹 서버는 URL을 요청에 맞게 콘텐츠를 생성하는 프로그램에 매핑할 수 있다.

• 아파치는 서버가 실행 가능한 경로명을 포함한 URL로 요청을 받으면, 그 경로에 대응하는 디렉터리에서 프로그램을 찾아 실행하려 시도한다.
• 특정 확장자의 파일만 실행하도록 설정이 가능하다.

많은 웹 서버가 서버사이드 인클루드도 지원하고 이는 '#include' 지시문을 사용하여 하나 이상의 파일 내용을 웹 서버의 웹 페이지에 포함 시키는데 유용하다. (참고) 서버는 콘텐츠에 변수 이름, 내장된 스크립트가 될 수 있는 특별한 패턴이 있는지 검사 받고 이는 변수 값, 실행 가능한 스크립트의 출력 값으로 치환된다. 이는 동적 콘텐츠를 만드는 쉬운 방법이다. (코드 상에서 변수 이름과 같이 선언된 것을 값으로 치환하여 클라이언트에게 제공한다는 의미인 것 같다.) (동적 콘텐츠란 DB 상태에 따라 다르게 출력이 되는 콘텐츠 같은 것을 의미)

5. 응답 만들기

서버가 리소스 식별 후, 요청 메서드로 서술되는 동작을 수행한 뒤 응답 메세지를 반환하는 단계

• 응답 메세지의 구성요소

1. 응답 상태 코드
2. 응답 헤더
3. 응답 본문(있다면)

응답 본문이 있다면 다음과 같은 내용을 포함한다.

• 응답 본문의 MIME 타입을 서술하는 Content-Type 헤더
• 응답 본문의 길이를 서술하는 Content-Length 헤더
• 실제 응답 본문의 내용

  MIME 타입 결정

  MIME 타입과 리소스를 연결하는 여러 가지 방법은 다음과 같다. (MIME는 미디어 타입으로 문서, 파일, 바이트 집합의 특징을 나타내는 것이다.)

mime.types

• 확장자별 MIME 타입이 담겨 있는 파일을 탐색하여 리소스의 타입을 계산

매직 타이핑(Magic typing)

• 아파치 웹 서버는 파일의 내용을 검사해 알려진 패턴에 대한 테이블에 해당하는 패턴이 있는지 찾아 결정할 수 있다.
• 느리지만 파일이 표준 확장자 없이 이름이 지어진 경우에는 특히 편리하다.

유형 명시(Explicit typing)

• 특정 파일, 디렉터리 안의 파일들이 확장자나 내용에 상관없이 어떤 MIME 타입을 갖도록 웹 서버를 설정할 수 있다.

유형 협상(Type negotiation)

• 한 리소스가 여러 종류의 문서 형식에 속하도록 설정하는 것으로 서버가 사용자와 협상 과정을 통해 사용하기 가장 좋은 형식을 판별한 것인지 여부도 설정이 가능하다.
• 웹 서버는 특정 파일이 특정 MIME 타입을 갖게끔 설정할 수도 있다.

리다이렉션

요청을 수행하기 위해 종종 다른 브라우저로 가도록 리다이렉트 할 수 있다.

• 응답 코드 : 3XX

다음과 같은 상황에서 유용하다.

• 영구적으로 리소스가 옮겨진 경우
• 임시로 리소스가 옮겨진 경우
• URL 증강 - 문맥 종보를 포함시키기 위해 재 작성된 URL로 리다이렉트
• 부하 균형 - 과부화된 서버에 대한 요청을 다른 서버로 리다이렉트(좀 더 자세히 공부해야 할 부분인 것 같다.)
• 디렉터리 이름 정규화
  • 클라이언트가 URL 요청 시 빗금('/')을 빠뜨렸다면, 대부분의 웹 서버는 상대경로가 정상적으로 동작할 수 있도록 빗금('/')을 추가한 URL로 리다이렉트한다.

    6. 응답 보내기

    서버가 생성한 응답을 클라이언트로 보내는 단계

    • 서버는 여러 커넥션을 맺고 있기 때문에 커넥션 상태를 추적해야한다.
      • 지속 커넥션이라면 특별히 주의해서 다뤄야한다.(Content-Length 헤더를 바르게 계산해야한다.)
      • 비지속 커넥션이라면 모든 메세지 전송 후 커넥션을 닫아야한다.

7. 로깅

트랜잭션이 완료되었을 때 트랜잭션이 어떻게 수행되었는지에 대한 로그를 로그파일에 기록하는 단계 (자세한 내용은 21장에서 다룬다.)

해당 글은 '이것이 코딩테스트다 with 파이썬' (나동빈 지음) 책 내용을 정리한 것입니다.

정렬 알고리즘 개요

정렬(Sorting)이란 테이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

1. 선택 정렬

가장 작은 데이터를 선택해서 스왑(swap)을 통해 맨 앞부터 정렬하는 방법

1. 다음과 같은 배열이 있다고 가정하자

*2. 초기 단계에서는 전체 데이터 중 가장 작은 걸 선택에서 맨 앞에 '7'과 바꾼다. *

3. 가장 작은 '0'은 올바른 위치에 정렬되었기 때문에 이를 제외한 숫자 중 가장 작은 것을 선택해 5와 바꾼다.

4. 위 과정을 반복하면 최종적으로 배열이 정렬된다.

코드

def selection_sort():
    for i in range(len(array)):
        min_index = i
        for j in range(i + 1, len(array)):
            if array[min_index] > array[j]:
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]

    return array

시간 복잡도

선택 정렬의 시간 복잡도를 구해보면 다음과 같다.

• 기본적으로 N-1 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다.
• 위 코드로 구현했을 때 연산 횟수
  • N + (N - 1) + (N - 2) + ••• + 2 ≈ N(N+1)/2
• 빅오 표기법으로 간단히 O(N²) 로 표기할 수 있다.

2. 삽입 정렬

데이터를 하나씩 확인하여 적절한 위치에 삽입하는 방법

• 직관적으로 이해하기 쉽고 선택 정렬에 비해 구현은 어렵지만 실행 시간 측면에서 효율적이다.
• 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.

⬆️는 들어갈 수 있는 위치를 의미한다.

1. 다음과 같은 배열이 있다고 가정하자

2. 두번째부터 시작해서 '5'는 '7'보다 작기 때문에 '7' 앞인 첫번째 위치에 삽입한다.

3. '7'은 올바른 위치에 있기 때문에 그대로 둔다. (다음 과정인 '9' 또한 변화가 없다.)

4. '0'은 '5', '7', '9' 중에 가장 작기 때문에 '5'앞인 첫번째 위치에 삽입된다.

5. '3'은 '0', '5', '7', '9' 중에 '0'보다 크고 '5'보다 작기 때문에 두번째 위치에 삽입된다.

6. 위 과정을 반복하면 최종적으로 배열이 정렬된다.

코드

def insertion_sort():
    for i in range(1, len(array)):
        for j in range(i, 0, -1):
            if array[j] < array[j - 1]:
                array[j], array[j - 1] = array[j - 1], array[j]
            else:
                break

    return array

시간 복잡도

삽입 정렬의 시간복잡도는 O(N²)이다.(선택 정렬과 마찬가지로 반복문이 두번 수행된다.) 하지만 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하고 최선의 경우 O(N)의 시간 복잡도를 가진다.

3. 퀵 정렬

퀵 정렬은 가장 많이 사용되는 알고리즘 중 하나이다.

• 기분 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.

동작과정을 통해 설명하면 다음과 같다.

1. 다음과 같은 배열이 있다고 가정하자

2. '5'을 p(pivot)로 설정하고 왼쪽에서부터 p보다 큰 데이터를 선택하고 오른쪽에서부터 p보다 작은 데이터를 선택한다. 이후 선택된 '7', '4'의 위치를 바꾼다.

• 위치 변환

3. 다시 왼쪽(이때 바뀐 위치가 시작 기준이 된다.)에서부터 p보다 큰 데이터를 선택하고 오른쪽에서부터 p보다 작은 데이터를 선택한다. 이후 선택된 '9', '2'의 위치를 바꾼다.

• 위치 변환

4. 다시 과정을 반복하면 다음과 같이 r과 l의 위치가 엇갈린 상황이 발생한다. 그럼 p와 r의 위치를 바꿔준다. 이는 p가 전체 배열에서 있어야 할 위치가 되며 더 이상 위치의 변화를 주지 않는다.

• 위치 변환

*5. 과정 4에서 '5'를 기준으로 왼쪽과 오른쪽 부분으로 나누어 위와 같은 과정을 반복해서 수행한다. *

코드

version 1

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end

    while left <= right:
        while left <= end and array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right:
            array[right], array[pivot] = array[pivot], array[right]
        else:
            array[left], array[right] = array[right], array[left]

    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

위 코드는 퀵 정렬을 직관적으로 이해하기 쉽게 작성한 코드이다.

version 2

def quick_sort(array):
    if len(array) <= 1:
        return array

    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

위 코드는 파이썬의 장점을 살려 리스트 컴프리헨션을 사용해 코드를 짧게 작성한 코드이다.

리스트 컴프리헨션이란?

직관적으로 리스트를 생성하는 방법으로 조건문을 사용하여 조건에 만족하는 값으로만 리스트를 생성할 수 있다.

코드에서 사용한 것을 보면 다음과 같다. 1. 배열을 pivot과 나머지를 나눠서 선언한다.

    pivot = array[0]
    tail = array[1:]

2. tail(나머지)에서 리스트 컴프리헨션을 사용해 left와 right을 나눈다.

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

디버그로 실행하여 결과를 확인하면 다음과 같다.

pivot '7'를 기준으로 작은 배열의 값을 left, 큰 배열의 값은 right로 리스트가 생성된 것을 볼 수 있다.

3. 이후 나눈 부분 가운데 pivot을 넣고 나머지 정렬과정을 수행한다.

    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

시간 복잡도

• 퀵 정렬의 평균적인 시간복잡도는 O(NlogN)이다.
• 이전 정렬에 비해 매우 빠른 편인데 이와 같은 시간복잡도를 가지는 이유는 다음과 같다.
  • N이 8이라면 분할은 총 3번 이루어진다.
  1. 8 -> 4, 4
  2. 4 -> 2, 2
  3. 2 -> 1, 1
  • 여기서 log의 밑은 2이며 8은 2의 3제곱이기 때문에 최종적으로 O(NlogN)의 시간 복잡도를 가지게 된다.
• 추가적으로 N이 1000일 때 logN은 약 10 정도되기 때문에 N에 비해서 logN은 매우 작은 수임을 알 수 있다.

4. 계수 정렬

계수 정렬은 특정 조건이 부합할때만 사용할 수 있는 방법이다.

• 데이터의 크기 범위가 제한더되어 정수 형태로 표현할 수 있을 때만 사용가능
• 일반적으로 데이터의 크기차이가 1,000,000을 넘지 않을 때 효과적

동작과정을 통해 설명하면 다음과 같다.

1. 다음과 같은 배열이 있다고 가정하자

2. 데이터의 범주 크기에 맞는 배열을 선언한다.

3. 데이터를 하나씩 확인해 몇번 등장하는지 카운트한다.

** 7 ** 5 9 0 3 1 6 2 9 1 4 8 0 5 2

.. (과정 반복) ..

4. 횟수를 카운트한 배열의 출력을 반복한다.

0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

코드

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]

count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end = ' ')

시간 복잡도

모든 데이터가 양의 정수인 상황에서 데이터 개수 N, 최대값의 크기를 K라 할 때, 계수 정렬의 시간 복잡도는 O(N+K)로 매우 빠른편이다. 하지만, 공간 복잡도 또한 O(N+K)이기 때문에 만약, 데이터가 '0', '999,999' 두개만 존재할 때도 1,000,000개의 리스트를 선언해야하는 비효율적인 상황이 발생할 수 있다.

[파이썬의 정렬 라이브러리] sort(), sorted()등의 함수는 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.

문제 설명

일반적인 dfs문제로 1인 노드를 탐색해서 연결된 영역의 개수를 카운트하는 문제이다. 일반적으로 이와 같은 문제는 예제로 전체 맵에 대한 입력으로 하는 반면 해당 문제는 1인 노드의 좌표 값을 입력으로 받는다. 그래서 입력받은 맵의 크기만큼 모든 값이 0인 2차원 배열을 선언한 후 해당 입력 받은 좌표 값을 1로 바꿔준 후에 로직을 수행하도록 접근했다.

문제 상황

다음과 같이 코드를 작성했는데 예제 입력에 대한 출력이 제대로 되지 않는 것을 확인했다. 디버그 모드로 실행해서 코드에서 문제가 되는 부분을 찾았는데 다음 부분에서 문제가 발생했다.

2차원 배열 선언

코드에서 모든 값인 0인 2차원 배열 선언을 한 후에 배열에서 입력받은 좌표 값을 1로 바꿔주었다.

graph = [[0] * M] * N  

for j in range(K):  
    x, y = map(int, input().split())  
    graph[y][x] = 1  

해당 로직을 수행 후에 graph를 출력해봤는데,, 다음과 같이 출력이 되는 것을 확인했다.

[
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], 
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], 
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], 
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], 
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], 
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], 
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1], 
    [1, 1, 1, 1, 1, 0, 0, 1, 1, 1]
]

graph[0][0] = 1 로 바꿔서 확인해보니 문제를 파악할 수 있었다. 나는 첫번째 배열의 첫번째 요소의 값만 바꿧지만 모든 배열의 첫번째 요소가 1로 바뀐 것을 볼 수 있다.

[
    [1, 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, 0, 0], 
    [1, 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, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
]

얕은 복사

결론은 위와 같이 2차원 배열을 선언할 경우 list의 얕은 복사가 발생한다. 즉 [0] * M] 길이의 list가 얕은 복사로 단순히 N개 생기는 것. 얕은 복사는 객체를 참조하기 때문에 하나의 값만 바뀌어도 나머지가 전부 바뀌게 된다.(for문 쓰는 것을 피하려다 아주 기본적인 부분에서 놓쳤다.. )

코드

# 유기농 배추  
T = int(input())  

dx = [-1, 1, 0, 0]  
dy = [0, 0, -1, 1]  

for i in range(T):  
    M, N, K = map(int, input().split())  

    graph = [[0] * M] * N  

    for j in range(K):  
        x, y = map(int, input().split())  
        graph[y][x] = 1  


    def dfs(x, y):  
        graph[x][y] = 0  

        for k in range(4):  
            nx = dx[k] + x  
            ny = dy[k] + y  

            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:  
                dfs(nx, ny)  


    result = 0  
    for y in range(N):  
        for m in range(M):  
            if graph[y][m] == 1:  
                dfs(y, m)  
                result += 1  

    print(result)

해결 방법

2차원 배열을 다음과 같이 선언해서 얕은 복사가 일어나지 않게 했고 추가적으로 [런타임 에러 (RecursionError)]가 발생하는 것을 확인해서 코드를 추가해줬다.

import sys  
sys.setrecursionlimit(10**6)

...

# graph = [[0] * M] * N  
graph = [[0 for col in range(M)] for row in range(N)]  

for j in range(K):  
    x, y = map(int, input().split())  
    graph[y][x] = 1  

코드

# 유기농 배추
import sys
sys.setrecursionlimit(10**6)
T = int(input())

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(T):
    M, N, K = map(int, input().split())

    graph = [[0 for col in range(M)] for row in range(N)]

    for j in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1


    def dfs(x, y):
        graph[x][y] = 0

        for k in range(4):
            nx = dx[k] + x
            ny = dy[k] + y

            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
                dfs(nx, ny)


    result = 0
    for y in range(N):
        for m in range(M):
            if graph[y][m] == 1:
                dfs(y, m)
                result += 1

    print(result)

문제 설명

전체 맵에서 연결된 섬의 개수를 카운트하는 문제로 그래프 탐색으로 문제를 해결할 수 있다. 전체 노드를 탐색하면서 연결된 노드를 재귀방식으로 계속 탐색하고 최종적으로 더 이상 연결된 섬이 없을 때 True 값을 반환하여 개수를 카운트하는 dfs방식으로 접근해봤다.

문제 상황

다음과 같이 코드를 작성했는데 [런타임 에러 (RecursionError)] 발생했다. 8방향으로 섬(1인 값)인지 확인하기 때문에 재귀 호출이 너무 많은 것 같다고 판단.

인터넷에서 찾아본 결과 파이썬 자체에서 재귀호출할 수 있는 max값이 정해져있어 sys.setrecursionlimit(10 ** 6) 코드를 추가해 해당 값을 임의로 설정했다.

하지만, 이번에는 틀렸다고 결과가 나왔다.

코드

# 섬의 개수  
import sys  

read = sys.stdin.readline  
sys.setrecursionlimit(10 ** 6)  


def dfs(x, y):  
    if x < 0 or x >= h or y < 0 or y >= w:  
        return False   
    if graph[x][y] == 1:  
        graph[x][y] = 0  
        dfs(x - 1, y - 1)  
        dfs(x, y - 1)  
        dfs(x + 1, y - 1)  
        dfs(x - 1, y)  
        dfs(x + 1, y)  
        dfs(x - 1, y + 1)  
        dfs(x, y + 1)  
        dfs(x + 1, y + 1)  
        return True  
    return False  

while True:  
    w, h = map(int, read().split())  

    if w == 0 and h == 0:  
        break  
    graph = []  
    for i in range(h):  
        graph.append(list(map(int, read().split())))  

    result = 0  

    for i in range(w):  
        for j in range(h):  
            if dfs(i, j):  
                result += 1  

    print(result)

해결 방법

결론은,,, 재귀 호출 자체를 하지 않도록 코드를 짜야한다는 것이였다. 위에서 정의한 dfs 메서드를 보면 일단 dfs함수를 호출하고 해당 위치의 값이 전체 범위를 벗어났는지 혹은 섬(1)이 아닌지를 판단하여 False를 반환하는데 이 과정 자체를 조건문으로 필터링하여 호출되는 경우 자체를 줄여야한다.

def dfs(x, y):  
    if x < 0 or x >= h or y < 0 or y >= w:  
        return False   
    if graph[x][y] == 1:  
        graph[x][y] = 0  
        dfs(x - 1, y - 1)  
        dfs(x, y - 1)  
        dfs(x + 1, y - 1)  
        dfs(x - 1, y)  
        dfs(x + 1, y)  
        dfs(x - 1, y + 1)  
        dfs(x, y + 1)  
        dfs(x + 1, y + 1)  
        return True  
    return False  

코드

# 섬의 개수  
import sys  

read = sys.stdin.readline  
sys.setrecursionlimit(10 ** 6)  

dx = [-1, 0, 1, -1, 1, -1, 0, 1]  
dy = [-1, -1, -1, 0, 0, 1, 1, 1]  

def dfs(x, y):  
    graph[x][y] = 0  
    for i in range(8):  
        nx = x + dx[i]  
        ny = y + dy[i]  
        if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:  
            dfs(nx, ny)  


while True:  
    w, h = map(int, read().split())  

    if w == 0 and h == 0:  
        break  
    graph = []  
    for i in range(h):  
        graph.append(list(map(int, read().split())))  

    result = 0  

    for i in range(h):  
        for j in range(w):  
            if graph[i][j] == 1:  
                dfs(i, j)  
                result += 1  

    print(result)

dfs

이와 같이 외부에서 조건문으로 필터링하여 재귀호출 자체가 수행되지 않게 하도록함

if graph[i][j] == 1:  
        dfs(i, j)  
        result += 1 

...

def dfs(x, y):  
    graph[x][y] = 0  
    for i in range(8):  
        nx = x + dx[i]  
        ny = y + dy[i]  
        if 0 <= nx < h and 0 <= ny < w and graph[nx][ny] == 1:  
            dfs(nx, ny)  

결론 및 피드백

• 일반적으로 재귀호출을 통해 구현하는 dfs보다 queue를 사용하여 구현하는 bfs를 먼저 생각해보자
  • 왜냐하면, 상대적으로 더 빠르게 코드가 동작한다.
• 문제와 별개로 x, y 값이 2차우너 배열에서 문제에서 w,h 값 중 어떤 것인지 종종 헷갈리는 상황을 발견했다. 로직이 맞더라도 반복문을 잘못 작성하면 문제가 생길 수 있기 때문에 유의해야 할 것 같다.

문제 설명

그래프에 대한 노드, 간선 정보가 주어지고 DFS, BFS로 그래프 탐색 결과를 출력하는 문제이다. 일반적으로 DFS는 재귀, BFS는 큐 방식으로 구현한다. 이전에 책으로 공부하면서 간단한 구현을 하는 방법에 대해서 알고 있어서 크게 어렵지 않을거라고 생각했는데 푸는데 생각보다 어려움이 있었다.(정답율이 생각보다 낮은 이유가 있었다..)

답을 도출하기 전에 이전에 책으로 공부하면서 구현했는 DFS, BFS 코드를 먼저 보자 DFS, BFS 구현 예제

# dfs  
def dfs(graph, v, visited):  
    visited[v] = True  
    print(v, end=' ')  

    for i in graph[v]:  
        if not visited[i]:  
            dfs(graph, i, visited)  


graph = [  
    [],    
    [2, 3, 8],  
    [1, 7],  
    [1, 4, 5],  
    [3, 5],  
    [3, 4],  
    [7],  
    [2, 6, 8],  
    [1, 7]  
]  

visited = [False] * 9  

dfs(graph, 1, visited)  

# bfs  
from collections import deque  
def bfs(graph, start, visited):  
    queue = deque([start])  

    visited[start] = True  

    while queue:  
        v = queue.popleft()  

        print(v, end=' ')  

        for i in graph[v]:  
            if not visited[i]:  
                queue.append(i)  
                visited[i] = True  

graph = [  
    [],    
    [2, 3, 8],  
    [1, 7],  
    [1, 4, 5],  
    [3, 5],  
    [3, 4],  
    [7],  
    [2, 6, 8],  
    [1, 7]  
]  

visited = [False] * 9  

bfs(graph, 1, visited)

해당 예제는 '이것이 코딩 테스트다 with python' 책에서 나온 구현방법이며 가장 기본적인 형태를 가지고 있다. 문제와 다른 점은 그래프에 대한 정보가 어떻게 주어지는지이다.

# 예제
graph = [  
    [],    
    [2, 3, 8],  
    [1, 7],  
    [1, 4, 5],  
    [3, 5],  
    [3, 4],  
    [7],  
    [2, 6, 8],  
    [1, 7]  
]

# 문제
graph = [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 4],
    [3, 4]
]

• 예제는 graph[i][:] 로 i번째 노드가 몇번 노드와 연결되어있는지 정보가 나열되어있다.
• 문제는 2차원 배열로 하나의 요소가 연결된 어떤 노드끼리 연결되어 있는지 정보가 나열되어있다.

문제 상황

그래서 리스트 컴프리헨션으로 list = [i[1] for i in graph if i[0] == v] 해당 노드가 연결되어 있는 노드의 정보를 추출해서 비슷한 방식으로 풀려고 했으나 당연히 되지 않았다. (여기서 v는 시작 노드이며 i[1]을 추출해 해당 노드가 어떤 노드와 연결되어있는지 추출해 배열로 만들었다.)

• 왜냐하면 각 요소의 i[0]가 아닌 i[1]인 경우는 고려하지 않기 때문이다.
• 예를 들어 [1, 4], [2, 1] 처럼 있다고 가정하자 위와 사실상 '1'노드는 '2', '4'와 연결되어있는데 위와 같이 코드를 작성하면 '2' 노드에 방문을 하지 못한다.

해결 방법

입력 받은 노드의 연결 정보에서 각 요소의 위치를 바꿔 graph에 추가해준다. 코드로 보면 다음과 같다.

# 기존 정보
graph = [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 4],
    [3, 4]
]
# 위치 변경 
change_location = [
    [2, 1],
    [3, 1],
    [4, 1],
    [4, 2],
    [4, 3]
]
# 최종 결과
result = [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 4],
    [3, 4],
    [2, 1],
    [3, 1],
    [4, 1],
    [4, 2],
    [4, 3]
]

이처럼 위치를 바꾼정보를 탐색할 정보 리스트에 합쳐주면 해결할 수 있다. 어짜피 재방문한 경우 코드 상에서 dfs 메서드를 호출하지 않도록 구현하기 때문에 제대로 동작하는걸 확인할 수 있었다.

정답 코드

# DFS와 BFSfrom collections import deque  

n, m, v = map(int, input().split())  

graph = []  
for i in range(m):  
    graph.append(list(map(int, input().split())))  

visited_dfs = [False] * (n + 1)  
visited_bfs = [False] * (n + 1)  

list_1 = [i[0] for i in graph]  
list_2 = [i[1] for i in graph]  

for i in range(m):  
    graph.append([list_2[i], list_1[i]])  

def dfs(v):  
    visited_dfs[v] = True  
    print(v, end=' ')  

    list = [i[1] for i in graph if i[0] == v]  
    list.sort()  

    for i in list:  
        if not visited_dfs[i]:  
            dfs(i)  


def bfs(v):  
    queue = deque([v])  

    visited_bfs[v] = True  

    while queue:  
        v = queue.popleft()  

        print(v, end=' ')  

        list = [i[1] for i in graph if i[0] == v]  
        list.sort()  

        for i in list:  
            if not visited_bfs[i]:  
                queue.append(i)  
                visited_bfs[i] = True  

dfs(v)  
print()  
bfs(v)

입력 값의 위치변환 후 병합

list_1 = [i[0] for i in graph]  
list_2 = [i[1] for i in graph]  

for i in range(m):  
    graph.append([list_2[i], list_1[i]])  

dfs

def dfs(v):  
    visited_dfs[v] = True  
    print(v, end=' ')  

    list = [i[1] for i in graph if i[0] == v]  
    list.sort()  

    for i in list:  
        if not visited_dfs[i]:  
            dfs(i)  

• 시작 위치에서의 값으로 연결된 노드의 정보를 리스트로 추출하고 sort함수를 통해 정렬한다.(왜냐하면 문제에서 작은 수부터 방문하라고 했기 때문이다.)
• 그리고 이전에 알던 구현 방법으로 재귀호출을 통해 그래프 탐색을 한다.

bfs

def bfs(v):  
    queue = deque([v])  

    visited_bfs[v] = True  

    while queue:  
        v = queue.popleft()  

        print(v, end=' ')  

        list = [i[1] for i in graph if i[0] == v]  
        list.sort()  

        for i in list:  
            if not visited_bfs[i]:  
                queue.append(i)  
                visited_bfs[i] = True  

• dfs와 마찬가지로 시작 위치에서 연결된 노드를 추출하고 queue를 사용하여 bfs를 구현

이 글은 'HTTP 완벽 가이드' 책을 읽고 정리한 내용입니다.

• HTTP는 어떻게 TCP 커넥션을 사용하는가
• TCP 커넥션의 지연, 병목, 막힘
• 병렬 커넥션, keep-alive 커넥션, 커넥션 파이프라인을 활용한 HTTP의 최적화
• 커넥션 관리를 위해 따라야 할 규칙들

  4.1 TCP 커넥션

TCP/IP TCP(Transmission Control Protocol) - 전송 제어 프로토콜로 한 기기에서 다른 기기로 데이터 전송을 담당 IP(Internet Protocol) - 인터넷 프로토콜로 데이터의 조각(fragment)을 대상 IP주소로 보내는 역할

TCP

• 커넥션을 맺을 수 있다.
• 케넥션이 맺어지면 클라이언트 <-> 서버 컴퓨터 간에 데이터 손실없이 안전하게 전달된다.

  UDP

• User Datagram Protocol
• 커넥션을 맺을 수 없다.
• TCP에 비해 안전성은 떨어지지만 더 빠르고 간단하다. (스트리밍, 게임과 같은 곳에서 사용)

URL입력시 동작 과정

1. 브라우저가 (특정 URL)의 호스트 명을 추출한다.
2. 브라우저가 호스트 명에 대한 IP주소를 찾는다.
3. 브라우저가 포트 번호(80)를 얻는다.
4. 브라우저는 IP주소의 80번 포트로 TCP 커넥션 을 생성한다.
5. 이후 클라이언트 <-> 서버의 요청 응답
6. 브라우저가 커넥션을 끊는다.

   4.1.1 신뢰 할 수 있는 데이터 전송 통로인 TCP

• TCP 커넥션은 인터넷을 안정적으로 연결해준다. (신뢰할 만한 통신 방식 제공)
• 바이트들이 순서에 맞게 정확히 전달된다. (데이터의 손실, 손상 등이 없기 때문에)

4.1.2 TCP 스트림은 세그먼트로 나뉘어 IP 패킷을 통해 전송된다.

HTTPS (Hypertext Transfer Protocol Secure)

• 기존 http protocol 의 보안 기능을 더한 것
• TLS or SSL 이라고 불리는 암호화 계층이 추가

HTTP 메세지 전송

• TCP 커넥션을 통해 데이터의 내용을 순서대로 전송
• 세그먼트라는 단위로 데이터 스트림을 나눈 후에 IP 패킷에 담아 전송
• IP 패킷
  • IP 패킷 헤더 (20 ~ 60byte) - 20byte 초과 시 option 필드가 존재한다. (in IPv4)
  • TCP 세그먼트 헤더 (20byte)
  • TCP 데이터 조각(0 ~ 그 이상의 byte)

4.1.3 TCP 커넥션 유지하기

• 컴퓨터 여러 개의 TCP 커넥션을 가지고 있다.
  • 포트 번호를 통해서 여러 커넥션을 유지
• TCP 커넥션 식별
  • < src ip addr, src port, des ip addr, des port>
  • 이 값들이 모두 같은 경우는 존재할 수 없다.

4.1.4 TCP 소켓 프로그래밍

• 운영체제는 TCP 커넥션의 생성과 관련된 여러 기능 제공

  클라이언트와 서버가 TCP 소켓 인터페이스를 사용하여 상호작용

• S 소켓 생성 후 80포트로 소켓을 묶는다. 이후 커넥션 허가 및 커넥션을 기다린다(클라이언트로부터)
• C IP addr, port를 얻고 소켓을 생성 후 서버의 IP:port 로 연결
• S <-> C 연결 이후 요청과 응답 과정을 수행
• 더 이상의 요청이 없을 때, 커넥션을 종료

4.2 TCP의 성능에 대한 고려

• HTTP는 TCP의 상위 계층이기 때문에 HTTP 트랜잭션의 성능은 TCP 성능에 영향을 받는다

  4.2.1 HTTP 트랜잭션 지연

• 트랜잭션을 처리하시는 시간 < TCP 커넥션 설정 시간, 요청 전송 및 응답 시간
  • 대부분의 HTTP 지연은 TCP 네트워크 지연 때문에 발생

    1. URL 호스트 명을 IP주소로 변환하는 과정 (초기 방문시)
    2. 클라이언트의 TCP 커넥션 요청 ( 보통 1~2초지만 요청이 많으면 소요 시간 크게 증가)
    3. 서버가 요청 메세지를 읽고 처리하는 시간
    4. 요청 처리 후  HTTP 응답을 보내는 시간

  • 이러한 TCP 네트워크 지연은 다음과 같은 요인이 있다.
    • HW 성능
    • 네트워크와 서버의 전송 속도
    • 요청과 응답 메세지의 크기
    • 클라이언트와 서버 간의 거리

      4.2.2 성능 관련 중요 요소 ( 가장 일반적인 TCP 관련 지연들 )

4.2.3 TCP 커넥션 핸드셰이크 지연

TCP 커넥션 핸드셰이크

• TCP 커넥션을 맺기 위해 연속적으로 IP패킷을 교환하는 과정
• 하지만, 작은 크기의 데이터 전송에 이러한 커넥션 연결과정은 HTTP 성능을 저하시킬 수 있다.
• 핸드셰이크 과정
  1. 클라이언트가 SYN 라는 플래그를 가지는 TCP 패킷(40~60byte)을 서버에게 보낸다.
  2. 서버는 몇가지 커넥션 매개변수 산출 후, 요청이 받아졌다는 SYN + ACK 플래그를 가진 TCP 패킷을 보낸다.
  3. 마지막으로, 클라이언트는 커넥션이 잘 맺어졌음을 알리는 응답신호를 보낸다.( 이때 같이 데이터를 보낼 수 있다.)
• 크기가 작은 HTTP 트랜잭션은 50%이상의 시간을 위와 같은 TCP 커넥션을 구성하는데 사용된다.

4.2.4 확인응답 지연

• 인터넷 자체가 패킷 전송을 완벽히 보장하지 않는다.
  • 혼잡 상태거나 TTL이 0이 되는 패킷들은 라우터에서 폐기한다.

    성공적인 데이터 전송을 보장하기 위한 TCP의 자체적 확인 체계

• 각 TCP 세그먼트는 순번, 데이터 무결성 체크섬을 가진다.
  • 전송 성공 시(각 세그먼트를 온전히 받음), src 쪽에 확인 응답 패킷 전송
  • 전송 실패 시(확인 응답 패킷 X), 다시 재전송
• 확인 응답
• 편승 - 크기가 작기 때문에 같은 방향(즉, 수신자가 송신자에게 보낼 때)으로 송출되는 데이터에 같이 실어서 보낸다
  • 편승되는 경우의 수를 늘리기 위해 확인응답 지연 알고리즘을 구현
    1. 송출할 확인응답을 특정 시간동안 버퍼에 저장
    2. 편승시키기 위한 데이터 패킷 탐색
    3. 일정 시간 내 찾지 못하면 별도의 패킷으로 전송
  • 실제로 편승시킬 수 있는 경우가 적기 때문에 지연 알고리즘으로 인한 지연이 자주 발생
  • 요청과 응답 두가지 형식으로만 이루어져 있기 때문에

    4.2.5 TCP 느린 시작(slow start)

    인터넷의 혼잡 제어 방법

• TCP 커넥션은 만들어진 지 얼마나 지났는지에 따라 달라질 수 있다.
• 시간이 지나면서 자체적으로 튜닝 된다.
  • 속도 제한
    • 처음에는 커넥션의 최대 속도 제한, 이후 성공적으로 전송 시 속도 제한을 높여나간다.
  • 패킷 수 제한
    • 패킷이 성공적으로 전달 시, 추가로 2개의 패킷을 더 전송할 수 있는 권한이 생긴다.

[정리] 처음부터 많은 데이터, 빠른 속도로 보낼 시 혼잡이 발생할 수 있기 때문에 천천히, 작은 데이터를 보내보면서 속도와 크기를 늘려나가는 방식의 혼잡 제어

4.2.6 네이글 알고리즘과 TCP_NODELAY

• 애플리케이션이 어떤 크기의 데이터든지 TCP 스택으로 전송할 수 있도록 인터페이스를 제공

  • TCP 세그먼트는 40byte 상당의 플래그와 헤더를 포함
  • 작은 데이터 패킷을 많이 보내면 위와 같은 헤더 또한 같은 수로 증가하기 때문에 네트워크 성능 저하

    많은 양의 TCP 데이터를 합치는 알고리즘 ??

• 네이글 알고리즘은 세그먼트가 최대 크기 (1500byte 정도)가 되지 않으면 전송 X

• 다른 모든 패킷이 확인응답 받았을 경우, 최대 크기보다 작은 패킷 전송 허락

• 다른 패킷들이 아직 전송 중, 데이터는 버퍼에 저장된다.

  • 전송되고 나서 확인응답을 기다리던 패킷이 확인응답 혹은 충분한 패킷이 쌓였을 때 버퍼에 저장된 데이터가 전송된다.

  추가

1. TCP가 데이터를 전송할 때, 첫 번째 패킷이 네트워크를 통해 전송되고 그에 대한 확인 응답(ACK)을 기다립니다.
2. 첫 번째 패킷에 대한 ACK가 도착하기 전에는, 작은 크기의 메시지들을 큐에 저장하고, 이 메시지들을 누적시켜 하나의 큰 패킷으로 만듭니다.
3. 첫 번째 패킷에 대한 ACK가 도착하면, 큐에 누적된 메시지들을 하나의 큰 패킷으로 전송합니다.

   문제점

• 크기가 작은 HTTP 메세지는 추가적인 데이터를 기다리며 지연
• 확인응답 지연과 함께 쓰일 경우 형편없이 동작
  • 확인응답이 도착할때까지 데이터 전송을 멈추고 있는 반면, 확인응답 지연 알고리즘은 확인응답을 100~200ms 지연시킨다.
• 그래서 성능 향상을 위해 TCP_NODELAY를 설정해 네이글 알고리즘을 비활성화 하기도 한다.
  • 이럴 경우 작은 크기의 패킷이 많이 생기는 것을 방지하기 위해 큰 크기의 데이터 덩어리를 만들어야함.

4.2.7 TIME_WAIT의 누적과 포트 고갈

• TCP 커넥션을 끊으면 종단에서는 커넥션의 IP 주소와 포트 번호를 메모리의 작은 제어영역에 기록
  • 이는 새로운 커넥션이 일정시간동안 생성되지 않기 위한 목적
  • 세그먼트 최대 생명주기의 두배(약 2분)가 유지된다.
• 서버의 성능에 따라 포트 고갈이 일어날 수도 있다.
  • 트랜잭션을 빠르게 처리하면 일어날 가능성이 높다.
• 커넥션을 너무 많이 맺거나 대기 상태로 있는 제어 블록이 많아지는 상황을 주의해야한다.

  4.3 HTTP 커넥션 관리

• 커넥션을 생성하고 최적화하는 HTTP 기술

  4.3.1 흔히 잘못 이해하는 Connection 헤더 ??

• HTTP는 클라이언트와 서버 사이 중개 서버(프락시, 캐시)가 놓으는 것을 허락한다.
• HTTP 메세지는 이 중개 서버를 거치면서 전달된다.
• Connection 헤더 필드는 커넥션 토큰을 쉼표로 구분하여 가지고 있는다.
• 세 종류의 토큰이 전달 될 수 있다.
  • HTTP 헤더 필드 명은, 이 커넥션에만 해당되는 헤더들을 나열
  • 임시적인 토큰 값은, 커넥션에 대한 비표준 옵션을 의미
  • close 값은, 커넥션이 작업이 완료되면 종료되어야함을 의미
• 커넥션 토큰이 HTTP 헤더 필드 명을 가지고 있으면, 현재 커넥션만을 위한 정보이므로 다음 커넥션에 전달되면 안된다.

4.3.2 순차적인 트랜잭션 처리에 의한 지연

• 3개의 이미지가 있는 웹페이지. 이 페이지를 보여주기 위해서
  • 4개의 HTTP 트랜잭션을 만든다.
    • 커넥션 발생 지연 + 느린 시작 지연 발생
  • 여러 개의 이미지 동시 로드
    • 모든 객체를 내려받기 전까지 텅 빈 화면을 보여줘야 한다.

      HTTP 커넥션의 성능을 향싱 시킬 수 있는 기술

• 병렬 커넥션
  • 여러 개의 TCP 커넥션을 통한 동시 HTTP 요청
• 지속 커넥션
  • 커넥션을 맺고 끊는 데서 발생하는 지연 제거를 위한 케녁션 재활용
• 파이프라인 커넥션
  • 공유 TCP 커넥션을 통한 병렬 HTTP dycjd
• 다중 커넥션
  • 요청과 응답들에 대한 중재( 실험적인 기술 )

4.4 병렬 커넥션

• HTTP는 클라이언트가 여러 개의 커넥션을 맺음으로써 여러 개의 HTTP 트랜잭션을 병렬로 처리할 수 있게 한다.

  4.4.1 병렬 커넥션은 페이지를 더 빠르게 내려받는다

• 단일 커넥션의 대역폭 제한, 커넥션이 동작하지 않고 있는 시간을 활용하면 => 객체가 여러 개 있는 웹페이지를 더 빠르게 내려받을 수 있다.
• 즉, 단일 커넥션의 대역폭을 쪼개서 사용하는 것 -> 한번의 핸드셰이크만 필요한가? No

  4.4.2 병렬 커넥션이 항상 더 빠르지는 않다

• 일반적으로 더 빠르지만 항상 그렇지는 않다.
  • 대역폭이 좁을 때 여러개의 객체를 병렬로 내려받는 경우, 제한된 대역폭 내에서 전송받는 것은 느리기 때문에 성능상에 장점은 거의 없다.
• 다수의 커넥션은 메모리를 많이 소모, 자체적인 성능 문제 발생
  • 실제로는 4개 정도의 벙렬 커넥션만을 허용

    4.4.3 병렬 커넥션은 더 빠르게 '느껴질 수' 있다.

• 항상 빠르게 로드하지는 않는다.
• 하지만 여러 개의 객체가 동시에 보여지면서 더 빠르게 느낄 수 있다.

  4.5 지속 커넥션

• 요청에 대한 처리가 완료된 후에도 계속 연결된 상태로 있는 TCP 커넥션
• 커넥션을 끊기 전까지는 트랜잭션 간에도 커넥션을 유지한다.
• TCP의 느린시작으로 인한 지연을 피함으로써 더 빠르게 데이터 전송이 가능

  4.5.1 지속 커넥션 vs 병렬 커넥션

  병렬 커넥션

  장점

• 여러 객체가 있는 페이지를 더 빠르게 전송한다.

  단점

• 각 트랜잭션마다 새로운 커넥션을 맺고 끊기 때문에 시간, 대역폭이 소요
• 각 새로운 커넥션은 TCP 느린 시작으로 인한 지연 발생
• 실제로 연결 가능한 병렬 커넥션 수의 제한

  지속 커넥션

  장점

• 커넥션을 맺기 위한 사전 작업, 지연을 줄여준다.
• 튜닝된 커넥션을 유지하며 커넥션의 수를 줄여준다.

  단점

• 지속 커넥션을 잘못 관리할 경우, 계속 연결된 상태로 수많은 커넥션이 쌓인다.
  • 이는 로컬의 리소스, 원격의 클라이언트와 서버의 리소스에 불필요한 소모를 발생한다.

[결론] 지속 커넥션은 병렬 커넥션과 함께 사용될 때 가장 효과적이다!

HTTP/1.0+ : keep-alive 커넥션

HTTP/1.1 : 지속 커넥션

4.5.2 HTTP/1.0+의 Keep-Alive 커넥션

새로운 커넥션을 맺고 끊는 데 필요한 작업이 없어서 시간이 단축

4.5.3 Keep-Alive 동작

1. 클라이언트는 요청에 Connection:Keep-Alive 헤더를 포함 시킨다.
2. 요청을 받은 서버는 두가지 경우가 존재
   • Keep-Alive 지원
     • 응답 메세지에 같은 헤더를 포함 시켜 응답
   • Keep-Alive 미지원
     • 헤더를 포함시키지 않고 응답 -> 응답 전송 후 서버 커넥션을 끊을 것이라 추정

       4.5.4 Keep-Alive 옵션

• 언제든지 현재의 Keep-Alive 커넥션을 끊을 수 있으며 처리되는 트랜잭션의 수를 제한할 수 있다.
  • Keep-Alive의 동작은 Keep-Alive 헤더의 쉼표로 구분된 옵션들로 제어
    • timeout
      • Keep-Alive 응답 헤더를 통해 보낸다.
      • 커넥션이 얼마나 유지될 것인지를 의미( 실제로 이대로 동작한다는 보장은 없다.)
    • max
      • Keep-Alive 응답 헤더를 통해 보낸다.
      • 몇 개의 HTTP 트랜잭션을 처리할 때까지 유지 될 것인지를 의미( 실제로 이대로 동작한다는 보장은 없다.)
  • Keep-Alive 헤더 사용은 선택 사항이지만 Conncetion: Keep-Alive 헤더가 있을 때만 사용할 수 있다.

Connection: Keep-Alive
Keep-Alive: max:5, timeout:120

=> 5개의 추가 트랜잭션이 처리될 동안 or 2분동안 커넥션 유지하라는 응답 헤더

4.5.5 Keep-Alive 커넥션 제한과 규칙

1. keep-alive는 HTTP/1.0에서 기본으로 사용되지 않는다. 클라이언트는 Connection: Keep-Alive 요청 헤더를 보내야 한다.
2. 커넥션을 유지하려면 모든 메세지에 Connection: Keep-Alive 헤더를 포함해야한다. 미 포함시 서버가 커넥션을 끊을 것이다.
3. 클라이언트는 서버의 Connection: Keep-Alive 응답 헤더가 없는 것을 보고 커넥션을 끊을 것을 알 수있다.
4. 커넥션이 끊어지기 전 엔터티 본문의 길이를 알 수 있어야 커넥션을 유지할 수 있다.
   • 엔터티 본문이 정확한 Content-Length값과 Type, 청크 전송 인코딩으로 인코드 되어야 함을 뜻함
   • 잘못된 Length값은 트랜잭션이 끝나는 시점에 기존 메세지의 끝과 새로운 시작을 정확히 알 수 없다.
5. keep-alive 커넥션은 Connection: Keep-Alive 헤더를 인식하지 못하는 서버와 맺어지면 안된다. 현실적으로는 쉽지 않다.
6. 기술적으로 HTTP/1.0을 따르는 기기로부터 받는 모든 Connection 헤더 필드는 무시해야한다.
   • 오래된 프락시 서버로부터 실수로 전달될 수 있고 오래된 프락시에 행이 걸릴 수 있는 위험이 있다.
   • 하지만 이 규칙을 지키지 않기도 한다.
7. 클라이언트는 응답 전체를 모두 받기 전 커넥션이 끊어졌을 경우, 요청이 반복될 경우 생기는 문제가 있기 때문에 요청을 다시 보낼 수 있게 준비되어있어야한다.

   4.5.6 Keep-Alive와 멍청한(dumb) 프락시

   

• 멍청한 프락시는 HTTP의 Connection 헤더를 단순히 확장 헤더로만 취급. 즉, 이해하지 못한다.
• 첫 요청과 응답을 통해 클라이언트와 서버는 프락시 서버와 같이 커넥션을 유지하는 것으로 알고 있다.
• 클라이언트는 keep-alive 커넥션으로 계속 요청을 보낸다.
• 서버는 적어도 max, timeout과 같은 매개변수의 값만큼 커넥션을 유지한다.
• 하지만 멍청한 프락시는 커넥션이 끊이지기만을 기다린다.

프락시와 홉별 헤더

• 이런 잘못된 통신을 피하기 위해 프락시는 Connection 헤더를 전달하면 안된다.
• 또한, Proxy-Connection 등과 같은 홉별 헤더들 역시 전달하거나 캐시하면 안된다.

  4.5.7 Proxy-Connection 살펴보기

• Proxy-Connection 헤더를 사용해 클라이언트의 요청이 중개서버를 통해 이어지는 경우 모든 헤더를 무조건 전달하는 문제를 해결
• 멍청한 프락시는 홉별 헤더를 무조건 전달하기 때문에 문제를 일으킨다.

멍청한 프락시

• 클라이언트는 Proxy-Connection을 보내고 프락시 서버는 그대로 전달한다.
• 서버는 이를 무시하고 응답을 보낸다.
• 프락시와 클라이언트, 서버 사이에 커넥션이 유지되지 않는다.

  영리한 프락시

• 클라이언트는 Proxy-Connection을 보내고 프락시 서버는 제대로된 Connection 헤더를 보낸다.
• 서버는 일반적으로 커넥션을 유지하기 위해 응답을 보낸다.
• 프락시와 클라이언트, 서버 사이에 커넥션이 유지된다.

중개 서버에 멍청한 프락시와 영리한 프락시가 같이 있으면 문제가 발생한다.

• 게다가 문제를 발생시키는 프락시들은 방화벽, 캐시 서버, 리버스 프락시 서버 가속기와 같이 네트워크상에서 '보이지 않는' 경우가 많다.

4.5.8 HTTP/1.1의 지속 커넥션

• HTTP/1.1에서는 keep-alive를 지원하지 않는 대신 더 개선된 지속 커넥션을 지원한다.
• HTTP/1.1에서는 별도 설정을 하지 않는 한, 모든 커넥션을 지속 커넥션으로 취급한다.
• HTTP/1.1 애플리케이션은 트랜잭션이 끝난 후 Connection:close 헤더를 명시해야 커넥션을 끊을 수 있다.
  • 하지만 Connection:close 를 보내지 않는 것이 서버가 커넥션을 영원히 유지하겠다는 뜻은 아니다.
  • 클라이언트와 서버는 마친가지로 언제든지 커넥션을 끊을 수 있다.
    • 이게 Connection 헤더의 파라미터 값대로 동작을 보장하지 못하는 이유

4.5.9 지속 커넥션의 제한과 규칙

1. 클라이언트가 요청에 Connection:close 헤더를 포함했다면, 더 이상 그 커넥션으로 요청을 보낼 수 없다.
2. 클라이언트가 추가 요청이 없을 경우 마지막에 Connection:close 헤더를 보내야한다.
3. 커넥션에 있는 모든 메세지는 자신의 Length정보가 정확해야 커넥션을 지속 가능
   • 엔터티 본문은 정확한 Content-Length값을 가진다
   • 청크전송 인코딩으로 인코드 되어 있어야한다.
4. HTTP/1.1 프락시는 클라이언트, 서버 각각에 별도의 지속 커넥션을 맺고 관리
5. HTTP/1.1 프락시 서버는 클라이언트의 지원 범위를 알고 있지 않다면 지속 커넥션을 맺으면 안된다.
   • 오래된 프락시의 Connection 헤더 전달 문제
   • 현실적으로 지키기 쉽지 않다.
     6. 서버는 메세지 전송 중 커넥션을 끊지 않고 끊기 전 적어도 한개의 요청에 대해 응답은 하지만 HTTP/1.1 기기는 Connection 헤더 값과 상관 없이 언제든지 끊을 수 있다.
     7. HTTP/1.1 애플리케이션은 중간에 끊어지는 커넥션을 복구할 수 있어야만 한다.
     8. 클라이언트는 전체 응답전 커넥션이 끊어지면 요청을 반복해서 보내도 문제 없는 경우 보낼 준비가 되어있어야한다.
     9. 하나의 사용자 클라이언트는 서버 과부화를 방지하기 위해, 넉넉하게 2개의 지속 커넥션을 유지해야 한다.

4.6 파이프라인 커넥션

파이프라인의 제약 사항

1. HTTP 클라이언트는 커넥션이 지속 커넥션인지 확인하기 전까지는 파이프라인을 이어서는 안된다.
2. HTTP 응답은 요청 순서와 같게 와야 한다. HTTP 메세지는 순번이 매겨져 있지 않아서 응답이 순서 없이 오면 순서에 맞게 정렬시킬 방법이 없다.
3. HTTP 클라이언트는 커넥션이 언제 끊어지더라도, 완료되지 않은 요청이 파이프라인에 있으면 언제든 다시 요청 보낼 준비가 되어 있어야 한다.
   • 10개 요청후 5개의 응답만 받고 커넥션이 끊김
   • 남은 5개의 실패한 요청을 커넥션을 다시 맺고 요청을 보낼 수 있어야한다.
4. HTTP 클라이언트는 POST 요청같이 반복해서 보낼 경우 문제가 생기는 요청은 파이프라인을 통해 보내면 안된다.
   • 에러 발생시, 요청 중 어떤 것들이 서버에서 처리되었는지 클라이언트가 알 방법이 없다.
   • POST와 같은 비멱등(연산이 한번 일어날 때 마다 결과가 변할 수 있는) 요청을 재차 보내면 문제가 생길 수도 있다.

4.7 커넥션 끊기에 대한 미스터리

• 커넥션 관리(언제 끊어야 하는지)에는 명확한 기준이 없다.

4.7.1 '마음대로' 커넥션 끊기

• 어떠한 HTTP 클라이언트, 서버, 혹은 프락시든 언제든 TCP 커넥션을 끊을 수 있다.
  • 보통은 메세지를 다 보낸 다음 끊는다

4.7.2 Content-Length와 Truncation

• 각 HTTP 응답은 본문의 정확한 크기 값을 가지는 Content-Length 헤더를 가지고 있어야 한다.

4.7.3 커넥션 끊기의 허용, 재시도, 멱등성

• 커넥션은 심지어 에러가 없더라도 언제든 끊을 수 있다.
• 이에 HTTP 애플리케이션은 예상치 못하게 커넥션이 끊어졌을 때에 적절히 대응할 수 있는 준비가 되어있어야한다.
  • 트랜잭션 수행중 커넥션이 끊기면, 클라이언트는 다시 커넥션을 맺고 한번 더 전송 시도
  • 클라이언트는 요청을 큐에 쌓아 놓을 수 있다.
  • 반면, 서버는 아직 처리되지 않고 스케줄이 조정되어야하는 요청을 남겨둔 채로 커넥션을 끊어 버릴 수 있다.
• 클라이언트는 커넥션이 끊기면 서버에서 얼마만큼 요청이 처리되었는지 알 수 없다.
  • 이는 GET요청은 상관 없지만 POST같은 비멱등 경우 문제가된다.
  • 멱등
    • GET, HEAD, PUT, DELETE, TRACE
  • 비멱등
    • POST

** [멱등, 비멱등]** 여러번 요청해도 서버에서 상태가 변하는 유무에 따라 나뉘게 된다. ** **PUT -> 여러번 실행해도 리소스의 상태가 마지막 PUT 요청의 페이로드를 반영한 상태로 유지된다. DELETE -> 여러번 실행해도 서버에서 리소스의 상태가 '삭제'라는 최종 상태에는 변함이 없다. POST -> 예를 들어 첫번째 요청으로 사용자가 생성된 후 또 요청을 보내면 중복되는 새로운 사용자가 생성될 수 있기 때문에 서버의 상태가 두번의 요청 후에 다르게 되기 때문에 비멱등이다.

4.7.4 우아한 커넥션 끊기

• TCP 커넥션은 양방향이다.

  전체 끊기와 절반 끊기

• 전체 끊기
  • 애플리케이션은 TCP 입력 채널과 출력 채널 중 한 개만 끊거나 둘 다 끊을 수 있다.
  • 방법 : close() 호출
• 절반 끊기
  • 입력, 출력 중 하나를 개별적으로 끊을 수 있다.
  • 방법: shutdown() 호출

TCP 끊기와 리셋 에러

• 단순한 HTTP 애플리케이션은 전체 끊기만 사용할 수 있다.
  • 애플리케이션이 각기 다른 HTTP 클라이언트, 서버, 프락시와 통신할 때
  • 그들과 파이프라인 지속 커넥션을 사용할 때
  • 예상치 못한 쓰기 에러를 예방하기 위해 절반 끊기를 사용해야함
• 보통은 출력 채널을 끊는 것이 안전
  • 반대편 기기는 더이상 입력이 없음으로 내가 출력 커넥션을 끊었다는 것을 알게 됨
• 클라이언트는 데이터를 더 보내지 않는 것에 확신하지 않는 이상, 입력 채널을 끊는 것은 위험
  • 끊긴 상태에서 데이터 전송시 , 서버의 운영체제는 TCP 'connection reset by peer' 메세지를 보냄
  • 이는 심각한 에러로 취급, 버터에 저장된 + 아직 읽히지 않은 데이터 전부 삭제
  • Example
    • C - 10개의 요청을 파이프라인 지속 커넥션을 통해 전송
    • S - 10개의 응답을 버퍼에 저장 ( 아직 애플리케이션이 읽지 않음)
    • 이미 충분히 오래 유지되었다고 판단 -> 커넥션 종료
    • C - 11번째 요청 전송
    • S - 'connection reset by peer' 메세지 응답 및 , 버퍼에 저장된 응답 데이터 전부 삭제

우아하게 커넥션 끊기

• 애플리케이션의 우아한 커넥션 끊기
  • 자신의 출력 채널 끊는다.
  • 다른 쪽의 출력 채널이 끊기는 것을 기다린다. ( 자신의 입력채널에 더 이상 데어티가 안들어옴)
• 하지만 상대방이 절반 끊기를 구현했다는 보장 X
• 절반 끊기를 했는지 검사해준다는 보장 X
• 따라서 자신의 출력 채널에 절반 끊기 후, 입력 채널의 대해 상태를 주기적으로 검사
  • 만약 입력 채널이 timeout 시간 내에 끊어지지 않는다면 리소스 보호를 위해 커넥션을 강제로 종료

Spring에서의 동작과정

• Spring Framework에서 요청과 응답을 담당하는 서블릿 컨테이너는 WAS의 일부
• HTTP 요청을 받아 처리하고 응답을 반환하는 역할을 한다.
  • TCP 커넥션 관리는 이 과정에서 중요한 부분 중 하나
• 동작 과정
  1. TCP 커넥션 개설: 클라이언트가 -> 서버 연결 요청. 서블릿 컨테이너 내부의 웹 서버는 TCP 소켓을 열고, 클라이언트와 서버 간의 TCP 커넥션 개설(3-way handshake과정을 통해 연결 설정)
  2. 요청 처리: TCP 커넥션을 통해 전송된 HTTP 요청은 서블릿 컨테이너에 도달합니다. 서블릿 컨테이너는 해당 요청을 분석하여 적적한 서블릿에 전달. (서블릿은 요청을 처리 후 응답 생성)
     • Handler Mapping
  • 들어오는 요청을 해당하는 핸들러(컨트롤러)를 찾아 매핑한다. (Spring MVC)

      1. **요청 식별**: 클라이언트로부터 들어온 요청은 먼저 DispatcherServlet에 의해 받아진다. DispatcherServlet은 Spring MVC의 프론트 컨트롤러 역할.
      2. **핸들러 매핑 조회**: DispatcherServlet은 등록된 핸들러 매핑 전력을 조회, 요청 URL에 해당하는 핸들러(컨트롤러 메소드) 를 찾는다.
      3. **핸들러 실행**: 매핑된 핸들러가 결정되면, DispatcherServlet은 해당 핸들러 실행. (이 과정에서 핸들러에 필요한 다양한 파라미터가 바인딩, 비지니스 로직이 수행)
      4. **뷰 리졸빙 및 응답 반환**: 핸들러의 실행 결과를 바탕으로, DispatcherServlet은 적절한 뷰를 찾아 클라이언트에게 응답을 반환. (혹은 JSON 타입의 데이터 반환)

  • @RequestMapping
  3. 응답 반환: 처리된 응답은 다시 HTTP 응답으로 클라이언트에게 전송
  4. 커넥션 유지 및 종료 : HTTP/1.1 스펙에 따라, 일정 시간동안 커넥션 유지 될 수 있다.
  5. 커넥션 풀링: 성능 최적화를 위해 서블릿 컨테이너는 종종 TCP 커넥션 풀을 사용. 미리 생성된 TCP 커넥션의 집합으로, 요청이 들어올 때마다 새로운 커넥션을 개설하는 대신 풀에 있는 커넥션을 재사용
  6. 비동기 처리: 최신의 서블릿 컨테이너는 비동기 처리 지원, 하나의 요청 처리가 완료될 때까지 TCP 커넥션을 유지하면서도 그 동안 다른 요청을 처리할 수 있다.

이 글은 'HTTP 완벽 가이드' 책을 읽고 정리한 내용입니다.

HTTP가 인터넷의 배달원이라면, HTTP 메시지는 무언가를 담아 보내는 소포와 같다.

메시지의 흐름

메시지는 클라이언트, 서버, 프락시 사이를 흐르며 메시지의 방향을 의미하는 용어는 다음과 같다.

• 인바운드
• 아웃바운드
• 업스트림
• 다운스트림

1. 메시지는 원 서버 방향을 인바운드로 하여 송신된다.

• 인바운드 : 메시지가 원 서버로 향하는 것
• 아웃바운드 : 모든 처리가 끝난 뒤에 메시지가 클라이언트로 돌아오는 것

  2. 다운스트림으로 흐르는 메시지

  HTTP 메시지는 강물과 같이 흐른다. 요청, 응답 메시지에 관계없이 모든 메시지는 다운스트림으로 흐른다.

메시지의 각 부분

메시지는 시작줄, 헤더 블록, 본문 이렇게 세 부분으로 이루어진다.

• 시작줄과 헤더는 줄 단위로 분리된 아스키 문자열
• 각 줄은 캐리지 리턴(ASCII 13), 개행 문자(ASCII 10)로 구성된 두 글자의 줄바꿈 문자열로 끝난다.
  • 이 줄바꿈 문자열은 CRLF라고 쓴다 \r\n

문법

모든 HTTP 메시지는 "요청 메시지" , "응답 메시지" 으로 분류된다.

요청 메시지 형식

<메서드> <요청 URL> <버전>
<헤더>

<엔터티 본문>

응답 메시지 형식

<버전> <상태코드> <사유 구절>
<헤더>

<엔터티 본문>

시작줄

모든 HTTP 메시지는 시작줄로 시작하며 이것이 어떤 메시지인지 서술한다.

• 요청 메시지 : 무엇을 해야하는지
• 응답 메시지 : 무슨일이 일어났는지

요청줄

해당 부분에서 서버에서 어떤 동작이 일어나야 하는지 설명해준다.

• 메서드
• 동작에 대한 대상을 지칭하는 요청 URL
• HTTP 버전

  응답줄

  해당 부분에서 수행 결과에 대한 정보를 클라이언트에게 돌려준다.
  • 수행 결과에 대한 상태 정보
  • 결과 데이터
  • HTTP 버전
  • 상태 코드 및 사유 구절(수행상태에 대해 설명해주는 텍스트)

시작줄의 요소

메서드 : 서버에게 무엇을 해야하는지 말해주는 역할

• 'GET/special/saw-blade.gif HTTP/1.0'
• 여기서 'GET'이 메서드이다.

• 'GET', 'HEAD' 메서드와 같은 경우, 서버에 어떤 작용(DB 서버의 예로 데이터 등록, 수정, 삭제 등)도 없는 안전한 메서드라고 불린다.

상태 코드 : 클라이언트에게 무엇이 일어났는지 말해주는 역할

• 'HTTP/1.0 200 OK'
• 여기서 '200이 상태 코드이다.

(상태 코드에 대한 자세한 설명은 생략)

사유 구절 : 상태 코드에 대한 글로 된 설명, 응답 시작줄의 마지막 구성요소

• 'HTTP/1.0 200 OK'
• 여기서 'OK'가 사유 구절이다.

버전 번호 : 'HTTP/x.y'형태로 요청, 응답 메세지 양쪽 모두에 기술된다.

• 자신의 따르는 프로토콜의 버전을 상대방에게 말해주기 위한 수단
• 'HTTP/1.1'의 버전을 가지고 있다면 해당 버전까지 이해할 수 있음을 의미한다.

헤더 블록

헤더와 메서드는 클라이언트와 서버가 무엇을 하는지 결정하기 위해 함께 사용된다. 헤더는 크게 다섯가지로 분류된다.

1. 일반 헤더(General Headers)

• 기본적인 정보 제공
• 예를 들어 요청 메시지, 응답 메시지 작성 시, 요청, 응답의 생성 일시 등
• 일반 정보 헤더*

일반 캐시 헤더 HTTP/1.0에 도입된 것으로 매번 원 서버로부터 객체를 가져오는 대신, 로컬 복사본으로 캐시할 수 있는 헤더이다. (캐시에 대한 내용은 7장에서 자세히 설명)

2. 요청 헤더(Request Headers)

• 요청 메시지에서만 의미를 가지는 헤더
  • 누가, 무엇이 요청을 보냈는지에 대한 정보
  • 클라이언트의 선호, 능력에 대한 정보

요청 정보 헤더

요청 헤더의 종류 요청 헤더에는 기능에 따라 4가지로 분류된다.

1. Accept 관련 헤더 : 클라이언트가 무엇을 원하고 할 수 있는지에 대한 정보를 알려줄 수 있다. 이는 사용할 수 없는 것을 전송하는데 시간과 대역폭을 낭비하지 않기 때문에 서버, 클라이언트 양쪽 모두에게 유익하다.
2. 조건부 요청 헤더 : 이 요청 헤더를 사용하여 클라이언트는 서버에게 요청에 응답하기 전 자신이 설정한 조건이 참인지 확인하게 하는 제약을 포함시킬 수 있다.( 예를 들어 클라이언트 문서 사본 요청 시, 자신이 가지고 있는 사본과 다를 경우에만 전송을 해라)
3. 요청 보안 헤더 : 자체적으로 요청을 위한 간단한 인증요구/응답 체계를 가지고 있다. 이는 인증을 통해 트랜잭션을 더 안전하게 만들 수 있다.
4. 프락시 요청 헤더 : 프락시 서버의 기능을 돕기 위한 헤더

3. 응답 헤더(Response Headers)

• 클라이언트에게 부가 정보를 제공
• 누가 응답을 보내는지, 응답자의 능력 등을 설명하여 클라이언트가 더 나은 요청을 할 수 있도록 도와준다.

응답 정보 헤더

4. 엔터티 헤더(Entity Headers)

• 요청, 응답 양쪽 모두 포함할 수 있기 때문에, 양 타입의 메시지에 모두 나타날 수 있다.
• 엔터티와 내용물에 대한, 개체의 타입 및 리소스를 요청할 수 있는 유효한 메서드 등 광범위한 정보 제공

엔터티 정보 헤더

1. 콘텐츠 헤더 : 엔터티의 콘텐츠에 대한 구체적인 정보를 제공한다. (종류, 크기 등)

• 자주 보는 'Content-Type','Content-Length'가 여기 해당된다.

2. 엔터티 캐싱 헤더 : 리소스에 대해 키시된 사본이 아직 유효한지, 유효만료 시점이 언제인지 등

5. 확장 헤더(Extension Headers)

확장 헤더는 애플리케이션 개발자들에 의해 만들어졌지만 아직 승인된 HTTP 명세에는 추가되지 않는 비표준 헤더이다.

본문

엔터티 본문이라고도 불리는 해당 부분은 HTTP 메세지의 화물이라고 할 수 있다.

HTTP가 수송하도록 설계된 것들로 HTTP 메시지는 이미지, 비디오, HTML 문서, 소프트웨어 애플리케이션, 신용카드 트랜잭션, 전자우편 등 여러 종류의 디지털 데이터를 실어 나를 수 있다.