제일 왼쪽부터 0층,1층,2층이라고 하겠음 (*3층으로 보이지만 가중치를 갖는 층은 2개뿐이기에 2층 신경망임)

신경망 신호 전달 방법을 보기 전에 퍼셉트론을 살짝 복습해보자

3-2를 보면 편향을 나타내질 않고있음. 편향을 명시하면 아래와 같이 나타낼 수 있다

조건 분기 동작을 하나의 함수로 표현 (0을 넘으면 1출력, 그렇지 않으면 0출력) -> h(x)

h(x)처럼 입력신호의 총합을 출력신호로 변환하는 함수를 활성화함수라고함 입력신호의 총합이 활성화를 일으키는지를 정하는 역할을 한다.

3-2의 식을 다시 써보면, 가중치가 곱해진 입력신호의 총합을 계산하고 그 합을 활성화 함수에 입력해서 다시 결과를 내는 2단계로 처리가 된다. 이식을 다시 나타내면 아래와 같이 나타낼 수 있음. 가중치 신호를 조합한 결과가 a라는 노드가 되고 활성화함수를 통과하여 y라는 노드로 변환되는 과정임

활성화함수는 임곗값을 경계로 출력이 바뀌는데, 이런 함수를 계단 함수라고 함 그래서 퍼셉트론에서는 활성화함수로 계단함수를 이용한다. 라고 할 수 있음 즉, 활성화함수로 쓸 수 있는 여러 후보 중에서 퍼셉트론을 계단 함수를 채용하고 있다. 계단 함수 이외의 함수를 사용하면 어떻게 될까 -> 활성화 함수를 계단 함수에서 다른 함수로 변경하는 작업이 신경망의 세계로 나아가는 열쇠임 ( ? ) (긍까 퍼셉트론에서는 활성화함수로 계단함수를 사용함. 그래서 출력이 0,1로만 나오게되는데 가중치를 자동으로.....학습하게 하려면 계단 함수가 아닌 다른 활성화 함수가 필요하다 이말인가?)

시그모이드 함수

신경망에서는 활성화함수로 시그모이드 함수를 이용하여 신호를 변환하고 그 변환된 신호를 다음 뉴런에 전달한다.

계단 함수를 그래프로 그리기

시그모이드 함수를 그래프로 그리기

시그모이드 함수와 계단 함수 비교

차이점 - 시그모이드 함수는 입력에 따라 출력이 연속적으로 변화, 계단함수는 0을 경계로 갑자기 바뀌어 버림 -> 시그모이드의 이 매끄러움이 신경망 학습에서 아주 중요한 역할을 하게 된다 공통점 - 입력이 아무리 작거나 커도 출력은 0, 1 사이

또 다른 공통점은 둘 다 비선형 함수라는 것이다.

활성화 함수로 선형함수를 안쓰는이유?

다층 퍼셉트론을 사용하는 이유가 단층으로 표현할 수 없는 것을 표현하기 위함인데, 단층으로 왜 표현을 못하냐? 직선으로 표현이 불가능한 것이기 때문. 다층일 때 이전 층의 출력값이 해당 층의 활성화 함수의 입력값이 되잖아? 근데 활성화 함수가 선형이어봐 선형 -> 선형 -> 선형...이래 되잖아 그래서 활성화 함수로는 비선형 함수를 사용해야하는거임.

ReLU 함수

입력이 0을 넘으면 입력을 그대로 출력, 0이하이면 0을 출력하는 함수

행렬의 곱

신경망은 분류, 회귀 모두 이용할 수 있음 어떤 문제냐에 따라 출력층에서 항등함수, 소프트맥스함수를 활성화 함수로 사용함

항등함수

입력을 그대로 출력함 따라서 출력층에서 항등함수를 사용하면 입력 신호 그대로 출력 신호가 된다.

소프트맥스 함수

분류에서는 소프트맥스 함수를 사용하는데 n은 출력층의 뉴런 수, yk는 그중 k번째 출력임을 뜻한다.

위와같은 코드는 오버플로 문제가 생길 수 있다 이를 해결하기 위해 함수를 개선된 소프트맥스 함수를 구현해보자. 이 함수가 의미하는 바는 지수함수를 계산할 때 어떤 정수를 더해도 결과는 바뀌지 않는다는 것이다. (왜지? 이건 알아봐야함니다.....시간이없어서...ㅎㅎ)

소프트맥스함수의 출력의 총합은 1이된다. 이 성질 덕분에 소프트맥스 함수의 출력을 '확률'로 해석할 수 있다. 이 결과 확률들로부터 가장 높은 확률이 n번째이니 n번이 정답이다.로 해석이 가능하다. 주의할 점은 각 원소의 대소관계는 변하지않는다는 점이다.

결과적으로 신경망으로 분류할 때는 출력층의 소프트맥스 함수를 생략해도 된다. (학습단계에서는 생략하면안됨 크로스엔트로피가뭐지....뒤에서 나오겟지?)

이번 장에서 할 일 -> 퍼셉트론을 써서 간단한 문제를 풀기

퍼셉트론이 먼가요? 다수의 신호를 입력으로 받아서 하나의 신호를 출력한다. (여기서 말하는 신호란 전류나 강물처럼 흐름이 있는 무언가라고 생각하면 조음) 퍼셉트론 신호가 흐른다(1) 흐르지않는다(0)라는 의미로 설명하겠슴.

*이번 장에서 기술하는 퍼셉트론은 정확히는 '인공뉴런', '단순 퍼셉트론'이라고 불리는 것이지만 기본적인 동작 방식은 거의 같으니 단순히 '퍼셉트론'이라고 하겠습니다.

입력으로 2개의 신호를 받은 퍼셉트론의 예 x1과 x2는 입력신호 y는 출력신호 w1, w2는 가중치 원은 뉴런 혹은 노드

입력신호가 뉴런에 보내질 때는 각각 고유 가중치가 곱해짐(w1x1, w2x2) 뉴런에서 보내온 신호의 총합이 정해진 한계를 넘어설 때만 1을 출력함 -> 뉴런이 활성화한다 라고 표현 그 한계를 임계값이라고 표현하며 세타 기호(θ)로 나타냄 퍼셉트론 동작 원리는 이게 끝임

복수의 입력신호에 각각의 가중치를 부여함 가중치는 각 신호가 결과에 주는 영향력을 조절하는 요소로 작용한다. -> 가중치가 클수록 해당 신호가 그만큼 더 중요함을 뜻함

AND게이트를 퍼셉트론으로 표현해보기

and게이트를 퍼셉트론으로 표현해보기 위해서 해야할 일은 2-2의 진리표대로 작동하는 w1, w2, θ을 정하기 만족하는 매개변수 조합은 많다. (0.5, 0.5, 0.7), (1.0, 1.0, 1.0) ... x1과 x2가 모두 1일때만 가중 신호의 총합이 임계값을 넘어서게 만들면 됨(먼말알?)

NAND게이트를 퍼셉트론으로 표현해보기

nand는 and게이트랑 반대 x1과 x2가 모두 1일때만 0을 출력 and게이트를 구현하는 매개변수 부호를 모두 반전하면 nand게이트가 됨

OR게이트를 퍼셉트론으로 표현해보기

그럼 or게이트는 어떻게 표현해야할까 입력 신호 중 하나 이상이 1이상이면 출력이 1이되는 논리회로 입력값 x1, x2 중 하나 이상이 1일 때, 그 입력값과 가중치를 곱한 가중합이 임계값 이상이 되도록 w1,w2, 0를 정하면 됨

AND게이트 파이썬으로 구현해보기

2-1에서의 세타를 -b를 치환하면 아래와 같은 식이 됨 여기서 b를 편향(bias) 이 그림에서의 관점으로 다시 퍼셉트론을 해석해보면 입력신호에 가중치를 곱한 값(x1w1)과 편향을 합하여 그 값이 0을 넘으면 1을 출력하고 그렇지 않으면 0을 출력한다.

