개발옹

Spring Boot 프로젝트를 하던중에 Security 관련 공부를 하면서 csrf 설정을 해야한다는 것을 보고, csrf가 궁금해져서 알아보게 되었습니다. 그리고 비슷한 개념인 XSS에 대해서도 살짝 맛보도록 하겠습니다.

1. CSRF(Cross-Site Request Forgery: 크로스 사이트 요청 위조)

CSRF는 Cross-Site Request Forgery의 약자로, 번역하면 사이트 간 요청 위조를 의미합니다.

CSRF는 웹사이트의 취약점을 이용하여 사용자의 의지와 무관하게 공격자가 의도한 행위(데이터 삭제, 수정, 등록 등)을 특정 웹사이트에 요청하게 하는 공격입니다.

생성된 요청이 인증된 사용자의 동의를 받았는지 확인할 수 없는 웹 애플리케이션의 CSRF 취약점을 이용하는 것입니다.

• 사용자가 인증한 세션에서 웹 애플리케이션이 정상적인 요청과 비정상적인 요청을 구분하지 못하는 점을 악용하는 공격 방식

공격자의 요청이 사용자의 요청인 것처럼 속여서 공격하는 방식이기에 '크로스 사이트 요청 위조'라는 명칭이 붙었습니다.

CSRF 공격 시나리오

CSRF 공격의 시나리오는 아래와 같습니다.

1️⃣ 사용자가 웹사이트에 접속해서 로그인하여 권한을 인증하고 세션을 생성합니다.

2️⃣ 공격자는 악성 웹사이트로 사용자를 유인합니다. 사용자가 이 링크를 클릭하면 공격자의 악성 웹사이트로 이동하게 됩니다.

3️⃣ 사용자가 악성 웹사이트에 방문하면, 해당 페이지에 포함된 스크립트나 이미지 태그가 사용자가 로그인한 웹사이트에 요청을 자동으로 전송합니다.

• 예를 들어, 은행 사이트라고 할 때, 공격자가 이미지 태그로 돈을 송금하는 요청을 보낸다고 해봅시다.

< img  src = "http://bank.com/transfer?amount=9999&toAccount=000011112222" />

해당 이미지 태그를 악성 웹사이트에 심어두면 사용자가 접속시 브라우저가 이 이미지를 로드하기 때문에, 해당 은행 웹사이트로 돈 송금 요청이 보내지게 됩니다.

4️⃣ 사용자는 웹사이트에 이미 인증을 한 상태이므로, 해당 요청은 서버에서 사용자의 정상적인 요청으로 판단하고 인증된 요청으로 처리합니다.

5️⃣ 서버는 이 악의적인 요청을 처리하여 사용자가 의도하지 않은, 공격자가 의도한 요청을 수행하게 됩니다.

• 예시로 보면, 사용자는 의도하지 않은 요청인, '000011112222' 계좌로 9,999원을 송금하게 됩니다.

CSRF 공격 사례

CSRF는 데이터 값을 변경하는 요청을 대상으로 합니다.

그러한 요청으로는 제품을 구입하거나 계정 설정, 기록을 삭제하거나 비밀번호를 변경하는 등의 요청이 있습니다. 

실제로 2008년에 옥션이 중국인 해커에게 CSRF 공격 방식으로 회원정보가 유출된 사례가 있습니다.

해커는 권한을 가지고 회사 내 작업을 하던 옥션 관리자에게 메일을 보냈고, 관리자는 이 메일을 조회했습니다. 

해커가 보낸 메일에는 태그가 들어간 코드가 포함되어 있었습니다. 

< img  src = "http://auction.com/changeUserAccount?id=admin&password=admin"  너비 = "0"  높이 = "0" >

(이미지 크기가 0이므로 관리자는 이 존재를 알지 못합니다.)

관리자가 메일을 조회하는 순간 이미지 파일을 받아오기 위해 URL이 열리게 되고, 해커가 원하는대로 관리자의 계정이 해커가 설정한 "admin"으로 변경됩니다. 이후 해커는 이 계정으로 서버 관리자 페이지에 접속해서 *백도어 프로그램을 올렸습니다.

*백도어 프로그램: 정상적인 절차를 거치지 않고도 접근을 가능하게 해주는 프로그램

백도어 프로그램을 이용해서 옥션 내부 웹 서버에 접속해 데이터베이스를 해킹했고, 회원 정보를 빼내간 것입니다.

이때 유출된 회원 정보가 1860만명이라고 합니다.

이러한 CSRF 공격에 당하게 되면 막대한 피해가 발생할 수 있습니다. 그렇기 때문에 웹 애플리케이션은 CSRF 공격을 방지하기 위해 CSRF 토큰을 통해 해당 요청이 인증된 사용자가 전송한 것이 맞는지를 확인하거나 재인증을 요구하는 등의 방식으로 CSRF 공격을 방지해야합니다.

2. CSRF 공격 방지 - Synchronizer Token Pattern

Spring에서는 CSRF 공격을 방지하기 위한 메커니즘 중 Synchronizer Token Pattern을 가장 우세하고 포괄적인 방법으로 소개하고 있습니다. Synchronizer Token Pattern은 CSRF 공격으로부터 애플리케이션을 보호하기 위해 서버와 클라이언트 간에 고유한 보안 토큰인 CSRF 토큰을 사용하는 방법입니다.

