취미와 밥줄사이

공간 복잡도 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현할 수 있다. 시간 복잡도: 얼마나 빠르게 실행되는지 공간 복잡도: 얼마나 많은 저장 공간이 필요하는지 좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다. 시간과 공간은 반비례적인 경향이 있다. 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함 총 필요 저장 공간 고정 공간(알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수(일정한 양의 메모리 공간) 가변 공간(알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간 입력값의 크기에 비례해서 알고리즘이 사용하는 메모리 공간을 의미 S(P) = c + Sp(n) c: 고정공간 Sp(n)SP(n): 가변 공간 고정 공간은 상수이므로 공간 복잡도는 ..

트리(Tree)란 트리는 노드로 이루어진 자료구조 트리는 하나의 루트 노드를 갖는다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 노드들은 특정 순서로 나열될 수 도 있고 그럴 수 없을 수도 있다. 각 노드는 부모 노드로의 연결이 있을 수도 있고, 없을 수도 있다. 각 노드는 어떤 자료형으로 표현 가능하다. 비선형 자로구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도 그래프의 한 종류 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph) DAG(Directed Ac..

배열(Array)이란? 배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료구조 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조 연속적인 메모리 공간에 순차적으로 데이터를 저장 배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다. 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다. 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있따. 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)가 되는 것이다. 배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다. 배열의 특징 추가적으로 소모되는 메모리 양(=overhead)가 거의 없다 Cache hit rate가 높다. cache hit ratio: 적중률 = (캐시히트 횟수)/(전체 참조횟수..

선형 검색(Linear Search) 순차 검색(Sequential Search)이라고도 한다. 데이터가 모인 집합(배열, lined List)의 처음부터 끝까지 하나씩 순서대로 비교하며 원하는 값을 찾아내는 알고리즘 데이터를 정렬할 필요가 없음 데이터의 양이 많아지면 검색에 소요되는 시간도 비례하여 많아지고, 하나씩 일일이 비교하기 때문에 비효율적이라는 단점이 있음 10개의 데이터가 있을 경우 마지막에 있는 데이터를 찾는 경우 10번의 비교가 필요하지만 100만개의 데이터가 있는경우 100만번의 비교가 필요함 선형검색은 linked list에서 자주 쓰임 def linear_search(sequence, key): for i in range(len(sequence)): if sequence[i] == ..

메인보드 cpu를 비롯해 컴퓨터의 주요 구성부품인 메모리카드(ram), 그래픽카드 등을 서로 연결해주는 뼈대, 혈관, 신경계 같은 존재 각 부품들이 하나로 연결되어 온전한 컴퓨터의 기능을 할 수 있게 해주는 회로가 존재함 이 회로들을 통해서 전기를 각 부품에게 배분해주는 역할을 하는 부품이 메인보드 메인보드가 없으면 cpu가 램으로 처리된 정보를 보낼 수 없음 메인보드 안에는 bios라는 일종의 작은 운영체제가 들어있음 메인보드에는 램을 꽂을 수 있는 램슬롯과 cpu 슬롯, 내장 사운드 카드와 내장 랜카드, 외장 그래픽 카드, 사운드 카드, tv 수신 카드 등을 꽂을 수 있는 pci 슬롯을 제공함 메인보드는 칩셋에 따라 사용할 수 있는 기능이 다름 컴퓨터의 모든 장치는 직접적으로든 간접적으로든 메인보드에..

캐시 자주 사용하는 데이터나 값을 미리 복사해 놓는 임시 장소 캐시는 저장 공간이 작고 비용이 비싼 대신 빠른 성능을 제공한다. Cache를 사용하면 좋은 상황 접근 시간에 비해 원래 데이터를 접근하는 시간이 올래 걸리는 경우 반복적으로 동일한 결과를 돌려주는 경우( 이미지 or 썸네일 ) 캐시에 데이터를 미리 복사해 놓으면 계산이나 접근시간 없이 더 빠른 속도로 데이터에 접근할 수 있음 반복적으로 데이터를 불러오는 경우, 지속적으로 DBMS나 혹은 서버에 요청하는 것이 아니라 메모리에 데이터를 저장하였다가 불러다 쓰는 것을 의미 지역성(locality)을 이용하여 데이터 접근 속도를 빠르게 하기 위한 메모리 계층 cpu와 주기억장치 간의 속도차로 발생하는 cpu idle time을 최소화하기 위해 캐시..

클럭 컴퓨터는 타이밍에 맞춰서 움직입니다. 그 타이밍은 0과 1(전기적 신호) 전기가 들어오면 1, 전기가 들어오지 않으면 0이라는 신호를 만들어서 데이터를 처리하고 데이터를 저장한다. CPU는 메인보드에서 공급받는 전기를 신호로 받아서 연산 작업을 진행함 직선으로 쏟아 오르는 부분이 1, 떨어지는 부분이 0 CPU의 클럭이 높다는 것은 한 번 움직이는 타이밍(1초)에 더 많은 양의 데이터를 처리한다는 의미("Hz") 1Hz = 1개의 전기신호 4Hz = 4개의 전기신호 1MHz = 100만 개의 전기 신호 cpu와 같이 전기회로를 통해 전기 신호(클럭)이 발생하게 되면 열이 발생함 많은 전기 신호가 오고 갈수록 그만큼 성능은 올라갈 수 있지만 더 많은 열을 냄 싱글 코어에 더 높은 클럭(전기 신호)를 ..

DHCP (Dynamic Host Configuration Protocol) DHCP는 Dynamic Host Configuration Protocol의 약자 호스트이 IP주소와 각종 TCP/IP 프로토콜의 기본 설정을 클라이언트에게 자동으로 제공해주는 프로토콜 DHCP에 대한 표준은 RFC 문서에 정의되어 있으며, DHCP는 네트워크에 사용되는 IP주소를 DHCP 서버가 중앙집중식으로 관리하는 클라이언트/서버 모델을 사용하게 됩니다. 네트워크 안에 컴퓨터에 자동으로 네임 서버 주소, ip address, 게이트웨이 주소를 할당해주는 것을 의미 동적 호스트 설정 프로토콜 ip주소와 게이트웨이 또는 네임서버 주소의 정보를 자동으로 할당해주는 프로토콜을 의미 DHCP의 장점 ip 설정이 자동으로 분배받아 사..