가중치와 편향을 도입한 AND게이트 구현해보기

편향과 가중치는 기능이 다르는 사실에 주의 w1, w2는 각 입력신호가 결과에 주는 영향력을 조절하는 매개변수이고 편향은 뉴런이 얼마나 쉽게 활성화하느냐를 조절하는 매개변수 예를 들어, 편향이 -0.1이면 가중합이 0.1을 초과해야만 뉴런이 활성화됨 편향이 -20.0이면 가중합이 20.0울 초과해야만 뉴런이 활성화됨

가중치와 편향을 도입한 NAND게이트 구현해보기

가중치와 편향을 도입한 OR게이트 구현해보기

지금까지 and, nand, or게이트를 퍼셉트론으로 구현해봄 xor은 퍼셉트론으로 구현 불가능함

xor은 그래프에 선형으로 나타내는게 불가능함 이런식의 곡선 영역을 비선형영역, 직선영역을 선형영역이라고함

퍼셉트론으로는 xor게이트를 표현할 수 없기때문에 다층퍼셉트론으로 표현해야함 직선 여러개를 조합해서 곡선처럼 만들어야함 단층퍼셉트론으로 구현 가능한 게이트들을 조합하여 xor을 구현할 수 있음

XOR게이트 파이썬으로 구현해보기

뉴런을 이용한 퍼셉트론으로 표현하면 아래와 같이 됨 xor은 다층구조 왼쪽을 기준으로 0층, 1층, 2층

이런식으로 층이 여러개인 퍼셉트론을 다층 퍼셉트론이라고 함

1. 0층의 두 뉴런이 입력신호를 받아 1층의 뉴런으로 신호를 보낸다.
2. 1층의 뉴런이 2층의 뉴런으로 신호를 보내고 2층의 뉴런은 y를 출력한다.

단층 퍼셉트론으로 구현하지 못하는 것을 층 하나를 늘려 다층 퍼셉트론으로 구현이 가능하다는 것을 알게 되었읍니다~ ^^ 얏호

• 퍼셉트론은 다수의 신호를 받아 하나의 출력으로 나타내는 알고리즘이다
• 퍼셉트론에서는 가중치와 편향을 매개변수로 설정한다
• 퍼셉트론으로 AND, OR 같은 논리 회로를 표현할 수 있다
• XOR게이트는 단층 퍼셉트론으로는 구현할 수 없다
• 2층 퍼셉트론을 이용하면 XOR 게이트를 구현할 수 있다
• 단층 퍼셉트론은 선형 영역만 표현이 가능하고 다층 퍼셉트론은 비선형 영역도 표현할 수 있다
• 다층 퍼셉트론은 이론상 컴퓨터를 표현할 수 있다( ㅋㅋ)

최종 프로젝트였던 LearnsMate 프로젝트의 기능 중 캠페인 등록 과정에서 문제가 있다는 것을 발견했다. 약 5,000개의 쿠폰을 발급하는데 무려 4.8초나 걸림🙃

쿠폰 발급이 이렇게 느리면 다음과 같은 문제점이 발생할 수 있다.

쿠폰 발급이 느릴 때 발생하는 문제점

1. 사용자 경험 저하

쿠폰은 사용자에게 동시에 발급되어야 한다. 그러나 발급이 지연되면 어떤 사용자는 쿠폰을 받고 어떤 사용자는 쿠폰을 받지 못한 상태가 될 수 있다. 서비스의 신뢰도와 고객 만족도가 하락될 수 있다.

2. 시스템 부하 증가

해당 시스템에 대한 요청이 동시에 몰릴 경우 서버의 부하가 급격히 증가할 수 있다. 다른 요청에 대한 응답 속도를 낮추거나 시스템 장애를 일으킬 수 있다.

3. 서버 리소스 낭비

긴 처리시간 동안 CPU, 메모리 등의 서버 자원이 지속적으로 사용된다. 자원이 낭비되면 다른 중요한 작업에 할당할 수 있는 리소스가 부족해져 전체 시스템의 효율성이 떨어질 수 있다.

4. 처리 실패 및 데이터 불일치

시간이 오래 걸리면 처리 도중 네트워크 문제나 세션 타임아웃 등으로 인해 일부 작업이 실패할 수 있다. 이 경우 쿠폰 발급이 정상적으로 이루어지지 않거나, 데이터가 불일치하는 문제가 발생할 수 있다.

이러한 문제들을 해결하기 위해 성능 개선 작업을 진행했다.

기존(순차 처리)

기존 코드가 어떻게 되어있었냐면 Spring Batch와 Spring Scheduler를 이용해 즉시/예약 캠페인을 전송했다. 로그를 찍어 확인해 봤을 때 ItemReader와 ItemProcessor는 특별한 지연 없이 빠르게 처리 되었지만, ItemWriter과정에서 병목 현상이 발생했다.

chunk방식으로 배치 처리를 했는데, 100개 단위로 데이터를 읽고 처리하며 트랜잭션을 관리한다. step은 기본적으로 단일 스레드로 처리해서 이 과정이 순차적으로 처리되다보니 속도가 느렸던 것이다.

🔧1차 개선(순차 처리 -> 병렬 처리)

스프링 프레임워크에서 제공하는 batchTaskExecutor의 ThreadPoolTaskExecutor를 활용해 병렬 처리를 설정했다. 이를 통해 여러 스레드를 사용해 작업을 동시에 처리할 수 있게 했다.

병렬 처리를 통해 4.8초 -> 2.0초로 약간의 성능 개선이 되었다.

싱글코어 환경에서 어떻게 병렬 처리가 가능한지❔❓

멀티 스레딩과 컨텍스트 스위칭개념에 대해 알아야 한다. 멀티 스레딩이란 하나의 프로세스 안에서 여러 개의 스레드를 실행하는 것. 각 스레드는 독립적인 실행 흐름을 가지고 있으며 CPU 자원을 공유하면서도 동시에 작업을 분담한다. 하지만 '싱글 코어 환경에서는 물리적으로 하나의 코어에서 한번에 하나의 작업만 실행할텐데 어떻게 멀티 스레딩을 사용해요?' 라는 물음을 가질 수 있다. 싱글 코어 CPU는 실제로 한 번에 하나의 스레드만 실행할 수 있지만 OS가 매우 빠르게 여러 스레드를 번갈아 실행하여 마치 여러 작업이 동시에 수행되는 것처럼 보이게 한다. 이러한 빠른 전환 과정을 컨텍스트 스위칭이라고 한다. 컨텍스트 스위칭이란 CPU가 실행중인 스레드 상태를 저장하고 다른 스레드를 실행하기 위해 그 상태를 복원하는 과정을 말한다 이렇게 빠르게 전환하는 과정을 통해 여러 개의 스레드가 동시에 실행하는 것 처럼 보인다.

결론 -> 실제로 다중 스레드를 실행하는 것이 아니라 빠르게 전환해서 동시 실행하는 것 처럼 보이게 하는 거임.

🔧2차 개선(병렬 처리 + jdbcTemplate.batchUpdate())

병렬 처리를 통해 성능을 높였지만 여전히 최적의 성능이라 보긴 어려웠다. 추가로 분석해 본 결과, JPA의 saveAll() 메서드가 성능 저하의 주요 원인임을 발견했다.

saveAll() 메서드는 한번에 여러 개의 IssueCoupon 객체를 데이터베이스에 저장한다. 그런데 내부적으로 insert 쿼리를 한 번에 하나씩 실행하기 때문에, 많은 양의 데이터를 처리하면 DB로 보내는 요청 횟수가 많아지고, 결과적으로 네트워크 오버헤드와 트랜잭션 비용이 증가해 성능이 크게 떨어질 수 있다.

