어제자로 학기로부터 해방되어, 평소 꼭 정복해보고 싶었던 자료구조, 그리고 알고리즘에 대해 약간의 정리를 해볼까 합니다. 일종의 Cheatsheet인데요, 나중엔 머릿속에 다 들어와 있겠죠? 코딩테스트 풀이 때, 시간 초과와 메모리 초과로부터 좀 해방될 수 있었으면 좋겠네요. Data Structures Data Structure Purpose Time Complexity (Avg)Space Complexity Additional Notes Array Stores elements of the same type in contiguous memory locations. Access: O(1), Search: O(n), Insertion: O(n), Deletion: O(n) O(n) Fixed size, e..

데이터베이스 과목을 열심히 들은 보람이 있네요.

이해하며 개인 노션에 작성한 글인데, 경어체를 쓸 겨를이 없군요! 추후 수정하도록 하겠습니다. 우선, s값을 계산해보자. 입력값 Xi * Wi(가중치)(i는 1부터 끝까지) + 1 * W0(bias) = s 구한 값을 f(), 즉 전달 함수(=활성화 함수)에 집어 넣는다. 여기서는, s가 특정값 이상이면 1이고, 아니면 0이다. 생물에서, 역치를 넘으면 반응하는 것 과 비슷하다. 그럼, OR 연산을 하는 퍼셉트론을 구해보자. s는 어떻게 계산될까? x1 + x2 + (-0.5) = s 일 것이고, 그럼 만약 x1 = 1, x2 = 0 이면? 0.5가 나오고, 0을 넘으니 f(s) = 1 일 것이다. 그럼 만약 x1 = 0, x2 = 1 이면? 마찬가지로 0.5가 나오고, 0을 넘으니 f(s) = 1 일 ..