🔐 CSRF 토큰

사용자가 인증을 하더라도 CSRF 공격이 가능하기 때문에 보통 JWT만을 이용하여 사용자를 인증한다하였을때에도 공격을 받을 수 있습니다. 그래서 CSRF 토큰을 사용해서 CSRF 공격을 방지합니다.

CSRF 토큰이란, 서버에 들어온 요청이 실제 서버에서 허용한 요청이 맞는지를 확인하기 위한 토큰입니다.

CSRF 토큰은 서버에서 생성해서 클라이언트와 공유되는 인증 값입니다. 클라이언트는 서버에 요청시에 서버에서 인증해준 CSRF 토큰을 포함해서 요청해야합니다. CSRF 토큰이 없으면 서버는 요청을 거부하게 됩니다. 

CSRF 토큰을 HTML 폼에 담아서 보내는 방식이 일반적으로 사용되는 방식입니다.

1️⃣ 클라이언트는 애플리케이션 서버에 HTTP GET 요청을 통해 액세스합니다.

2️⃣ 서버는 CSRF 토큰을 생성하고 HTTP 세션에 저장합니다. 생성된 CSRF 토큰은 HTML 형식의 숨겨진 태그(hidden)를 사용하여 클라이언트와 연결됩니다.

3️⃣ 클라이언트는 HTML 폼의 버튼을 통해 애플리케이션 서버에 요청을 보냅니다. CSRF 토큰은 HTML 폼의 Hidden 필드에 포함되어 있으므로 CSRF 토큰 값이 요청 매개변수로 함께 전송됩니다. 

4️⃣ 서버는 요청 파라미터에 지정된 CSRF 토큰 값과 HTTP POST 메서드를 사용하여 액세스 할 때 HTTP 세션에 유지된 CSRF 토큰 값이 동일한지 확인합니다. 토큰 값이 일치하지 않으면 잘못된 요청으로, 오류가 발생합니다.

다시 정리하자면, 아래와 같습니다.

• 로그인한 사용자가 페이지에 접속시 서버에서는 CSRF 토큰을 생성해서 사용자 세션이 저장합니다.
• 이후 사용자가 서버에 애플맄이션의 상태를 변경하는 작업을 요청할 때 페이지에 Hidden 으로 숨어있는 CSRF 토큰 값이 서버로 전송됩니다. 
• 서버에서는 이 CSRF 값이 세션에 저장된 값과 일치하는지 확인하여 해당 요청이 정상적인 요청임을 확인할 수 있습니다. 

CSRF 토큰 유의사항

[CSRF 토큰의 위치]

• HTML 폼 제출시 hidden 필드로 포함시켜서 전송해야합니다.
• AJAX 요청을 보낼시에는 CSRF 토큰을 Custom Header 값으로 포함시키거나 JSON payload(데이터)로 전송할 수 있습니다.
• CSRF 토큰을 쿠키에 포함시켜서 전송하면 안됩니다.
  
  • CSRF 토큰은 실제 사용자가 요청한 정상적인 작업인지를 검증해야하는데, 쿠키는 브라우저에 의해 자동으로 HTTP 요청에 포함되므로, 정상적인 요청인지 검증할 수 없게 됩니다.
  • '자동 전송'이라는 기능때문에 공격자가 만든 요청이여도 쿠키가 자동으로 포함되어 서버에 전송됩니다. 이로인해 서버는 이 요청이 정상적인 요청이라고 착각하여 요청을 수행할 수도 있습니다.
  • 따라서 CSRF 토큰은 사용자가 직접 제어할 수 있는 방식으로 전송되어야 합니다.
• CSRF 토큰은 서버 로그나 URL에 노출되어서는 안됩니다.

[HTTP 요청에 따른 요구사항]

• 애플리케이션의 상태를 변경하는 요청에 대해서만 CSRF를 요청해도 괜찮습니다. (POST, PUT, PATCH, DELETE)
  • 단, 이를 위해서는 상태가 변경되지 않는(=멱등 요청)요청(GET, HEAD, OPTIONS, 및 TRACE)이 오직 읽기 전용(read-only) 작업만 수행하도록 보장해야합니다.
• HTTP GET(상태가 변경되지 않는 안전한 요청)에는 CSRF 토큰을 포함시키지 않아야합니다.
  • GET 요청은 캐시되거나 URL로 노출될 수 있기 때문에 CSRF 토큰이 유출될 수도 있습니다.
  • 토큰이 유출되면 공격자가 이 토큰을 재사용하여 CSRF 공격을 시도할 수도 있습니다.

3. CSRF vs XSS

CSRF와 XSS는 모두 웹 애플리케이션에서의 공격 유형이지만, 차이점이 있습니다.

먼저 XSS가 무엇인지 간단하게 짚고 넘어가겠습니다.

XSS(Cross-Site Scripting)

XSS는 Cross-Site Scripting의 약자로, 번역하면 사이트 간 스크립팅 입니다.

XSS 공격은 공격자가 웹 페이지에 악의적인 스크립트를 삽입하여, 사용자의 브라우저에서 실행시키는 공격입니다. 