JDBC Batch Insert 방식은 대량 데이터 처리 시 성능이 매우 우수하다. JdbcTemplate의 batchUpdate()를 사용해서 여러 SQL insert문을 한번에 실행한다.

SQL을 한 번에 묶어서 처리하기 때문에 데이터베이스와의 통신 횟수가 줄어들고, 이로 인해 네트워크 지연과 데이터베이스 I/O 부하가 최소화되어 JPA 방식에 비해 훨씬 빠르게 처리할 수 있다.

jdbcTemplate.batchUpdate() 사용으로 2.0초 -> 0.1초로 줄어들었다.

수빈이는 현재 점 N (0 ≤ N ≤ 100,000) 에 있고, 동생은 점 K (0 ≤ K ≤ 100,000) 에 있다. 수빈이는

• 걷기: X → X-1, X → X+1 (1초 소요)

• 순간이동: X → 2*X (0초 소요)

위 방식으로 이동하며, 가장 빠른 시간에 동생을 찾아야 한다.

BFS로 문제 풀이 ❌

import sys
from collections import deque
inp = sys.stdin.readline

n, k = map(int, inp().split())

queue = deque()
queue.append([n, 0])

cur = [0]*2

visit = set()
visit.add(n)

while queue:
    cur = queue.popleft()

    if cur[0] == k:
        print(cur[1])
        exit()

    dx = cur[0]*2, cur[0]+1, cur[0]-1

    for nx in dx:
        if nx < 0 or nx > 100000 or nx in visit: continue
        visit.add(nx)
        if nx == cur[0]*2:
            queue.append([nx, cur[1]])
        else:
            queue.append([nx, cur[1]+1])

이 경우 더 빠른 시간으로 동생에게 도달할 수 있어도 이미 방문 처리가 되어버려 무시하게 되는 문제가 생겼다.

에시: 5-> 10-> 20

• 순간 이동으로 5-> 10 경로로 가면 0초
• 걷기로 5 -> 6 -> 7 -> 8 -> 9 -> 10 경로로 가면 5초 걷기로 먼저 10에 도달하면 visit에 추가되고 이후 순간이동으로 0초 안에 도달할 수 있어도 이미 방문 처리 되었기 떄문에 무시된다.

0-1 BFS로 문제 풀이 ✔️

가중치가 0, 1로 나뉘는 그래프에서는 deque의 앞, 뒤를 나눠서 우선순위를 설정하는 방식으로 구현하는 0-1 BFS가 적합하다.

0-1 BFS 특징

가중치가 0 또는 1인 그래프에서 사용 일반 BFS의 경우 큐의 한 방향으로만 추가하지만, 0-1는 앞, 뒤로 넣어 우선순위를 보장한다. 우선순위 큐 없이도 다익스트라와 같은 결과를 낼 수 있다.

import sys
from collections import deque
inp = sys.stdin.readline

n, k = map(int, inp().split())

queue = deque()
queue.append(n)

INF = int(1e9)
visit = [INF]*100001
visit[n] = 0

while queue:
    cur = queue.popleft()

    if cur == k:
        print(visit[cur])
        exit()

    nx = cur*2

    if 0 <= nx <= 100000 and visit[nx] > visit[cur]:
        visit[nx] = visit[cur]
        queue.appendleft(nx)

    nx = cur+1

    if 0 <= nx <= 100000 and visit[nx] > visit[cur]+1:
        visit[nx] = visit[cur]+1
        queue.append(nx)

    nx = cur-1

    if 0 <= nx <= 100000 and visit[nx] > visit[cur]+1:
        visit[nx] = visit[cur]+1
        queue.append(nx)

순간이동을 하는 경우 appendleft(nx)를 하여 우선 처리, 걷기는 append(nx)를 하여 뒤쪽에 넣어주었다.

또한 visit을 set() -> list()로 변경하고 visit[nx] > visit[cur]+1라는 조건을 걸어 더 짧은 경로일 때만 업데이트하도록 했다.

다익스트라로 문제 풀이 ✔️

다익스트라는 가중치가 양수인 그래프에서 최단 경로를 구하는 알고리즘이기 때문에 이 문제는 다익스트라로도 풀이가 가능하다.

import sys
import heapq
inp = sys.stdin.readline

n, k = map(int, inp().split())

INF = int(1e9)
distance = [INF] * 100001
distance[n] = 0

queue = []
heapq.heappush(queue, (0, n))

while queue:
    dist, cur = heapq.heappop(queue)

    if cur == k:
        print(dist)
        exit()

    if distance[cur] < dist:
        continue

    for next_pos, cost in ((cur*2, 0), (cur+1, 1), (cur-1, 1)):
        if 0<= next_pos <= 100000:
            new_cost = dist + cost
            if distance[next_pos] > new_cost:
                distance[next_pos] = new_cost
                heapq.heappush(queue, (distance[next_pos], next_pos))

0-1 BFS vs 다익스트라

⏰ 시간 복잡도 비교

가중치가 0, 1이라면 -> 0-1 BFS 가중치가 양수이고 다양한 값이 존재한다면 -> 다익스트라

결론

이 문제처럼 가중치가 0 또는 1인 경우에는 다익스트라보다 0-1 BFS가 더 빠르고 간결하게 구현 가능하므로, 해당 알고리즘을 사용하는 것이 좋다🤓

1. 일반 순열

순서가 있고 중복이 안됨 -> [1, 2, 3]중에 2개씩 선택하는 경우 12, 13, 21, 23, 31, 32

✅ DFS를 이용해 직접 구현한 일반 순열

import sys
inp = sys.stdin.readline()

n, m = map(int, inp.split())
arr = []
for i in range(n):
    arr.append(i+1)

result = []
visited = [False]*n

def permut():
    if len(result) == m: 
        print(result)
        return

    for i in range(n):
        if visited[i]: continue
        visited[i] = True
        result.append(arr[i])
        permut()
        visited[i] = False
        result.pop()

permut()

✅ itertools를 사용해 구현한 일반 순열

from itertools import permutations

data = [1, 2, 3]
result = list(permutations(data, 2))
print(result)

# 출력: [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

⏰시간복잡도

O(P(n, m)) = O(n! / (n - m)!) 첫 번째 자리에 n개 중 1개 -> n 두 번째 자리에 n-1개 중 1개 -> n-1 ...m개 뽑을 때 까지 곱하면 -> n × (n-1) × ... × (n-m+1) = P(n, m)

2. 일반 조합

순서가 없고 중복이 안됨 -> [1, 2, 3]중에 2개씩 선택하는 경우 12, 13, 23

✅ DFS를 이용해 직접 구현한 일반 조합

n, m = map(int, inp.split())
arr = [i+1 for i in range(n)]

result = []
def comb(idx):
    if len(result) == m:
        print(result)
        return

    for i in range(idx, n):
        result.append(arr[i])
        comb(i+1)
        result.pop()

comb(0)

✅ itertools를 사용해 구현한 일반 조합

from itertools import combinations

data = [1, 2, 3]
result = list(combinations(data, 2))
print(result)

# 출력: [(1, 2), (1, 3), (2, 3)]

⏰시간복잡도

O(C(n, m)) = O(n! / (m!(n-m)!)) 순열에서 중복되는 값을 없애야 하므로 -> P(n, m) / m!

3. 중복 순열

순서가 있고 중복이 가능 -> [1, 2, 3]중에 2개씩 선택하는 경우 11, 12, 13, 21, 22, 23, 31, 32, 33

✅ DFS를 이용해 직접 구현한 중복 순열

n, m = map(int, inp.split())
arr = [i+1 for i in range(n)]

result = []
def dup_permut():
    if len(result) == m:
        print(result)
        return

    for i in range(n):
        result.append(arr[i])
        dup_permut()
        result.pop()

