HSM 개발공부

개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (BFS, Breadth-First Search): 노드들과 같은 레벨에 있는 노드를 먼저 탐색하는 방식. 한 단계씩 내려가면서 같은 단계에 존재하는 노드들을 먼저 순회함. 깊이 우선 탐색 (DFS, Depth-First Search): 노드의 자식들을 먼저 탐색하는 방식. 한 노드 의 자식을 타고 끝까지 순회한 후, 다시 돌아와 다른 노드들의 자식을 타고 내려가며 순회함. 파이썬의 딕셔너리와 리스트 자료구조를 활용해 그래프를 표현 가능함 BFS (너비우선탐색, Breadth-First Search) 구현 방문할 노드(need_visti_queue)들과 방문한 노드(visited_queue)들을 append하는 두 개의 큐를 활용함 graph = dic..

그래프 실제 세계의 현상이나 사물을 정점(vertex) 또는 노드(node)와 간선(edge)으로 표현하기 위해 사용함 용어 무방향 그래프 정점의 차수: 하나의 노드에 인접한 노드 수 방향 그래프 진입 차수: 외부에서 들어오는 간선 수 진출 차수: 외부로 나가는 간선 수 경로 길이: 경로를 구성하기 위해 사용된 간선 수 단순 경로: 처음 노드와 끝 노드를 제외하고 종복된 노드가 없는 경로 A → B → D (O) A → C → D (O) A → B → A → C → D (X) A → B → D → C → A (O) 사이클: 단순 경로 중에서 시작 노드와 끝 노드가 동일한 경우 A → B → C → A 그래프 종류 무방향 그래프 방향이 없는 그래프 간선을 통해 노드는 양방향으로 갈 수 있다 방향 그래프 간..

병합정렬 배열을 절반으로 잘라 나눈다. (분리 단계) 잘라서 나눈 배열을 재귀적으로 병합정렬 시킨다. (병합 단계) 예시로 이해 [2, 8, 6, 4] [2, 8], [6, 4] [2], [8] | [6], [4] 앞 두 배열을 정렬하여 합친다. -> [2, 8] 뒤 두 배열을 정렬하여 합친다. -> [4, 6] [2, 8]과 [4, 6]을 합친다. 2 [2] 남은 배열: [8], [4, 6] 8 > 4 -> [2, 4] 남은 배열: [8], [6] 8 > 6 -> [2, 4, 6] 남은 배열: [8] [2, 4, 6, 8] 구현 from turtle import right def split(array): if len(array)

퀵정렬 기준점(pivot이라고 부름)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다. 왼쪽 오른쪽으로 나눈 데이터들을 동일한 함수를 호출하여 나누는 작업을 반복한다. 작 작업을 통해 리턴받은 데이터를 결합하면 정렬된 데이터를 얻을 수 있다. 구현 def qsort(array): if len(array) pivot: right.append(array[idx]) else: left.append(array[idx]) return qsort(left) + [pivot] + qsort(right) if __name__ == "__main__": result = qsort([4, 7, 134, 53, 12, 678, 432, 1, 8]) print(result)

정의 동적계획법: 한 번 계산한 결과는 Memoization(메모이제이션) 기법을 통해 다시 계산하지 않는다. 전체 문제를 해결하기 위해 작은 단위의 문제를 해결하고, 해결한 작은 단위의 문제의 답을 통해 전체 문제를 해결한다. 상향식 접근법 (최하위 해답-작은 단위의 문제-을 구하고 단계적으로 올라가서 최상위 문제-전체 문제-를 해결한다.) 분할정복 문제를 나눌 수 없을 때 까지 나누어 잘게 나누어진 문제의 답을 합쳐 전체의 답을 얻는 알고리즘 하향식 접근법 (상위의 답을 구하기 위해 아래로 내려가면서 하위의 답을 구하는 방ㅎ식) 일반적으로 재귀적으로 구현 퀵 정렬, 병합정렬 공통점과 차이점 공통점: 문제를 잘게 쪼갠다. 차이점 동적 계획법은 부분 문제가 중복되지만 분할 정복은 중복되지 않는다. 동적 ..