우선 군집화가 뭐였나요? 유사한 데이터끼리 모으는 것을 군집화 라고 합니다. 군집화는 다음과 같은 종류가 있습니다. 계층적 군집화: 군집들이 계층적인 구조를 가지도록 합니다. 병합형 계층적 군집화 하나의 데이터로 출발하여, 가까운 것을 결합해 나가며 계층구조를 생성합니다. Bottom-Up 방식이라고 볼 수 있습니다. 분리형 계층적 군집화 전체 데이터를 가지는 하나의 군집에서 출발하여, 유사성을 바탕으로 군집을 분리합니다. 분할 군집화: 계층 구조를 맏늘지 않고, 전체 데이터를 유사한 것들끼리 나눠서 묶습니다. ex) K-means 알고리즘 분산값 V를 최소로 하는 점의 집합을 찾는 것이 목표입니다. 1. 초기에 군집의 중심을 임의로 설정해줍니다. (K개 설정) 2. 모든 점들에 대해, 가장 가까운 U(..

결정 트리는, 트리 형태로 의사결정 지식을 표현하는 것을 말합니다. 위의 예시는, 날씨가 어떨 때 테니스를 치러 갈까? 를 결정하는 의사결정 트리인데요, 쉽게 말해 Internal Node는, 기상 상황들을 말하는 것이고, Edge는 그 기상 상황이 어떤지, 즉 속성값을 나타냅니다. 그리고 마지막 Terminal node는, 부류. 여기서는 Yes or No를 나타냅니다. 결정 트리 알고리즘을 구성하는 것은, - 우선 하나의 노드로 구성된 트리에서 시작합니다. 1. 분할 속성을 선택하고, 2. 속성값에 따라서 서브트리를 확장 및 생성하고, 3. 데이터를 속성값에 따라 분배합니다. 이 1-2-3 과정을 반복합니다. 우리는 일반화 성능이 우수한 최대한 간단한 트리를 원합니다. 방금, 결정 트리 알고리즘을 구..

Routing이 뭔지 기억 나시나요? Network Layer의 두 가지 핵심기능이 포워딩과 라우팅 이었죠, 포워딩은 라우터 내부에서 적절한 Input port -> Output port를, 라우팅 테이블을 기반으로 찾아가는 것이었고요, 라우팅은 Source -> Destination 까지의 전체적인 경로를 결정합니다. 이 라우팅 기법에는 두가지가 있는데요, 1. Link State routing - 다익스트라 알고리즘 - OSPF - Complete Topology 2. Distance Vector routing - 벨만포드 알고리즘 - RIP - Partial Topology(Info) 아직 무슨 소리인가 싶겠지만, 차근차근 알아봅시다. 라우팅 알고리즘을 어떻게 분류할까요? 아 참, 잠깐 복습해봅시다..

네트워크 레이어의 프로토콜은 세 가지가 공존하는데요, Routing Protocol(경로를 설정해 줌) - 이 프로토콜을 통해 포워딩 테이블을 작성합니다. IP Protocol(= routed protocol) - 주소 입니다. Datagram 포맷을 가지고 있습니다. ICMP Protocol(에러를 추적하고, 컨트롤해주는 프로토콜) IP의 데이터그램의 형식입니다. IPv4 방식이나, ver엔 4가 들어가구요, TTL 이라는 개념이 있습니다. 패킷이 여러 라우터들을 거쳐 지나가는데, 어쩌다 무한루프를 돌다가 좀비가 될 수 있으니 TTL 이란 것을 설정해주는데, 일종의 수명 입니다. Hop - Hop 을 할 때마다 TTL을 하나씩 감소시킵니다. TTL이 0이 되는 패킷은 폐기합니다. Flgs, Fragme..

우선, 개념을 복습하기에 앞서 스케줄링이 어디서 쓰이는지 알고 학습해야 합니다. 라우터 내에 일어나는 포워딩 과정에서, Input port가 아닌 Output port에서 버퍼링, 즉 datagram buffer queueing이 발생했을 때 어떤 패킷을 내보낼지 결정할 때 사용하는 정책입니다. FIFO Queue를 사용할 때는, 큐에 도착한 순서대로 내보내는데요, 실제 상황에서는, 큐가 꽉 찼을 때 새로운 패킷이 도착했을 경우 버릴 패킷을 정해야 합니다. 1. tail drop: 새로 들어오는 패킷을 버립니다. 2. priority: 우선순위 규칙에 따라서, 새로 온 것을 버리거나 기존 것을 제거합니다. 3. random: 들어오는 패킷과 쌓인 큐를 랜덤하게 뽑아서 버립니다. 2번의 경우는 자체적인 정..

지금 우리가 무엇을 공부하고 있는지 기억해야 합니다. 라우터 내부에서 일어나는 것은? 포워딩 이죠. 포워딩은? Input port로 들어온 것을 적절한 output port로 이동시켜주는 일이구요. lookup, forwarding queueing input port의 트래픽을 다 합친 것보단, 스위치 패브릭의 처리 속도가 느리기 때문에 Queueing은 필연적입니다. 그리고 패킷 스위칭에서 Store and forward / Queueing delay and loss가 여기서 일어난다고 이해할 수 있겠습니다. Queueing이 일어나는 주된 상황인, Head of Line blocking을 알아봅시다. 좌측 그림에서, 1번 포트와 3번 포트는 동일한 output port로 포워딩 하려고 합니다. 그런데..

스위칭 패브릭은 Input buffer로 들어온 패킷을, 적절한 output buffer로 패킷을 옮겨주는 것을 의미합니다. 그리고 switching rate라는 개념이 있는데요, 스위칭 속도로 이해할 수 있겠습니다. 스위칭 패브릭에는 세 가지 종류가 있습니다. memory 방식은, 처음 등장한 라우터의 방식입니다. 메모리 대역폭에 영향을 받고, 한 시점에 하나의 포워딩만 동작합니다. Bus 방식은 중앙 데이터 버스를 여러 컴포넌트가 공유하는 방식인데요, 메모리 방식보단 조금 나은데, 충돌이나 경합이 발생할 수 있습니다. crossbar 방식은, 가장 빠른 스위치 아키텍처가 필요할 때 사용하는데요, bus의 대역폭 문제도 극복했고, 지금 가장 많이 이용되는 방법입니다.