dup_permut()

✅ itertools를 사용해 구현한 중복 순열

from itertools import product

data = [1, 2, 3]
result = list(product(data, repeat=2))
print(result)

# 출력: [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

⏰시간복잡도

O(n^m) 각 자리마다 n가지를 m번 가능 -> n × n × ... × n = n^m

4. 중복 조합

순서가 없고 중복이 가능 -> [1, 2, 3]중에 2개씩 선택하는 경우 11, 12, 13, 22, 23, 33

✅ DFS를 이용해 직접 구현한 중복 조합

n, m = map(int, inp.split())
arr = [i+1 for i in range(n)]
result = []

def dup_comb(idx):
    if len(result) == m:
        print(result)
        return

    for i in range(idx, n):
        result.append(arr[i])
        dup_comb(i)
        result.pop()

dup_comb(0)

✅ itertools를 사용해 구현한 중복 조합

from itertools import combinations_with_replacement

data = [1, 2, 3]
result = list(combinations_with_replacement(data, 2))
print(result)

# 출력: [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

⏰시간복잡도

O(C(n + m - 1, m)) = O((n + m - 1)! / (m!(n-1)!)) 서로 다른 원소 n개 중 중복을 허용하여 m개 선택 -> 중복 조합 공식 사용 [1,2,3]에서 2개를 중복 허용 조합 → C(3 + 2 - 1, 2) = C(4,2)

5. 중복값이 존재하는 일반 순열

순서가 있고 중복값이 존재하는 일반 순열 -> [1, 2, 3, 3]중에 2개를 선택하는 경우 12, 13, 21, 23, 31, 32, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 일반 순열

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
visited = [False]*len(arr)
def dup_num_permut():
    if len(result) == m:
        print(result)
        return

    tmp = 0

    for i in range(len(arr)):
        if tmp == arr[i] or visited[i]: continue

        result.append(arr[i])
        tmp = arr[i]
        visited[i] = True
        dup_num_permut()
        result.pop()
        visited[i] = False

dup_num_permut()

6. 중복값이 존재하는 일반 조합

순서가 없고 중복값이 존재하는 일반 조합 -> [1, 2, 3, 3]중에 2개를 선택하는 경우 12, 13, 23, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 일반 조합

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
def dup_num_comb(idx):
    if len(result) == m:
        print(result)
        return

    tmp = 0

    for i in range(idx, len(arr)):
        if tmp == arr[i]: continue
        result.append(arr[i])
        tmp = arr[i]
        dup_num_comb(i+1)
        result.pop()

dup_num_comb(0) 

7. 중복값이 존재하는 중복 순열

순서가 있고 중복 값이 존재하는 중복 순열 -> [1, 2, 3, 3]중에 2개를 선택하는 경우 11, 12, 13, 21, 22, 23, 31, 32, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 중복 순열

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
def ddup_permut():
    if len(result) == m:
        print(result)
        return

    tmp = 0
    for i in range(len(arr)):
        if tmp == arr[i]: continue
        result.append(arr[i])
        tmp = arr[i]
        ddup_permut()
        result.pop()

ddup_permut()

8. 중복값이 존재하는 중복 조합

순서가 없고 중복 값이 존재하는 중복 조합 -> [1, 2, 3, 3]중에 2개를 선택하는 경우 11, 12, 13, 22, 23, 33

✅ DFS를 이용해 직접 구현한 중복값이 존재하는 중복 조합

(※ itertools로는 구현 불가)

m = 2
arr = [1, 2, 3, 3]
result = []
def ddup_comb(idx):
    if len(result) == m:
        print(result)
        return

    tmp = 0
    for i in range(idx, len(arr)):
        if tmp == arr[i]: continue

        result.append(arr[i])
        tmp = arr[i]
        ddup_comb(i)
        result.pop()

ddup_comb(0)

⏰시간복잡도

중복 값이 존재하는 경우에 같은 조합/순열과 시간복잡도가 동일하지만 visited, tmp로 걸러주기 때문에 경우의 수 자체는 줄어듦

조합과 순열의 분류

조합과 순열의 핵심 차이

일반 순열/조합 차이 일반 순열은 순서가 존재하기 때문에 for i in range(n)를 사용하는데, 이때 같은 값이 두번 들어가는 것을 방지하기 위해 visited 배열이 필요하다. 일반 조합의 경우는 순서가 없기 때문에 for i in range(idx, n) 처럼 인덱스가 커지는 경우만 존재하기 때문에 visited 배열이 필요 없다.

일반 순열/조합과 중복 순열/조합의 차이 일반은 중복이 허용되지 않기 때문에 일반 순열의 경우는 visited를 이용해서, 일반 조합은 comb(i+1)처럼 현재 인덱스+1한 값을 매개변수로 넣어준다. 중복은 중복이 허용되기 때문에 중복 순열의 경우는 visited 배열을 없애주고, 중복 조합은 comb(i)를 넣어주면 된다.

'중복값이 존재'와 '중복'의 차이 중복값이 존재한다는 건 arr[1, 2, 3, 3]처럼 배열 내 중복 값이 존재한다는 거고, 중복이 가능하다는건 그 배열 내의 요소로 가능한 조합을 뽑을 경우 해당 요소를 여러 번 사용할 수 있다는 것이다.(예: 1을 두 번 사용해서 11을 만들 수 있음)

무선랜은 IEEE802.11 표준규격을 따름. 반이중화 통신을 사용

반이중화 통신

• 양쪽 장치는 서로 통신할 수 있지만 동시에는 할 수 없음 한번에 한 방향만 통신

CSMA/CA: 반이중화 통신 중 하나 장치에서 데이터를 보내기 전에 사전에 가능한 충돌 방지를 하는 방식 CSMA/CA로 프레임을 보낼땐 다음과 같은 과정이 일어남

1. 사용중인 채널이 있다? -> 다른 채널을 감지하다 유휴 상태인 채널 발견
2. 프레임 간 공간 시간(IFS: InterFrame Space)만큼 기다림. (IFS는 프레임 우선순위 정의할때도 사용. 낮으면 우선순위 높은거)
3. 프레임 보내기 전 랜덤 상수 기반으로 결정된 시간만큼 기다린 후 프레임 보냄

-> 제대로 송신이 되었고 ACK 세그먼트를 받았으면 마침 -> 받지 못했다면 k = k+1을 하며 과정 반복. 반복하다가 k가 Kmax보다 커지면 프레임 전송 버림(abort)

무선 LAN 대표적인 기술

와이파이

• 전자기기들이 무선LAN신호에 연결할 수 있게 하는 기술 근거리 무선망이라고도 할 수 있지만 근거리 무선망은 블루투스, 지그비 등도 있기때문에 엄밀히 말하면 틀린 말임

무선 LAN #2. 주파수와 2.4GHz와 5GHz의 차이

• 무선 LAN은 무선 신호 전달 방식을 이용하여 2대 이상의 장치를 연결하는 기술임 그냥 전달되는게 아니라 공기중에 주파수 쏴서 무선통신망 구축 크게 2개가 있음 우리가 카페 가면 2.4랑 5 두가지가 있음 (*5를 쓰는게 보통 더 빠름) 장애물이 많은 지역에서 5보다 좋음, 호환성이 좋음 -> 2.4 장애물엔 약함. 근데 속도가 더 빠름 -> 5

전이중화(full duplex) 통신은 양쪽 장치가 동시에 송수신할 수 있는 방식을 말한다. 동축케이블, 광케이블 등을 기반으로 만들어진 유선LAN을 이루는 이더넷은 IEEE802.3 프로토콜을 기반으로 전이중화 통신을 쓴다. 충전기 생각하면됨. 충전기 보통 USB C타입이랑 아이폰(8핀) 있음 충전기에 대한 프로토콜이 없다? 그럼 엄청 다양하게 나오겠지? 네트워크도 그런식의 규약을 IEEE802.3으로 정함 IEEE802.3은 이더넷프레임은 어떤 구조를 기반으로 할 것인지, 케이블의 최대 전송량, 어떤 케이블만이 가능하도록 할 것인지 등을 정한 규칙임