개요 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전이진트리 완전이진트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 삽입하는 트리. 사용하는 이유 최대값, 최소값을 빠르게 찾기 위함이다. 데이터를 마구마구 넣다가 중간에 그 순간의 최대값, 최소값을 빠르게 찾기 좋다. 힙의 구조 힙은 두 가지로 분류할 수 있다. 최대값을 찾기 위한 최대 힙(Max Heap)과 최소값을 찾기 위한 최소 힙(Min Heap) 힙은 두 가지 조건을 가긴 자료구조이다. 최대 힙의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. 최소 힙의 경우 각 노드의 값은 자식 노드가 가진 값보다 작거나 같다. 완전 이진 트리 형태를 가진다. 힙 vs 이진탐색트리..

개요 트리의 구조 트리: Node와 Branch를 이용해서 사이클을 이루지 안호록 구성한 데이터 구조 트리 중 이진 트리(Binary Tree) 형태의 구조로 탐색(검색) 알고리즘 구현을 위해 자주 사용 용어 Node: 트리에 데이터를 저장하는 기본 요소 (데이터, 연결된 다른 node에 대한 branch 정보 포함) Root node: 트리의 최상위 노드 Level: Root node를 레벨 0으로 봤을 때 하위 node들의 깊이를 나타냄 Parent node: 어떤 노드의 하위 레벨에 연결된 노드 (위쪽 노드) Child node: 어떤 노드의 상위 레벨에 연결된 노드 (아래쪽 노드) Leaf node: Child node가 없는 노드 Depth: 트리에서 node가 가질 수 있는 최대 level 이..

Proxy Server (프록시 서버)란? 서버와 클라이언트 사이에 위치하여 두 호스트를 중계해주는 역할을 주로 한다. 중계 역할 이외에도 캐싱 기능, 보안 기능을 제공하며 프록시가 어디에 위치하느냐에 따라 Forward Proxy, Reverse Proxy 두 종류로 나눌 수 있다. Forward Proxy vs. Reverse Proxy Forward Proxy 클라이언트측과 인터넷 사이에 위치한 프록시를 Forward Proxy라고 한다. 캐싱 기능 프록시에서 제공하는 기능의 첫 번째는 캐싱이다. 이 경우 클라이언트가 데이터를 요청하고 응답받는 순서는 클라이언트 → 프록시 → 인터넷 → 서버 → 인터넷 → 프록시 → 클라이언트 순으로 된다. 이 때 프록시 서버는 서버에서 클라이언트 측으로 전송한 데..

System Bus 컴퓨터를 구성하는 요소(CPU, I/O장치, Memory)들을 연결해주는 통로다. 여러 하드웨어들을 물리적으로 연결해 전기적 신호로 데이터를 주고받을 수 있게 해준다. 종류는 크게 세 가지로 데이터 버스, 주소 버스, 제어 버스가 있다. 데이터 버스 CPU와 다른 장치 사이에서 데이터가 오가는 통로. Memory와 I/O장치의 명령어를 CPU로 보내거나 CPU가 연산한 결과를 Memory, I/O장치로 보낼 때 사용하는 양방향버스다. 주소 버스 주소 버스는 물리적 주소를 특정하기 위해 사용하는 버스다. CPU나 입출력장치(DMA-enabled device)가 메모리(혹은 기억장치)에서 데이터를 읽거나 쓸 때 주소 버스에 데이터 버스에 실어보내는 값의 메모리 주소를 전달한다. CPU가 ..

입출력 제어방식 컴퓨터와 입출력장치 사이에서 데이터가 오가는 방식을 입출력 제어방식이라고 하는데, DMA와 PIO는 이 입출력 제어방식들 중 하나이며 총 네 가지 방식이 있다. 대형 컴퓨터에서 사용하는 Channel에 의한 I/O를 제외한 세 가지 방식에 대해 알아본다. 제어방식 CPU 관여 여부 프로그램에 의한 I/O(PIO, Program I/O) O Intrrupt에 의한 I/O O DMA(Direct Memory Access)에 의한 I/O X Channel에 의한 I/O X Programmed I/O vs Interrupt I/O(Interrupt Initiated I/O) 이 두가지 입출력 방식은 CPU가 입출력(데이터의 이동)을 담당한다는 점에서는 같지만, 입출력이 준비되었음을 인식하는 과정..