이로인해 사용자는 의도하지 않은 동작을 수행하거나, 공격자에게 쿠키, 세션 등의 정보를 탈취 당하게 됩니다.

XSS는 SQL Injection과 함께 웹 상에서 가장 기초적인 취약점 공격 방법 중 하나입니다.

XSS 공격 대응 방안

• 중요 정보는 쿠키 대신 서버에 저장합니다.
• 정보를 암호화 합니다.
• httpOnly 옵션을 설정합니다.
  • document.cookie를 이용해 쿠키에 직접 접근하는 것을 방지
• URL Encoding이나 문자열을 치환합니다.

CSRF 와 XSS 의 차이

[공격 대상]

• CSRF 공격 대상은 "Server"이고 XSS 공격 대상은 "Client"입니다.
• CSRF는 특정 웹 사이트가 사용자의 웹 브라우저를 신뢰하는 상태를 노린 것이고, XSS는 사용자가 특정 웹 사이트를 신뢰하는 점을 노린 것입니다.

[공격 방식]

• CSRF는 공격자가 사용자의 브라우저를 속여 의도하지 않은 요청을 특정 웹사이트로 보내도록 유도합니다. 사용자의 권한을 이용해 서버에 대한 악성 공격을을 하게 하는 것입니다. 
• XSS는 공격자가 악성 스크립트를 웹페이지에 삽입하여 해당 페이지를 방문하는 사용자의 브라우저에서 스크립트가 실행되게 합니다. 스크립트는 사용자의 브라우저에서 실행되므로 사용자의 권한으로 민감한 데이터를 탈취하거나 임의의 명령을 실행할 수 있습니다.

CSRF 공격

1️⃣ 공격자자 웹 사이트에 자금 이체 요청을 위조합니다.

2️⃣ 공격자는 그 요청을 하이퍼링크(스크립트)에 삽입하여 웹 사이트에 로그인 할 사용자에게 전송합니다.

3️⃣ 사용자가 그 링크를 클릭하면, 사용자도 모르게 웹 사이트에 요청을 전송하게 됩니다.

4️⃣ 웹 사이트의 서버는 로그인 된 사용자의 요청이기 때문에 정상으로 판단하고, 사용자의 계정에서 공격자의 계정으로 자금을 이체합니다.

XSS 공격

1️⃣ 공격자가 스크립트 주입이 가능한 취약점이 있는 웹 사이트를 찾습니다.

2️⃣ 취약점을 찾아 세션 쿠키를 탈취하는 악성 스크립트를 사이트에 삽입합니다.

3️⃣ 사용자가 웹 사이트를 방문할 때마다 스크립트가 작동됩니다.

4️⃣ 작동된 스크립트를 통해 사용자의 세션 쿠키를 탈취합니다.

Reference

1. 모노톤 스택(Monotone stack) 이란?

스택(Stack)은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 후입선출(LIFO:Last In, First Out) 형태의 자료구조 입니다.
즉, 가장 먼저 들어온 데이터가 가장 마지막에 나가고, 마지막에 들어온 데이터가 가장 먼저 나가는 구조입니다.

• 모노톤 스택(Monotone stack)은 특정한 순서를 유지하면서 데이터를 관리하는 스택 자료구조 입니다.
  • Monotone은 증가하거나 감소하는 등의 일정한 경향이 보임을 의미합니다.
• 모노톤 스택(Monotone stack)은 증가하거나 감소하는 일정한 경향을 가진 스택입니다.
• 모노톤 스택(Monotone stack)은 특정 문제에 대해 시간 복잡도를 O(N)으로 줄여주는 매우 효율적인 해결책을 제공합니다.
  • 다음/이전 데이터의 최댓값/최솟값을(Nearest Greater/Smaller Element) 찾는 문제에 유용하게 쓰입니다.

2. 모노톤 스택(Monotone stack)의 종류 및 구현

스택은 LIFO(Last In, First Out) 자료 구조이기 때문에 모노톤 스택의 최상위 요소를 제거하면서 단조 증가/감소 순서를 유지합니다. 새로운 요소는 항상 최상위에 추가됩니다.

1) 단조 증가 스택(Monotone Increasing Stack)

• 스택의 요소들이 오름차순으로 정렬되는 스택
  • 오름차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 커진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 내려갈수록 값이 작아짐

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 크거나 같은 경우를 유지하는 스택
  
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 작거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 항상 특정 순서(오름차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

2) 단조 감소 스택(Monotone Decreasing Stack)

• 스택의 요소들이 내림차순으로 정렬되는 스택
  • 내림차순을 유지한다는 것은 스택의 아래쪽부터 위쪽으로 올라갈수록 값이 작아진다는 의미
  • 스택의 최상위에서부터 시작하여 아래로 갈수록 값이 커짐

• 스택의 맨 위에 있는 요소가 항상 그 아래에 있는 요소보다 작거나 같은 경우를 유지하는 스택
  • 스택에 새로운 요소를 추가할 때, 그 요소가 스택의 최상위 요소보다 크거나 같을 때까지 기존 요소를 제거
  • 이때, 단조성을 유지해야합니다. (스택에 있는 요소들이 특정 순서(내림차순)를 유지)
  • 중복 값 허용 여부에 따라 값이 같은 경우에 대한 제거 여부를 정하면 됩니다.