전이중화 통신

• 양쪽 장치가 동시에 송수신할 수 있는 방식. 송신로와 수신로를 나눠서 데이터를 주고 받을 수 있다.

예전 유선LAN은 반이중화 통신중 하나인 CSMA/CD(Carrier Sense Multiple Access with Collision Detection)를 썼다. 회선을 사용하는지를 파악한 후 사용하지 않는다면 데이터를 보내고 충돌이 발생한다면 일정 시간 이후 재전송 하는 방식을 말한다. 전이중화는 송신로 수신로가 따로 있다. 반이중화는 통로가 하나. 그니까 확인하고 보내는거. 이 확인하는 기술이 CSMA/CD

유선 LAN #2. 케이블

트위스트페어케이블

• 트위스트페어케이블은 2가지로 나뉨. 실드처리를 한 STP케이블 / 안한 UTP케이블

LAN케이블

• 유선 LAN을 구축할 때 쓰는 케이블인 LAN케이블은 UTP 케이블 타입이다.
• 참고로 LAN케이블을 꽂을 수 있는 커넥터를 RJ45 커넥터라고 한다.

광섬유케이블

• 레이저를 통해 통신하며 보통 100Gbps의 데이터를 전송하는 케이블을 광섬유케이블이라고 한다. 빛의 굴절률이 높은 부분을 코어, 낮은 부분을 클래딩이라고 함 이렇게 다른 밀도를 가지는 유리나 플라스틱 섬유를 기반으로 제작함. 한번 들어간 빛이 내부에서 계속해서 반사하며 전진하여 반대편 끝까지 가는 원리를 이용한 것이다.

L7스위치

• 로드밸런서라고도 함. 서버의 부하를 분산하는 기기. 강점: 서버 이중화, 보안 IP, Port 뿐만이 아니라 url, 헤더, 쿠키 등을 기반으로 트래픽을 분산한다. 헬스체크를 통해 장애가 발생한 서버를 확인하고 해당 서버로 트래픽을 보내지 못하게 하는 역할을 한다. 로드밸런서와 연결된 서버들한테 계속해서 TCP연결을 함. 3-웨이 핸드셰이크가 성립이 돼. 어 이 서버 살아있네? 하는거임 이거를 주기적으로 보내는걸 헬스체크라고 함

• 이로 인해 사용자는 장애 발생과 무관하게 서비스를 이용할 수 있게 됨

**AWS에서 L7스위치를 이용한 로드밸런싱은 ALB라는 컴포넌트를 통해서 하며 L4스위치를 이용한 로드밸런싱은 NLB 컴포넌트를 통해서 구축함

네트워크를 이루는 장치 #2. 전송 계층

L4스위치

• 로드밸런서의 특징인 트래픽 분산 등을 할 수 있다. 패킷의 IP주소와 Port번호를 참고해서 적절히 트래픽 분산을 할 수 있다. (L7스위치는 IP, Port번호 뿐만아니라 url, 헤더, 쿠키 등으로도 가능) 전송계층의 TCP, UDP 등의 헤더를 기반으로 우선순위를 판단해서 분산이 가능 L7과 똑같이 헬스체크가 가능하다.

네트워크를 이루는 장치 #3. 인터넷 계층

라우터

• 라우팅은 하나 이상의 네트워크에서 경로를 선택하는 프로세스를 말하는데 이 라우팅을 하는 장비를 라우터라고 함. 다른 네트워크에 존재하는 장치끼리 서로 데이터를 주고받을 때 "패킷소모 최소화", "경로 최적화"를 하는 장비 (라우팅을 할때마다 패킷이 소모됨. 이 패킷소모를 최소화해주는게 라우터)

L3스위치

• L2스위치의 기능 + 라우팅을 하는 장비 라우팅 테이블을 참조해서 IP패킷에 IP주소를 담아 보낸다.

네트워크를 이루는 장치 #4. 데이터링크 계층

• TCP계층의 링크계층을 쪼개서 데이터링크 계층과 물리 계층으로 나눌 수 있음. 데이터링크 계층은 '이더넷 프레임'을 통해 에러 확인, 흐름 제어, 접근 제어를 담당하는 계층을 말한다.
• 물리계층은 무선 LAN과 유선 LAN을 통해 0과 1로 이루어진 데이터를 보내는 계층을 말한다.

L2스위치

• 장치들의 MAC 주소를 MAC 주소 테이블을 통해 관리하며 해당 테이블을 기반으로 인터넷 계층에서 받은 패킷을 기반으로 이더넷프레임을 만들어 목적지 MAC 주소로 패킷을 보내주는 역할을 함

L2스위치와 L3스위치의 차이점

L2스위치는 L3스위치와 비교하는 식으로 질문이 많이 들어옴

네트워크 레이어를 통해 데이터가 데이터링크 레이어로 캡슐화되어 내려옴. 네트워크 레이어는 L3스위치가 담당, 데이터링크 레이어는 L2스위치가 담당. L3스위치는 라우팅 테이블 / L2스위치는 Mac 주소 테이블 L3스위치는 IP주소를 담당 / L2스위치는 Mac주소를 담당 L3스위치는 IP패킷을 보냄 / L2스위치는 이더넷프레임을 보냄

브리지

• 브리지는 두 개의 근거리 통신망(LAN)을 상호 접속할 수 있도록 하는 통신망 연결 장치를 말한다. 통신망의 범위를 확장하고 서로다른 LAN을 기반으로 하나의 통신망을 구축할 때 쓰인다.

네트워크망 두개를 하나로 합칠때 브리지를 사용

네트워크를 이루는 장치 #5. 물리 계층

• 물리계층은 실제로 유선랜 무선랜을 기반으로 바이너리 데이터(0, 1)를 주고받는 계층임

NIC

• LAN카드라고 함. 네트워크 인터페이스 카드(Network Interface Card)는 네트워크에 연결하기 위해 PC에 설치된 회로기관을 말함. 이 장치에는 PC의 고유 식별번호인 MAC주소가 있다. 우리가 갑자기 네트워크 연결이 안된다? 이 NIC에 문제가 있을 확률이 높다

리피터

• 들어오는 약해진 신호 정도를 증폭하여 다른 쪽으로 전달하는 장치이다

AP

• Access Point는 패킷을 복사하는 장치이다. AP에 유선 LAN을 연결한 후 무선 LAN기술을 기반으로 무선 네트워크망을 구축할 수 있다.

네트워크 기기는 계층별로 나눌 수 있다. 상위 계층을 처리하는 기기는 하위 계층을 처리할 수 있지만 그 반대는 불가하다. L7 스위치는 L4 스위치가 하는 기능을 할 수 있음 -> 위 계층은 아래 계층이 하는 일을 할 수 있다.

레이어별 프로토콜, PDU

레이어별 네트워크 장치

GET: 데이터를 읽다.

• url을 기반으로 하기때문에 길이제한(2000자미만)이 있다.
• 성공시 HTTP 상태코드 200을 반환한다.
• 캐싱이 가능하다.
• url을 기반으로 요청하기 때문에 해당 요청의 파라미터가 브라우저 기록에 남는다.
• url을 기반으로 요청하기 때문에 요청할 때 ASCII문자열만을 보낼 수 있다.
• 사용자 이름, 비밀번호 등 민감한 정보를 전달할 때 사용하지 않는다.

POST: 데이터를 생성하다.

