티스토리

HSM 개발공부

검색하기

블로그 홈

HSM 개발공부

h-devnote.tistory.com/m

신수동탈곡기 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

BFS (너비우선탐색, Breadth-First Search) DFS (깊이우선탐색, Depth-First Search) 개요 대표적인 그래프 탐색 알고리즘 너비 우선 탐색 (BFS, Breadth-First Search): 노드들과 같은 레벨에 있는 노드를 먼저 탐색하는 방식. 한 단계씩 내려가면서 같은 단계에 존재하는 노드들을 먼저 순회함. 깊이 우선 탐색 (DFS, Depth-First Search): 노드의 자식들을 먼저 탐색하는 방식. 한 노드 의 자식을 타고 끝까지 순회한 후, 다시 돌아와 다른 노드들의 자식을 타고 내려가며 순회함. 파이썬의 딕셔너리와 리스트 자료구조를 활용해 그래프를 표현 가능함 BFS (너비우선탐색, Breadth-First Search) 구현 방문할 노드(need_visti_queue)들과 방문한 노드(visited_queue)들을 append하는 두 개의 큐를 활용함 graph = dic.. 공감수 0 댓글수 0 2022. 5. 30.
그래프 그래프 실제 세계의 현상이나 사물을 정점(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 그래프 종류 무방향 그래프 방향이 없는 그래프 간선을 통해 노드는 양방향으로 갈 수 있다 방향 그래프 간.. 공감수 0 댓글수 0 2022. 5. 30.
병합정렬 (Merge sort) 병합정렬 배열을 절반으로 잘라 나눈다. (분리 단계) 잘라서 나눈 배열을 재귀적으로 병합정렬 시킨다. (병합 단계) 예시로 이해 [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) 공감수 0 댓글수 0 2022. 4. 17.
퀵정렬 (Quick sort) 퀵정렬 기준점(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) 공감수 0 댓글수 0 2022. 4. 17.
동적계획법(Dynamic Programming)과 분할정복 (Divide and Conquer) 정의 동적계획법: 한 번 계산한 결과는 Memoization(메모이제이션) 기법을 통해 다시 계산하지 않는다. 전체 문제를 해결하기 위해 작은 단위의 문제를 해결하고, 해결한 작은 단위의 문제의 답을 통해 전체 문제를 해결한다. 상향식 접근법 (최하위 해답-작은 단위의 문제-을 구하고 단계적으로 올라가서 최상위 문제-전체 문제-를 해결한다.) 분할정복 문제를 나눌 수 없을 때 까지 나누어 잘게 나누어진 문제의 답을 합쳐 전체의 답을 얻는 알고리즘 하향식 접근법 (상위의 답을 구하기 위해 아래로 내려가면서 하위의 답을 구하는 방ㅎ식) 일반적으로 재귀적으로 구현 퀵 정렬, 병합정렬 공통점과 차이점 공통점: 문제를 잘게 쪼갠다. 차이점 동적 계획법은 부분 문제가 중복되지만 분할 정복은 중복되지 않는다. 동적 .. 공감수 0 댓글수 0 2022. 4. 10.
힙 (Heap) 개요 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전이진트리 완전이진트리(Complete Binary Tree): 노드를 삽입할 때 최하단 왼쪽 노드부터 삽입하는 트리. 사용하는 이유 최대값, 최소값을 빠르게 찾기 위함이다. 데이터를 마구마구 넣다가 중간에 그 순간의 최대값, 최소값을 빠르게 찾기 좋다. 힙의 구조 힙은 두 가지로 분류할 수 있다. 최대값을 찾기 위한 최대 힙(Max Heap)과 최소값을 찾기 위한 최소 힙(Min Heap) 힙은 두 가지 조건을 가긴 자료구조이다. 최대 힙의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. 최소 힙의 경우 각 노드의 값은 자식 노드가 가진 값보다 작거나 같다. 완전 이진 트리 형태를 가진다. 힙 vs 이진탐색트리.. 공감수 0 댓글수 0 2022. 3. 27.
이진탐색트리 (Binary Search Tree, BST) 개요 트리의 구조 트리: 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 이.. 공감수 0 댓글수 0 2022. 3. 27.
Proxy Server Proxy Server (프록시 서버)란? 서버와 클라이언트 사이에 위치하여 두 호스트를 중계해주는 역할을 주로 한다. 중계 역할 이외에도 캐싱 기능, 보안 기능을 제공하며 프록시가 어디에 위치하느냐에 따라 Forward Proxy, Reverse Proxy 두 종류로 나눌 수 있다. Forward Proxy vs. Reverse Proxy Forward Proxy 클라이언트측과 인터넷 사이에 위치한 프록시를 Forward Proxy라고 한다. 캐싱 기능 프록시에서 제공하는 기능의 첫 번째는 캐싱이다. 이 경우 클라이언트가 데이터를 요청하고 응답받는 순서는 클라이언트 → 프록시 → 인터넷 → 서버 → 인터넷 → 프록시 → 클라이언트 순으로 된다. 이 때 프록시 서버는 서버에서 클라이언트 측으로 전송한 데.. 공감수 0 댓글수 0 2022. 2. 27.
System Bus System Bus 컴퓨터를 구성하는 요소(CPU, I/O장치, Memory)들을 연결해주는 통로다. 여러 하드웨어들을 물리적으로 연결해 전기적 신호로 데이터를 주고받을 수 있게 해준다. 종류는 크게 세 가지로 데이터 버스, 주소 버스, 제어 버스가 있다. 데이터 버스 CPU와 다른 장치 사이에서 데이터가 오가는 통로. Memory와 I/O장치의 명령어를 CPU로 보내거나 CPU가 연산한 결과를 Memory, I/O장치로 보낼 때 사용하는 양방향버스다. 주소 버스 주소 버스는 물리적 주소를 특정하기 위해 사용하는 버스다. CPU나 입출력장치(DMA-enabled device)가 메모리(혹은 기억장치)에서 데이터를 읽거나 쓸 때 주소 버스에 데이터 버스에 실어보내는 값의 메모리 주소를 전달한다. CPU가 .. 공감수 0 댓글수 0 2022. 2. 13.
PIO(Programmed I/O)와 DMA(Direct Memory Access) 입출력 제어방식 컴퓨터와 입출력장치 사이에서 데이터가 오가는 방식을 입출력 제어방식이라고 하는데, 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가 입출력(데이터의 이동)을 담당한다는 점에서는 같지만, 입출력이 준비되었음을 인식하는 과정.. 공감수 1 댓글수 0 2022. 2. 13.
컴퓨터 시스템의 기본 컴퓨터의 동작 방식 컴퓨터가 동작하는 방식은 아래의 세 단계를 반복하는 것과 같다. 입력 장치 혹은 네트워크 어댑터를 통해 컴퓨터에 처리 요청이 들어온다. 메모리에 있는 명령을 읽어 CPU에서 실행하고 그 결과를 다시 메모리의 다른 영역에 기록한다. 메모리의 데이터를 하드디스크(HDD)나 SSD 등의 저장 장치에 기록하거나 네트워크를 통해 다른 컴퓨터에 전송하거나, 혹은 디스플레이 등의 출력 장치를 통해 결과를 보여준다. 이러한 순서를 반복해서 하나의 처리(기능)으로 정리한 것을 프로그램이라고 하는데, 프로그램은 크게 애플리케이션, 미들웨어, OS(운영체제)로 구분할 수 있다. 프로그램의 종류 애플리케이션: 사용자가 직접 사용하는 프로그램. 오피스, 계산기, 브라우저 등 미들웨어: 여러 애플리케이션이 공.. 공감수 0 댓글수 0 2022. 2. 8.
메모리계층 메모리 장치의 계층 구조 [레지스터] - [캐시 메모리] - [메모리] - [저장장치] 크기 작음 크기 크다 가격 비쌈 가격 저렴 속도 빠름 속도 느림컴퓨터의 동작 흐름 명령어를 바탕으로 메모리에서 레지스터로 데이터를 읽는다. 레지스터에 있는 데이터를 바탕으로 계산을 수행한다. 계산 결과를 메모리에 쓴다. 컴퓨터는 레지스터에서 계산하는 시간보다 메모리에 접근하는 데 걸리는 시간, 레이턴시가 극도로 느리다. (2)단계가 아무리 빨라도 (1)과 (3)단계에서 병목이 발생하여 전체 처리속도는 메모리에 읽고 쓰는 레이턴시와 별 차이가 없게 되버린다. 캐시 메모리 캐시 메모리를 통해 레지스터 안에서 계산하는 것과 메모리에 접근하는 것 양 쪽 처리 시간의 차이를 메운다. [레지스터] - [캐시 메모리]의 레이턴시가.. 공감수 0 댓글수 0 2022. 2. 6.
메모리관리 리눅스는 커널의 메모리 관리 시스템으로 시스템에 탑재된 메모리를 관리한다. 각 프로세스는 물론이고 커널 자체도 메모리를 사용한다. 메모리 통계정보 메모리 통계정보는 free 명령어로 확인할 수 있다. (base) [user@server ~]$ free total used free shared buff/cache available Mem: 65387028 16650384 7639664 233184 41096980 48005532 Swap: 32767996 6065624 26702372 (base) [user@server ~]$ (base) [user@server ~]$ free -h total used free shared buff/cache available Mem: 62G 15G 7.3G 227M 39.. 공감수 0 댓글수 0 2022. 2. 5.
네트워크의 구조 - 네트워크, 패킷, 대역폭 네트워크 두 대 이상의 컴퓨터가 연결되면 네트워크라고 할 수 있다. 네크워크를 사용하여 컴퓨ㅜ터 간의 데이터 전송, 웹 사이트 열람, 메일 송수신과 같은 일을 할 수 있다. 인터넷은 전 세계의 큰 네트워크부터 작은 네트워크까지 연결한 거대한 네크워크를 말한다. 패킷 웹사이트를 보거나 데이터를 주고받기 위해서는 규칙이 있어야 한다. 그 규칫에는 패킷을 사용한다. 패킷은 컴퓨터 간에 데이터를 주고받을 때 네크워크를 통해 전송되는 데이터의 작은 조각을 의미한다. 패킷을 사용하는 이유 큰 데이터를 패킷으로 나누지 않고 그대로 보내면 네트워크의 대역폭을 너무 많이 점유하여 다른 패킷의 흐름을 막는다. 대역폭 일반적으로 네트워크에서 이용 가능한 최대 전송 속도로, 정보를 전송할 수 있는 단위 시간당 전송량을 말한다.. 공감수 0 댓글수 0 2021. 6. 25.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.