Deque<Integer> stack = new ArrayDeque<>();
for (int i=0; i<arr.length; i++) {
    // 스택의 최상위 요소가 현재 값보다 작거나 같으면 pop();
    while (!stack.isEmpty() && stack.peekFirst() <= arr[i]) {
    	stack.removeFirst();
    }
    // 스택의 최상위 요소보다 클 때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
    stack.offerFirst(arr[i]);
}

3. 모노톤 스택(Monotone stack) 구현 - 예시로 확인

개인적으로 모노톤 스택의 종류에 대해 이해하는데에 조금 시간이 걸렸습니다. 단조 증가 스택과 단조 감소 스택의 정렬 순서가 어디부터 시작하는지에 대한 정확한 이해를 못하고 무작정 이해하려고 하다보니 헷갈렸습니다. 

그래서 마지막으로 배열 예시를 정리하면서 아직은 조금 헷갈리는 부분을 정리해보겠습니다.

public static void main(String[] args) {
    int[][] testArrays = {
        {1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
        {10, 9, 8, 7, 6, 5, 4, 3, 2, 1},
        {5, 5, 4, 4, 3, 3, 2, 2, 1, 1},
        {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}
    };

    for (int[] arr : testArrays) {
        System.out.println("Monotonic Stack for array: " + Arrays.toString(arr));
        incresing(arr);
        decresing(arr);
        System.out.println();
    }
}

테스트 배열을 위와 같이 4가지 정도로 생성해두고 단조 증가 스택과 단조 감소 스택을 출력해보았습니다.

*각 스택은 2번 목차의 코드를 수행해서 생성

위 코드에 대한 출력 결과는 아래와 같습니다.

Monotonic Stack for array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Monotonic Increasing Stack: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
Monotonic Decreasing Stack: 10, 

Monotonic Stack for array: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 
Monotonic Decreasing Stack: 1, 2, 3, 4, 5, 

Monotonic Stack for array: [3, 6, 1, 9, 4, 7, 2, 8, 5, 10]
Monotonic Increasing Stack: 10, 5, 2, 1, 
Monotonic Decreasing Stack: 10,

단조 증가 스택은 요소들이 오름차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

단조 감소 스택은 요소들이 내림차순(스택의 아래부터 최상위까지)으로 정렬되어 있는 스택

인 점을 머리속에 꼭 담아두고 출력 결과를 확인해보면, 제대로 출력되는 것을 알 수 있습니다.

코드 구현시 중복 값은 허용하지 않았기 때문에 3번 예시처럼 중복 값이 없는 것을 확인할 수 있습니다.

만약 중복을 허용한다면 아래와 같은 결과가 출력됩니다.

Monotonic Stack for array: [5, 5, 4, 4, 3, 3, 2, 2, 1, 1]
Monotonic Increasing Stack: 1, 1, 
Monotonic Decreasing Stack: 1, 1, 2, 2, 3, 3, 4, 4, 5, 5,

단조 증가 스택 함수는 아래와 같을때 마지막 예시인 {3, 6, 1, 9, 4, 7, 2, 8, 5, 10} 에 대한 단조 증가 스택 생성 과정을 구체적으로 보겠습니다.

public static void incresing(int[] arr) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i=0; i<arr.length; i++) {
        // 스택의 최상위 요소가 현재 값보다 크거나 같으면 pop();
        while (!stack.isEmpty() && stack.peekFirst() >= arr[i]) {
        	stack.removeFirst();
        }
        // 스택의 최상위 요소보다 작을때까지 기존 요소를 제거하고, 현재 요소 스택에 추가
        stack.offerFirst(arr[i]);
    }
}

• 배열: {3, 6, 1, 9, 4, 7, 2, 8, 5, 10}

최종적으로 스택을 출력하면 [10, 5, 2, 1] 이 출력됩니다.

스택의 맨 위 요소가 현재 배열 요소보다 크거나 같으면 스택에서 제거하고, 현재 요소를 스택에 추가하면서 단조성을 유지할 수 있는 것입니다.

4. 모노톤 스택(Monotone stack) 관련 문제

• 백준 - 탑 보기

참고 링크

지난번에 트라이를 공부하고 포스팅으로 정리했는데, 아래 포스팅에서는 Map Interface로 구현을 했었습니다.

그런데 백준 - 전설(19585)을 트라이 자료구조로 풀어도 시간 초과가 나길래 더 찾아보니 Array로 구현하는 방식도 있어서 이번에는 Array 방식으로 구현한 트라이도 추가했습니다.

트라이(Trie)란?

트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조로, 자세한건 지난번 포스팅을 참고해주세요.

트라이(Trie) 구현 방식

트라이(Trie)는 두 가지 방식으로 구현할 수 있습니다.

1. Array를 이용하여 구현
2. Map Interface를 이용하여 구현

Array로 구현할 경우, 빠른 저장과 탐색을 할 수 있다는 장점이 있지만 필요한 메모리의 크기가 너무 크다는 것이 단점입니다.