• url이 아닌 HTTP message body를 통해 데이터를 전달한다.
• HTTP message body를 통해 전달되기 때문에 길이 제한이 없다.
• 성공적으로 데이터를 생성할 경우 HTTP 상태코드 201을 반환한다.
• 캐싱이 불가능하다.
• url을 기반으로 요청하지 않기 때문에 해당 요청의 파라미터가 브라우저 기록에 남지 않는다.

HTTP 메서드 #2. PUT과 PATCH의 차이

둘 다 데이터를 수정할 때 쓰는 메서드이지만 다음과 같은 차이가 있다.

PUT: 업데이트하는 데이터의 전체를 보내다.

• 요청을 보낼 때 해당 데이터 전체를 보내야 하고 전체 데이터의 교체를 의미한다.
• PUT은 해당 데이터가 없다면 새로이 생성하고 있다면 요청할 때 보낸 데이터와 교체를 진행한다. 예) '{"a":1, "b": 2}'가 있을 때 b를 3으로 바꾼다고 했을 때 'put'의 경우 '{"a":1, "b": 3}'으로 전체 데이터를 전부 보내야 한다.

PATCH: 업데이트하는 데이터의 일부를 보내다.

• 요청을 보낼 때 수정하는 일부분만 보내면 되고 일부분의 교체를 의미한다. 예) '{"a":1, "b": 2}'가 있을 때 b를 3으로 바꾼다고 했을 때 'patch'의 경우 '{"b": 3}'으로 부분 데이터를 보낸다.

1xx (정보)

• 서버가 요청을 잘 받았으며 해당 프로세스를 계속 이어가며 처리하는 것을 의미한다. 100: 계속함을 의미

2xx (성공)

• 서버가 요청을 잘 받았고 이를 기반으로 클라이언트에게 성공적으로 데이터를 보낸 것을 의미한다. 200 OK: 요청이 성공적으로 되었음을 의미 201 Created: 요청이 성공적이었으며 그 결과로 새로운 리소스가 생성되었음을 의미

3xx (리다이렉션)

• 서버가 클라이언트의 요청에 대해 완료를 위해 추가 작업 조치가 필요하다는 것을 의미한다. 301 Moved Permanently: 이 응답코드는 요청한 리소스의 URI가 변경되었음을 의미. 변경된 새로운 URI를 301 상태코드와 함께 주어야 한다.

4xx (클라이언트 오류)

• 클라이언트가 요청한 페이지를 제공할 수 없거나 클라이언트의 요청이 잘못되어 결과적으로 요청을 처리할 수 가 없음을 의미한다. 400 Bad Request: 서버가 클라이언트 요청을 이해할 수 없음을 의미 401 Unauthorized: 클라이언트의 인증이 되지 않음을 의미 404 Not Found: 요청받은 컨텐츠를 찾을 수 없다는 것을 의미

5xx (서버 오류)

• 서버가 클라이언트의 요청을 처리하지 못하는 상태임을 의미한다. 500 Internal Server Error: 서버에 오류가 있음을 의미 502 Bad Gateway: 게이트웨이 또는 프록시서버가 오류가 생겼음을 의미 504 Gateway Timeout: 게이트웨이 또는 프록시서버가 정해진 Timeout 시간동안 클라이언트의 요청을 처리하지 못함을 의미

토큰기반은 유저의 상태를 토큰에 담아놓고 서버들은 stateless하게 가자라는 이론이 담긴 기법임 이 토큰에다가 유저의 상태값을 다 넣음 이걸 기반으로 유저가 유효한지아닌지를 확인 어떻게 구현하냐면 MSA기반으로 설명 장바구니, 결제 서버가 있다 토큰을 관리하는 서버도 한대 존재 나머지 서버들은 토큰에대한 어떤 로직도 없음 보통은 이렇게함

근데 토큰 서버를 따로 두지 않고 다른 도메인을 처리하는 서버에 합쳐서 구축할 경우에 그 도메인에서 에러가 발생할 경우 인증에 관한 기능이 마비가 되고 이는 다른 도메인의 기능이 연쇄적으로 마비가 될 가능성이 있다.

토큰이 어떻게 생성되는가

1. 유저가 올바른 패스워드를 입력하면 토큰을 관리하는 authorization server에서 토큰을 줌
2. 그 토큰을 기반으로 사용자가 요청을 할 때 access토큰을 http header-authorization 또는 http header-cookie에 담아 인증이 필요한 서버에 요청해 원하는 컨텐츠를 가져옴

JWT란?

• JWT는 JSON Web Token을 의미하며 헤더, 페이로드, 서명으로 이루어져 있으며 JSON 객체로 인코딩되며 메시지 인증, 암호화에 사용된다. Header: 토큰 유형과 서명 알고리즘, base64URI로 인코딩됨 Payload: 데이터, 토큰 발급자, 토큰 유효기간, base64URI로 인코딩됨 Signature: (인코딩된 header + payload) + 비밀키를 기반으로 헤더에 명시된 알고리즘으로 다시 생성한 서명값

JWT 장점

• 사용자 인증에 필요한 모든 정보가 토큰 자체에 포함되어있기 때문에 별도의 인증 저장소가 필요 없다.
• 다른 유형의 토큰과 비교했을 때 경량화 되어있다.
• 디코딩했을 때 JSON이 나오기 때문에 JSON을 기반으로 쉽게 직렬화, 역직렬화가 가능하다.

JWT 단점

• 토큰이 비대해질 경우 당연히 서버 과부화에 영향을 줄 수 있다.
• 토큰을 탈취당했을 경우 디코딩했을 때 데이터를 볼 수 있다. -> 가장 신경써야하는 단점

토큰기반인증방식을 구현할 땐 refresh토큰과 access토큰 두 개를 기반으로 구현한다. access토큰의 수명은 짧게 - 헤더에 refresh토큰의 수명은 길게 - 데이터베이스나 Redis에 저장

refresh토큰이란?

• access토큰이 만료되었을 때 다시 access토큰을 얻기 위해 사용되는 토큰. 이를 통해 access토큰이 만료되었을 때마다 인증에 관한 비용이 줄어들게 된다. 로그인을 하게 되면 access토큰과 refresh토큰 두개를 얻는다.

그 다음 access토큰이 만료되거나 사용자가 새로고침을 할 때 refresh토큰을 기반으로 새로운 access토큰을 얻는다.

access 토큰 -> 인증을 위한 토큰 해커가 이걸 탈취하면 안되니까 만료기한을 작게 해야함 만료기한이 작으면 로그인을 여러번 해야한다는 단점이 생기잖아 서비스 이용하기 싫어짐 이걸 해결하기위해 refresh 토큰과 같이 씀 refresh 토큰은 만료기한이 큼. 이걸 기반으로 access토큰을 발급 받음 이렇게 하면 토큰기반인증방식의 장점을 취하면서 access토큰의 만료기한이 줄어드는것까지 보완하는 방식이 된다.

주의해야할 점

• access토큰을 얻었다면 그 이후에 요청을 할 때는 HTTP header-Authorization 또는 HTTP Header-Cookie에 담아 요청을 하게 된다. 이때 다음과 같은 규칙을 지키는 것이 좋다.

1. Bearer <토큰>으로 Bearer을 앞에 둬서 토큰기반인증방식이라는 것을 알려주어야 한다.
2. https를 사용해야 한다.
3. 쿠키에 저장한다면 sameSite: 'Strict'을 써야한다.
4. 수명이 짧은 access token을 발급해야 한다.
5. url에 토큰을 전달하지 말아야 한다.

** 이러한 점들은 OAuth2.0과 JWT에 관한 표준문서인 RFC6750, RFC7519를 기반으로 설명함