Map Interface로 구현할 경우, 메모리를 동적으로 할당하여 필요 노드만 메모리를 할당할 수 있다는 장점이 있지만 메모리 제한이 있는 경우 최적화 작업이 꽤 까다롭다는 단점이 있습니다.

1. Array로 구현

Array로 구현할 경우, Trie의 Node별 자식 노드를 Node형 배열로 구현합니다. 

이때, Trie Node에 들어가는 단어는 영어 소문자만 있다고 가정하며, 각 노드는 영어 소문자를 정수형(int)으로 변환하여 인덱스로 사용합니다.

* 자세한 설명은 이전 포스팅을 참고해주세요.

Node 클래스 생성

Map으로 구현한 Trie 의 Node와 다르게 자식 노드를 Node[] 로 초기화합니다.

childNode의 인덱스에 영어 소문자를 정수형(int)로 변환한 값이 들어가게 됩니다.

그리고 자식 노드의 수(childCnt)와 해당 노드의 문자(val)도 저장해줍니다.

static final int SIZE = 26; // 영어 소문자는 26자
private class Node {
    Node[] childNode = new Node[SIZE]; // 자식 노드: 영어 소문자를 인덱스화 하여 저장
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
    int childCnt = 0; // 자식 노드 수
    char val; // 노드의 문자
}

트라이(Trie) 자료구조 클래스 생성

public class TrieArray {
    private Node rootNode;
    public TrieArray() {
    	rootNode = new Node();
    }
}

기본 메서드

1) 노드 추가(insert)

문자열의 문자를 순회하면서 해당 문자가 자식노드로 있는지 확인하여 노드를 추가하는 메서드입니다. 

Map으로 구현했을때와는 다르게 현 노드의 자식 노드가 null 이 아닌지, 즉, 생성되어있는지를 확인하여, 없다면 생성합니다. 

생성시에는 자식 노드를 추가하고, 자식 노드의 문자를 할당해주고, 현 노드의 자식 노드 수를 증가시킵니다.

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드 확인
    for (int i=0; i < word.length(); i++) {
        char c = word.charAt(i);
        // 단어의 특정 문자를 인덱스(int)로 변환
        int intVal = charToInt(c);
        // 현 노드에 인덱스로 변환한 문자가 자식노드로 있는지 확인
        if (node.childNode[intVal] == null) {
            // 자식 노드에 없는 문자라면 새로 생성
            node.childNode[intVal] = new Node();
            node.childNode[intVal].val = c;
            node.childCnt++;
        }
        // 다음 탐색 노드를 자식노드로 변경
        node = node.childNode[intVal];
    }
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

2) 포함 여부 확인(contains)

문자열이 트라이에 있는지 확인하는 메서드로, 배열 방식에 맞게 구현해주면 됩니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        int intVal = charToInt(c); // 문자를 인덱스로 변환
        if (node.childNode[intVal] == null) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode[intVal];
    }
    return node != null && node.endOfWord; // 마지막 문자 여부를 반환
}

3) 노드 삭제(delete)

트라이에 존재하는 문자열을 삭제하는 메서드로, 삭제 조건에 맞춰 배열 방식에 맞게 구현해주면 됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
public void delete(Node node, String word, int idx) {
    // 단어의 마지막인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    } else {
        if (node.childCnt == 0) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    }

    char c = word.charAt(idx); // 현재 확인해야하는 문자
    int intVal = charToInt(c); // 문자를 인덱스로 변환

    Node child = node.childNode[intVal]; // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 삭제되었다면, 현 노드의 자식 노드 수 1 차감
    if (node.childNode[intVal] == null) node.childCnt--;
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childCnt == 0 && !node.endOfWord) node = null;
}

🧪 구현 테스트

구현 테스트는 Map 방식과 동일하니, 해당 포스팅을 참고해주세요 :)

💡 전체 코드(Array로 구현)는 아래 링크에서 확인해주세요.

2. Map Interface로 구현

아래 코드는 Map Interface로 구현한 코드이며, 자세한 설명은 이전 포스팅을 참고해주세요.

💡 Trie를 Map, Array로 구현한 코드는 아래 링크에서 확인해주세요.

Reference

1. 트라이(Trie)란?

원하는 요소를 찾기위해 자주 사용되는 이진 검색 트리 등에서는 타겟 요소를 찾는데에 O(logN)의 시간이 걸립니다.
하지만 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에,
원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸립니다.
따라서 이 작업을 여러번 수행한다면 시간이 오래 걸리게 됩니다. 
이러한 문자열 검색시의 단점을 해결하기 위해 나온 자료구조가 트라이(Trie)입니다.

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 구글이나 네이버 등에 검색어를 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 합니다.
• 래딕스 트리(Radix Tree)나 접두사 트리(Prefix Tree), 탐색 트리(Retrieval Tree)라고도 합니다
  • 트라이(Trie)는 Retrieval Tree에서 나온 단어

예를 들어 'Tistory'라는 단어를 검색하기 위해 제일 먼저 'T'를 찾고, 다음에 'i', 's', 't', ... 의 순대로 찾으면 됩니다.

이런 개념을 적용한 자료구조가 트라이(Trie)입니다.

2. 트라이(Trie)의 작동 원리