HTTP의 특징중 하나는 상태가 없음(stateless)하다라는 것 즉 HTTP 요청을 통해 데이터를 주고받을 때 요청이 끝나면 사용자의 정보 등을 유지하지 않는 특징이 있다. 근데 어떻게 로그인 상태를 유지하나? -> 이전에 로그인한 상태 값이 남아있어야 한다.

• 세션: 서버와 클라이언트의 연결이 활성화된 상태
• 세션ID: 웹서버 또는 DB에 저장되는 클라이언트에 대한 유니크한 ID(사용자를 구분할 수 있음)

사용자가 로그인을 위해 정보 전송 입력한 값이 맞다면 서버는 세션아이디를 만들고 쿠키에 세션아이디를 담아 return하고 db나 was(web application server)에 저장해둠 다음부터 요청할때 클라이언트의 요청헤더에는 자동으로 쿠키가 설정됨 서버는 이 세션아이디를 기반으로 이 세션아이디에 맞는 유저 아이디/비번을 찾음 -> 유효한가를 파악 유효하네? 로그인 되어있다~는 상태값을 알려줌

db에 세션아이디 저장할 때의 문제점 어떤 단점이있냐. 직렬화와 역직렬화에 대한 cost VARCHAR에 저장된 값을 꺼내서 다시 클라이언트에 보낼텐데 (JSON타입이나 문자열) 이때 오버헤드가 될 수 있다. 이러한 오버헤드가 그렇게 많진않지만 굳이 단점을 뽑자면 이거다

서버에 세션아이디 저장할때의 문제점 세션아이디가 많아지면(사용자가 많아지면) 서버의 메모리가 많이 소모되는 단점이 있다. 이것도 그렇게 많진 않다.

공통점

1. 브라우저에 캐싱을 함으로써 서버에 대한 요청을 줄여 서버부하를 방지할 수 있다.

• 세 개 모두 어떤 브라우저의 데이터 조각임 이걸 기반으로 뭘 할수있냐 서버에다가 요청을 한다 치자 요청해야할 정보를 이미 쿠키 등에 캐싱을 해두었기때문에 요청할 필요가 없으니 서버부하가 감소한다는 것

2. 캐싱으로 인해 다운로드하는 컨텐츠가 줄어들어 웹사이트의 컨텐츠를 더 빨리 다운로드가 가능하다.

• 서버에다가 100개를 요청해서 100개를 받아 그중 20개를 이미 로컬스토리지나 세션스토리지에 저장해뒀어 100개 다 필요없고 80개만 필요하니까 더 빨리 다운로드가 가능함

3. 사이트 기본 설정 커스터마이징(색상, 글꼴 크기 등)을 저장하거나 로그인 상태를 유지할 때 사용될 수 있다.

• 라이트/다크모드같은거. 로그인상태 유지

차이점

쿠키와 로컬스토리지는 오리진이 같은 여러개의 창이나 탭을 닫아도 유지가 된다.

브라우저의 작은 데이터 조각. 쿠키는 보통 어떻게 설정되냐 사용자가 서버에 요청 사용자가 서버 페이지 내놔하면 서버는 set-cookie라는 응답헤더에 설정한 쿠키를 보낸다. 다음부터 이 사용자가 쓰고있는 브라우저는 해당 쿠키값을 가지고 있게 됨 그 다음 서버에다가 요청을 할 때 자동으로 쿠키가 요청헤더의 쿠키라는 키를 가진 헤더를 추가해서 요청이 되고 브라우저에도 저장되게 된다. 쿠키는 클라이언트와 서버 둘 다 조작이 가능하지만 보통 서버에서 만료 기한 등을 설정 및 컨트롤 함 저장용량 최대 4Kb 로그인, 장바구나, 사용자 커스터마이징, 사용자 행동분석(주로 개인화된 광고에 활용되는 것들)에 사용

클라이언트에서도 설정 가능한 쿠키

• 클라이언트에서 자바스크립트 - document.cookie를 통해 쿠키를 설정할 수 있고 보낼때도 header - Cookie에 값을 정해서 보낼 수도 있다. (권장X) 왜 권장 X? -> 이렇게되면 쿠키에대한 제어권을 클라이언트에게 두게 되는데 쿠키는 보통 민감한 정보들이 담길수도 있기 때문에 이 제어권에 관한 것을 클라이언트가 아닌 서버에 두게 만들어야한다. == (네이버 서버가 해킹당할 확률 vs 내 폰 해킹될 확률 당연히 내폰이 높음 ㅇㅇ 보안이취약하겠지? 쿠키는 사용자도 되고 서버도되지만 서버에 두라는게 이런 이유)

세션쿠키

• Expires 또는 Max-Age 속성을 지정하지 않은 것. 브라우저가 종료되면 쿠키도 사라짐

영구쿠키

• Expires 또는 Max-Age 속성을 지정해서 특정날짜 또는 일정기간이 지나면 삭제되게 만든 쿠키. 브라우저를 닫을 때 만료되지 않음

secure

• 쿠키에 secure 옵션을 추가하면 https로만 쿠키를 주고받을 수 있게 하는 옵션이다. 하지만 Chrome v89 및 Firefox v75이상부터 localhost에서는 이 사양을 무시함.

• 위 버전의 브라우저는 http라도 localhost라면 secure 옵션을 걸어도 http로 쿠키를 주고 받을 수 있어 쉽게 테스팅이 가능함

httponly

• 공격자가 쿠키를 자바스크립트로 빼낼 수 없게 만든다. (document.cookie로 접근 불가)

samesite

• 요청이 동일한 도메인에서 시작된 경우에만 쿠키가 애플리케이션으로 전송되도록 허용

  a. loltier: master는 secure 속성 / b. kundol: amumu는 httponly 속성 a는 document.cookie로 추출하려고 해도 나오지 않음 secure는 https에서만

쿠키의 시큐어코딩

• 쿠키 - 세션으로 로그인을 처리한다면 다음과 같이 시큐어 코딩을 해야한다.
  1. cookie에 세션 ID를 담을 때 이 세션 ID를 기반으로 클라이언트의 개인정보를 유추할 수 없게 해야 한다.
  2. 자바스크립트로는 파악할 수 없게(document.cookie로 추출불가능하게) httponly 옵션을 걸고 https로만 쿠키를 주고받을 수 있게 secure옵션을 걸어야 한다.
  3. 일정시간의 세션 타임아웃을 걸어야 한다.

쿠키허용관련 알림창

• 서비스 운용시 쿠키를 사용한다면 쿠키허용관련 알림창을 만들어야한다.

• 방문기록을 추적할 때 쿠키가 사용되기 때문 이는 사용자의 데이터 간접수집에 해당하며 거기에 해당하는 KISA(한국인터넷진흥원) 지침을 준수해야하기 때문이다.

세션스토리지는 로컬스토리지와 매우 유사함 웹스토리지 객체로 브라우저 내 key, value 형태로 오리진에 종속되어 저장된다(로컬이랑 똑같) 하지만 동일한 오리진이라도 브라우저의 각 탭마다 독립적으로 저장된다. 다른 탭에서 세션 스토리지에 저장된 데이터에 접근할 수 없다. 세션스토리지는 탭을 닫으면 만료된다.

** 로컬스토리지와 세션스토리지의 차이점? -> 로컬스토리지는 동일한 오리진이면 로컬스토리지의 값을 공유하지만 세션스토리지는 그렇지 않다.

1. 로컬스토리지

브라우저마다 저장되는 데이터. 같은 오리진끼리 로컬스토리지를 공유함(오리진에 종속됨) 크롬 브라우저 로컬스토리지에다가 큰돌 천재라고 저장 했다 -> 익스플로러에서 못봄 로컬스토리지는 key, value 형태

특징