다음 그림은 문자열 집합 {"apple", "app", "dad", "dream", "age"}를 트라이로 구현한 것입니다.

*트라이(Trie)는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리입니다.

[공통 접두어]

"apple"과 "app"은 "app"라는 공통 접두어가 있으므로 같은 서브 트리에 표시됩니다.

즉, "a"라는 공통 접두어를 가진 "apple", "app", "age"는 Head의 자식 노드 'a'에,

"d"라는 공통 접두어를 가진 "dad", "dream"은 Head의 자식 노드 'd'에 표시됩니다.

[Leaf Node]

리프 노드는 각 단어의 마지막 문자를 의미하므로, 단어의 끝 문자라는 표시(endOfWord)를 해야합니다.

또한 리프 노드의 개수는 단어의 개수를 의미합니다.

[트라이(Trie) 생성 과정]

1. "apple"를 트라이에 삽입

• 'a': 첫번째 문자인 'a'는 초기에 트라이 자료구조 내에 아무것도 없으므로 Head의 자식노드에 'a'를 추가
• 'p': 'a' 노드에도 현재 자식이 하나도 없으므로 'a'의 자식노드에 'p'를 추가
• 'p', 'l', 'e'에 대해서도 자식노드로 추가
• 'l': "apple" 단어가 끝남을 알기 위해 'l' 노드에 마지막 노드(endOfWord)임을 표시

2. "app"를 트라이에 삽입

• 'a': 현재 Head의 자식 노드로 'a'가 이미 존재하기 때문에 'a' 노드를 추가하지 않고 기존에 있는 'a'노드로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동
• 'p': 'p'도 'a'의 자식 노드로 있으므로 'p'로 이동하면서, 'p'노드에 마지막 노드임을 표시

3. "dad", "dream",  "age"를 트라이에 삽입

• "dad"와 "dream"의 첫 문자인 'd'는 Head의 자식 노드로 없기 때문에 추가해서, 각 단어별로 문자를 순차적으로 추가
• "age"는 Head의 자식 노드로 'a'가 있기 때문에,
  • 'a'로 이동 => 'a'의 자식 노드에 'g'가 없으므로 'g'를 추가 => 'e'도 'g'의 자식 노드로 추가한 후 마지막 노드 표시

3. 트라이(Trie) 구현(Java)

그럼 트라이를 Java로 구현하려면 어떻게 해야할까?

기본적으로는 Map Interface를 사용해서 구현합니다.

Map의 Key값에는 단어를 이루는 각각의 문자들이 들어가고, Value에는 자식 노드 클래스를 저장합니다.

이제 순차적으로 자바로 구현을 해보겠습니다.

Node 클래스 생성

Node 클래스는 해당 노드의 자식 노드정보와 단어의 끝인지를 판단하는 변수로 구성합니다.

private class Node {
    HashMap<Character, Node> childNode = new HashMap<>(); // 자식 노드
    boolean endOfWord; // 단어의 끝인지에 대한 플래그
}

트라이(Trie) 자료구조 클래스 생성

기본적으로 루트 노드를 초기화해 줍니다.

*루트 노드는 1) 항상 비어있고 2) 루트노드의 자식 노드는 각 단어의 첫 글자입니다.

public class Trie {
    private Node rootNode;
    Trie() {
        // Trie 생성시 루트 노드는 기본으로 생성
        rootNode = new Node(); // 루트 노드는 빈 노드
    }
}

기본 메서드

1) 노드 추가(insert)

입력 받은 단어를 문자 순대로 트리 계층 구조의 자식 노드로 생성해서 넣습니다.

• 문자가 자식 노드에 존재하면 새로 생성하지 않고 자식 노드로 이동
• 단어의 마지막 문자인 노드라면 endOfWord = true로 설정

public void insert(String word) {
    Node node = this.rootNode;
    // 단어의 문자를 순회하면서 자식 노드를 확인
    //  1) 자식 노드에 있는 문자라면 자식 노드를 가져옴
    //  2) 자식 노드에 없는 문자라면 새롭게 생성
    for (int i=0; i<word.length(); i++) node = node.childNode.computeIfAbsent(word.charAt(i), key -> new Node());
    node.endOfWord = true; // 단어(word)의 문자를 모두 순회하면 마지막 노드는 리프 노드(=마지막 문자)이기때문에 endOfWord를 true로 설정
}

2) 포함 여부 확인(contains)

특정 단어가 트라이에 존재하는지 확인합니다.

• 루트 노드부터 단어의 문자 순대로 일치하는 자식 노드가 계층을 이루고 있는지 확인
• 단어의 마지막 문자에 endOfWord가 true

두 조건을 만족하는 경우가 트라이에 존재하는 경우입니다.

public boolean contains(String word) {
    Node node = this.rootNode;
    char c;
    for (int i=0; i<word.length(); i++) {
        c = word.charAt(i);
        if (!node.childNode.containsKey(c)) return false; // 현재 탐색하는 문자가 자식 노드에 없다면 존재하지 않는 단어
        node = node.childNode.get(c); // 마지막 문자를 node에 저장
    }
    return node.endOfWord; // 마지막 문자 여부를 반환
}

3) 노드 삭제(delete)

트라이에 추가했던 단어를 삭제합니다.

• 부모 노드에 대한 정보는 없기 때문에 삭제할 단어의 마지막 문자까지 이동해서 문자를 삭제해와야 합니다. => 재귀
• 다음 문자에 존재하는 자식노드가 있고, 삭제를 시작하는 마지막 노드(리프 노드)에는 endOfWord가 true로 되어있어야 합니다. 
  • 즉, 삭제할 단어가 트라이에 포함되어있어야 합니다.
• 단어 삭제를 위해 마지막 문자 노드인 리프 노드의 endOfWord를 false로 변경합니다. 이후 순차적으로 거꾸로 올라가면서 노드를 삭제합니다. 단, 아래 두 조건이 아닌 경우에만 삭제합니다.
  • 해당 노드의 자식노드가 있는 경우
    • 자식노드가 있다는 뜻은 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.
  • endOfWord가 true인 경우
    • 단어의 끝인 문자인 경우 다른 단어에 사용되는 문자라는 뜻이므로 삭제하면 안됩니다.

public void delete(String word) {
    delete(this.rootNode, word, 0);
}
// 재귀 호출을 위한 함수 오버로딩
private void delete(Node node, String word, int idx) {
    // 단어의 마지막 인덱스인 경우
    if (idx == word.length()) {
        if (!node.endOfWord) throw new Error(word + " not exist"); // 단어가 존재하지 않음
        node.endOfWord = false; // 단어의 끝 문자 표시를 false로 변경: 해당 문자 노드를 삭제하기 위함
        return; // 리프 노드의 부모 노드로 return
    }
    char c = word.charAt(idx); // 현재 확인해야하는 문자
    if (!node.childNode.containsKey(c)) throw new Error(word + " not exist"); // 자식 노드가 없는 경우(=단어가 존재하지 않는 경우)
    Node child = node.childNode.get(c); // 자식 노드 가져오기
    // 자식 노드가 있다면 리프 노드까지 내려가야 하므로 재귀 호출
    delete(child, word, idx+1);
    // 현 노드의 자식 노드가 리프 노드이고(=자식 노드가 없음), 단어의 끝인 문자가 아니라면 삭제
    if (child.childNode.isEmpty() && !child.endOfWord) node.childNode.remove(c, child);
}

🧪 구현 테스트

public static void main(String[] args) {
        Trie trie = new Trie();
        // insert
        String[] arr = {"apple", "app", "dream", "dad", "age"};
        for (String word: arr) {
            trie.insert(word);
        }
        // delete
        trie.delete("app");
        trie.delete("dream");
        // contains
        System.out.println(trie.contains("apple")); // true
        System.out.println(trie.contains("app")); // 삭제했으므로 false
        System.out.println(trie.contains("age")); // true
        System.out.println(trie.contains("dream")); // 삭제했으므로 false
        System.out.println(trie.contains("dad")); // true
}

위에서 예시로 들었던 문자열 배열을 기준으로 트라이를 생성하고 삭제, 포함여부를 확인하면 아래와 같은 결과를 확인할 수 있습니다.

💡 전체 코드는 아래 링크에서 확인해주세요.

4. 트라이(Trie) 시간 복잡도

총 문자의 개수를 N, 가장 긴 문자열의 길이가 L이라고 할때

• 생성 시간 복잡도: O(N*L)
  • 모든 문자열 N개를 넣어야하고, N개에 대해 트라이에 넣는 건 가장 긴 문자열 길이인 L만큼 걸린다.
  • 삽입은 O(L)만 소요
• 탐색 시간 복잡도: O(L)
  • 트리를 가장 깊게 탐색하는 경우는 가장 긴 문자열 길이인 L까지 들어가는 것이므로 O(L)

5. 트라이(Trie) 장단점

• 문자열에 대한 검색을 빠르게 할 수 있습니다.
  
  • 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나 추가하면 되기 때문에 문자열의 추가와 탐색 모두 O(M)만에 가능합니다.

• 필요로 하는 메모리의 크기가 너무 크다는 단점이 있습니다.
  • 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있기에 저장공간의 크기가 크다는 단점이 있습니다.
  • 문자열이 모두 영소문자로 이루어져 있어도, 자식 노드를 가리키는 26개의 포인터를 저정해야하는데
  • 최악의 경우에는 집합에 포함되는 문자열의 길이의 총 합만큼의 노드가 필요하기 때문에 총 메모리는 O(포인터 크기*포인터 배열 개수*총 노드 개수)가 됩니다.
    • 만약 1,000자리의 문자열이 1,000만개가 있다면 이때, 100만개의 노드가 필요하고 포인터의 크기가 8Byte라 하면 약 200MB의 메모리가 필요합니다.

트라이(Trie) 단점 해결을 위한 방법

'메모리의 크기가 너무 큰' 단점을 해결하기 위해, 보통 map이나 vector를 이용해서 필요한 노드만 메모리를 할당하는 방식을 사용합니다. 그러나 이는 메모리 제한이 타이트한 경우에는 최적화가 까다롭습니다.

또한 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것도 중요하다고 합니다.

6. 트라이(Trie) 코딩테스트 문제

• [백준] - 전설
• [백준] - 전화번호 목록 : 🔗풀이 포스팅

참고한 링크