• 하나의 키에 오로지 하나의 값만 저장됨
• 데이터는 사용자가 브라우저에서 수동으로 삭제하지 않는 한 평생 동안 로컬 저장소에 저장되어 만료 날짜가 없다. 컴퓨터 종료해도 사라지지 않음
• 최대 저장 용량 5MB
• 사용자의 행위를 기억할 때 로그인을 유지하기 위한 값 등으로 사용되며 로컬 스토리지 데이터는 자동으로 서버로 전송되지 않는다. (쿠키는 자동 전송)

내가 필터링 조건 같은걸 걸어두고 새로고침을 했을 경우 조건이 그대로 유지되었으면 좋겠다 -> 로컬스토리지에 저장

웹브라우저의 캐시 - 로컬스토리지와 오리진(origin)

2. 로컬스토리지와 오리진

오리진? 주소창에 url 치고 주소 들어갈때 프로토콜://호스트네임:포트번호/패스/?쿼리스트링/#해시 프로토콜, 호스트네임, 포트가 오리진임(포트번호는 생략되어있음)

https의 기본 포트번호는 443 / http의 기본 포트번호는 80

웹브라우저의 캐시 - 로컬스토리지의 활용사례:캐싱

1. 로그인 유지

• 로그인 방식은 세션/토큰이 있음 토큰기반일 때 어떤 서버에 아이디/패스워드 입력 토큰을 받음 이 토큰을 로컬스토리지에 저장 다시 요청할때 다시 로그인하지 않고 로컬스토리지에 저장된 토큰을 서버에 줌 (header-authorization) -> 로그인 유지

2. 캐싱 사용자는 브라우저에 입력을 하고 설정을 함 이런 값들을 캐싱. 담아둔다 자동완성을 생각해보자. 이전에 입력한 값들이 다시 입력할 가능성이 높다 사용자가 다시 입력하는 수고를 덜 수 있음 -> UX 증가. 이러한 것에 캐싱이 사용됨

우리가 http 요청할때 그냥 하는게 아님 헤더랑 바디로 구분된 녀석을 보냄 받을때도 헤더랑 바디

헤더가 무엇인가 html, xml, json 등 본문 -> http body general, response/request headers에 담기는게 header 헤더는 콜론으로 구분되는 key, value 형태로 설정됨 http요청을 할 때 3가지 헤더인 일반헤더, 요청헤더, 응답헤더가 자동으로 생성됨 서버에서 설정하는 헤더를 응답헤더 클라이언트에서 설정한 헤더를 요청헤더라고 함

일반헤더 - 요청한 URL, 요청메서드, 해당 자원을 요청할 때 해당 자원의 출처를 나타내는 URL을 노출시킬지 말지를 정하는 보안정도가 설정되어있는 Referrer Policy 등이 들어간다.

요청헤더 - 클라이언트가 요청할 때 클라이언트가 설정하는 또는 자동으로 설정되는 헤더를 말한다. 요청헤더에는 메서드, 클라이언트의 OS, 브라우저 정보 등이 담긴다.

응답헤더 - 서버가 클라이언트에게 응답을 보낼 때 설정하는 또는 자동으로 설정되는 헤더를 말한다. 응답헤더는 서버의 소프트웨어 정보 등이 담긴다. 예를 들어 nginx를 프록시서버로 두었다면 해당 정보가 표기된다. 하지만 대부분의 서버는 일반적으로 해커가 서버에서 어떤 소프트웨어가 사용되고 있는지 알 기 어렵게 하기 위해 서버 정보를 숨긴다.

유니캐스트란 1:1 통신을 말함. 대표적으로 HTTP통신이 있음 -> 내가 네이버 드가면?(정확히는 HTTPS) HTTP 요청한거임 이게 1ㄷ1 유니캐스트 가장 일반적인 전송 형태

멀티캐스트

멀티캐스트란 1:N 통신을 말함. N이지만 모든 노드들에게 데이터를 전달하지는 않고 특정 그룹에게만 데이터를 전달한다.

브로드캐스트

브로드캐스트란 1:N 통신을 말함. 그룹이 아닌 연결 되어있는 모든 노드에게 데이터를 전달함. 예) ARP

비선형 자료구조: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조 예 - 트리, 그래프

그래프

정점과 간선으로 이루어진 자료구조

정점과 간선

어떠한 곳에서 어떠한 곳으로 무언가를 통해서 간다. 어떠한 곳: 정점(vertex) 무언가: 간선(edge) 단방향 간선, 양방향 간선이 있음

정점으로 나가는 간선: outdegree 정점으로 들어오는 간선: indegree

정점과 간선으로 이루어진 집합: graph

가중치: 간선과 정점 사이에 드는 비용

트리

그래프 중 하나로 정점과 간선으로 이루어져 있고 트리 구조로 배열된 일종의 계층적 데이터의 집합 루트노드, 내부 노드, 리프 노드 등으로 구성

트리의 특징

1.부모 - 자식 계층 구조 2. V - 1 = E 간선 수는 노드 수 - 1 3. 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재' 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있음

루트 노드

: 가장 위에 있는 노드 (보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다)

내부 노드

: 루트 노드와 내부 노드 사이에 있는 노드

리프 노드

: 자식 노드가 없는 노드

트리의 높이와 레벨 깊이: 트리의 깊이는 각 노드마다 다름 루트 노드부터 특정 노트까지 최단 거리로 갔을 때의 거리 높이: 루트 노드부터 리프 노드까지 거리 중 가장 긴거리 레벨: 깊이와 같은 의미 서브 트리: 트리 내의 하위 집합

이진 트리

: 자식의 노드 수가 두 개 이하인 트리

• 정이진 트리(full binary tree): 자식 노드가 0 또는 두 개인 이진 트리

• 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진트리. 마지막 레벨의 경우 왼쪽부터 채워져 있다
• 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리
• 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리
• 균형 이진 트리(balanced binary tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진트리 map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나임

이진 탐색 트리

: 노드의 오른쪽 하위 트리에는 '노드 값보다 큰값'이 있는 노드만 포함 왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어있는 트리 왼쪽 및 오른쪽 하위 트리 해당 특성을 가짐 -> '검색'을 하기에 용이

왼쪽에는 작은 값 / 오른쪽에는 큰 값이 정해져 있기 때문에 10을 찾으려고 한다면 25의 왼쪽 노드들만 찾으면 됨

보통 $O(logn)$이지만 최악의 경우 $O(n)$이 걸린다. -> 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 떄문

AVL 트리

AVL 트리(Adelson-Velsky and Landis tree)는 선형적 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다. 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 난다.

탐색, 삽입, 삭제: $O(logn)$

삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 잡음

레드 블랙 트리

균형 이진 탐색 트리. 탐색, 삽입, 삭제: $O(logn)$

각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장 삽입 및 삭제 중 트리가 균형을 유지하도록 사용됨

"모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다"등의 규칙을 기반으로 균형을 잡는 트리

힙

완전 이진 트리 기반의 자료구조

• 최대힙: 루트 노트에 있는키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함
• 최소힙: 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 각 노드의 자식 노드와의 관계에서도 이 특징이 재귀적으로 이루어져야 함

  최대힙의 삽입

  : 새로운 노드를 힙의 마지막 노드에 이어서 삽입 새 노드를 부모 노드들과의 크기를 비교하며 교환

최대힙의 삭제

: 최댓값은 루트 노드이므로 루트 노드가 삭제되고 마지막 노드와 루트 노드를 스왑

우선순위 큐

우선순위 대기열이라고도 하며 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조

힙을 기반으로 구현된다.

맵

특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조

"이승철": 1, "박동영": 2 (키: value)

래드 블랙 트리 자료 구조를 기반으로 형성 삽입되면 자동으로 정렬됨

셋

특정 순서에 따라 고유한 요소를 저장하는 컨테이너 중복되는 요소는 없고 오로지 희소한 값만 저장하는 자료구조

해시 테이블

무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블

삽입, 삭제, 탐색: $O(1)$