• [자료구조] 트라이 (Trie)
• [Algorithm] Trie를 Java로 구현해보자!
• [자료구조] 트라이

네트워크를 공부하면 필수로 알아야하는 개념들에 대해 공부한 내용을 정리합니다.

네트워크(Network)

네트워크(Network)란 노드(Node)와 링크(Link)가 서로 연결되어 있으며 리소스를 공유하는 집합을 의미합니다.

• 노드: 서버, 라우터, 스위치 등의 네트워크 장치
• 링크(=Edge): 유선 또는 무선과 같은 연결매체로, 와이파이나 LAN

트래픽(Traffic)

트래픽(Traffic)은 특정 시점에 링크 내에 흐르는 데이터의 양, 서버를 통해 최종 사용자에게 전달된 데이터의 양을 의미합니다.

• ex. 서버에 저장된 파일(문서, 이미지 등)을 클라이언트(사용자)가 다운로드시 발생되는 데이터의 누적량
• 단위: bps(bits per seconds)

트래픽 계산

트래픽 = 용량 * 사용자 수

Q. 4GB 영화를 10명이 다운로드 받을때의 트래픽은?

• 4GB * 10명 = 40GB

처리량(Throughput)

처리량(Throughput)은 링크 내에서 성공적으로 전달된 데이터의 양을 의미합니다.

보통 트래픽 처리량을 나타내며, 많은 트래픽을 처리한다 = 많은 처리량을 가진다는 의미와 같습니다.

• 단위: bps(bits per seconds) 초당 전송 또는 수신되는 비트수

처리량은 사용자들이 많이 접속할때마다 커지는 트래픽, 네트워크 장치간의 대역폭, 네트워크 중간에 발생하는 에러, 장치의 하드웨어 스펙에 영향을 받습니다.

💡 트래픽과 처리량은 헷갈릴 수 있기 때문에 이렇게 이해하면 됩니다.

• "트래픽이 많아졌다" = 흐르는 데이터가 많아졌다.
• "처리량이 많아졌다" = 처리되는 트래픽이 많아졌다.

대역폭(Bandwidth)

대역폭(Bandwidth)은 주어진 시간 동안 네트워크 연결을 통해 흐를 수 있는 최대 비트수이며, 최대로 처리할 수 있는 트래픽을 의미합니다.

• 대역폭이 높을수록 사용자에게 빠른 서비스를 제공
  • ex. 고속도로의 차선이 2차선일때보다 8차선일 때 더욱 원활한 교통이 이루어짐
• 대략적인 최대 동시 접속자 수를 유추하는 척도
• 단위: bps(bits per seconds) 초당 전송 또는 수신되는 비트수 (초당 bit단위의 데이터 처리량)

대역폭 계산

대역폭(bps) = (용량 * 사용자수 * 8bits) / 처리시간

• bps 계산식 = 데이터크기(bits 단위) / 소요시간(초 단위)
• * 8bits는 Byte에서 bit(대역폭의 단위는 bps이기 때문)로 변환하기 위한 값 

Q1. 20,000명이 홈페이지에 접속할때 접속시마다 4MB의 용량을 다운로드 받아야하고, 이 요청이 10분내에 완료되어야 할 때, 대역폭은?

• 트래픽 =  (20,000명 * 4MB * 1개) = 80,000MB
• 대역폭 = (20,000 * 4MB * 8 = 640,000) /  (10분 * 60초 ) =1066Mbps = 1.066Gbps = 약 1Gbps의 대역폭 필요

Q2. 100Mbps 대역폭의 서버로 한 사용자당 100kbps로 동영상 파일을 요청할때, 최대 동접자수는?

• 100Mbps / 100kbps = 약 1,000명

트래픽 vs 처리량 vs 대역폭

트래픽은 흐르려는, 이동하려는 데이터 양을 의미하며, 이 트래픽을 처리할 때를 기준으로 생각하면 처리량과 대역폭을 쉽게 구분할 수 있습니다.

• 대역폭 : 네트워크의 '도로 폭'과 같으며, 이 '도로'를 통해 한 번에 얼마나 많은 데이터(트래픽)가 이동할 수 있는지를 나타냅니다.
• 처리량 : 특정 시점에서 '도로'를 통과하는 차량의 수에 해당하며, 다양한 요인에 의해 영향을 받을 수 있습니다. (네트워크 혼잡, 하드웨어 제한 등과 같은 외부 요인)

참고 강의 및 사이트

• [NETWORK] 대역폭(Bandwidth)이란?
• CS 지식의 정석 - 인프런

백엔드 웹개발자로 일을 하다가 신입 공채시장에 뛰어들게 되면서 전공지식을 더 공부해야겠다는 생각을 한 후 공부를 시작했어요. 

직접 필기하면서 공부하는 것도 도움이 많이 되지만, 매번 찾아봤던걸 다시 검색하는게 시간이 더 들길래 정리했습니다.

나중에 확인할 용도이긴 하지만, 혹시 잘못된 부분이 있다면 댓글로 알려주시면 감사드리겠습니다 🙇🏻

*공부하면서 계속 추가할 예정입니다.

🧑‍🏫 강의

• CS 지식의 정석 - 인프런
• 개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제