이진 트리의 종류

이진 트리란? 각 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다 정 이진 트리 (Full Binary Tree) 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리이다 아래 그림처럼 3의 자식이 하나밖에 없는 경우는 정 이진 트리가 아니다 완전 이진 트리 (Complete Binary Tree) 마지막 레벨 직전의 레벨까지는 모든 노드들이 다 채워진 트리이다 마지막 레벨에서는 노드들이 모두 채워질 필요가 없더라도 왼쪽부터 오른쪽으로 노드들이 채워져야 한다 아래 그림처럼 마지막 레벨 직전까지의 레벨이 모두 채워졌지만 마지막 레벨에서 노드가 왼쪽에서부터 채워지지 않은 경우는 완전 이진 트리가 아니다 완전 이진 트리의 높이 완전 이진 트리에는 높이와 관련된 성질이 있다 완전 이진 트리 안에 n개의 ..

Direct Access Table과 Hash Table

다음과 같은 key-value쌍의 데이터를 저장하려고 한다 key-value쌍을 저장하는 기본적인 두 가지 방법에 대해 알아보자 Direct Access Table 배열의 인덱스로 바로 접근하는 방법이다 배열에서 인덱스를 순서가 아니라 key라고 생각하고 key-value쌍을 저장하는 방식이다 key를 바탕으로 배열의 인덱스에 데이터를 저장한다 '57'키는 배열의 57번 인덱스에 저장하고 '208'키는 배열의 208번 인덱스에 저장하고 '900'키는 배열의 900번 인덱스에 저장하면 된다 각 key에 해당하는 value를 알고 싶으면 해당 인덱스에 접근하면 된다 가장 큰 장점은 배열의 인덱스에 O(1)으로 바로 접근할 수 있다는 것이다 반면에 단점은 공간을 많이 낭비한다는 것이다 위의 예시를 보면 사용하..

더블리 링크드 리스트 연산의 시간 복잡도

더블리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자 더블리 링크드 리스트의 접근, 탐색 연산 더블리 링크드 리스트의 접근, 탐색 연산은 싱글리 링크드 리스트의 접근, 탐색과 똑같다 head 노드부터 하나씩 다음 노드로 가면서 원하는 위치에 접근하거나 원하는 데이터를 가진 노드를 찾는다 시간 복잡도는 리스트의 길이 n에 비례하므로 O(n)을 갖는다 더블리 링크드 리스트의 삽입, 삭제 연산 삽입 연산의 경우 특정 노드가 주어졌을 때, 특정 노드의 앞과 뒤 노드의 레퍼런스만 바꿔주면 된다 링크드 리스트의 길이와 상관없이 항상 일정한 시간이 걸리므로 시간 복잡도는 O(1)을 갖는다 삭제 연산도 마찬가지로 레퍼런스만 바꿔서 연결만 끊어주면 되므로 링크드 리스트의 길이와 상관없이..

싱글리 링크드 리스트 연산의 시간 복잡도

싱글리 링크드 리스트의 접근, 탐색, 삽입, 삭제 연산에 대하여 시간 복잡도를 알아보자 싱글리 링크드 리스트의 접근 연산 링크드 리스트의 접근 연산은 해당 노드에 바로 접근이 불가하다 head에서부터 차근차근 다음 노드로 가서 원하는 노드에 접근을 해야 한다 인덱스 x에 있는 노드에 접근하려면 head에서부터 x번 가야 한다 원하는 노드에 접근하는데 걸리는 시간이 몇 번째 인덱스인지에 비례하는 것이다 링크드 리스트 안에 있는 노드의 수를 n이라고 하면 마지막 노드에 접근하려면 head에서부터 총 n-1번을 가야 한다 그러므로 접근 연산은 최악의 경우 O(n)의 시간 복잡도를 갖는다 싱글리 링크드 리스트의 탐색 연산 링크드 리스트의 탐색 연산은 선형 탐색을 이용한다 가장 앞에서부터 다음 노드를 하나씩 보면..

시간복잡도 분할 상환 분석(동적 배열의 추가 연산)

동적 배열의 추가(append) 연산 동적 배열의 추가 연산의 시간 복잡도를 계산해보자 다음과 같은 배열에 새로운 데이터를 추가한다고 하자 두 가지 경우에 대해서 생각해 볼 수 있다 1. 배열에 남는 공간이 있을 때 이 경우는 그냥 빈 공간에 데이터를 저장하면 되므로 시간 복잡도는 O(1)이다 2. 배열이 꽉 찼을 때 이 경우는 기존의 배열보다 큰 배열을 만들고 기존 배열에서 새로운 배열로 값을 다 복사해야 된다 기존 배열의 0번 인덱스에 접근해서 값을 복사하고 새 배열의 0번 인덱스에 접근해서 값을 붙여 넣고... 이미 있던 n개의 데이터를 복사해야 되므로 O(n)이 되고 새로운 데이터를 추가해야 되므로 O(1)이 되어 총 O(n+1) = O(n)이 된다 정리 배열에 남는 공간이 있을 때: O(1) 배..

NAS Docker 컨테이너 시작시 자동 실행할 명령 설정하기

/root 디렉토리로 이동한다 vim 으로 .bashrc 파일 열어준다 G를 눌러 파일의 맨 끝으로 이동해 준다 o를 눌러 커서 위치를 바로 다음 줄로 옮기고 입력 모드를 시작한다 이제 컨테이너가 시작하면 자동으로 실행할 명령을 넣어주면 된다 필자의 경우 장고 서버를 실행해주는 명령을 넣었다 ESC를 누른 후 :를 누른 후 wq를 입력하고 빠져나온다 컨테이너를 재시작 하면 명령이 자동으로 실행되는 것을 확인할 수 있다

NAS Docker를 이용한 Django환경 세팅(2/2) - Django 설치

파이썬 설치 pyenv를 이용하여 파이썬을 설치한다 원하는 버전으로 설치하면 된다 pyenv install 3.8.9 더보기 다음과 같은 에러가 난다면 아래 코드를 입력하면 된다 apt install libbz2-dev apt install libreadline-dev apt-get install libssl-dev https://devlog.jwgo.kr/2019/06/05/must-installed-lib-when-installing-python-using-pyenv/ https://toughrogrammer.tistory.com/231 django라는 이름으로 가상 환경을 만들어 주겠다 pyenv virtualenv 3.8.9 django 홈 디렉토리로 가서 가상환경을 local로 설정한다 cd /..

NAS Docker를 이용한 Django환경 세팅(1/2) - 컨테이너 설정

Docker 컨테이너 생성 나스 도커에서 우분투 이미지를 이용할 것이다 더블클릭하여 컨테이너를 생성하자 이름을 설정하고 고급 설정에 들어간다 볼륨 탭에서 폴더 추가를 누르고 컨테이너와 프로젝트 폴더를 공유할 폴더를 하나 만들고 선택한다 마운트 경로는 /home으로 설정한다 이렇게 하면 우분투의 /home에 있는 파일을 나스에서 쉽게 관리할 수 있다 포트 설정에서 컨테이너 포트는 8000, 로컬 포트는 끌리는 숫자로 설정한다 컨테이너 포트는 장고에서 실행할 웹 서버 포트를 설정할 수 있고 로컬 포트는 나스에서 컨테이너로 요청을 보내주는 포트이다 나중에 로컬 포트는 포트 포워딩으로 연결을 해주어야 한다 컨테이너를 생성하고 터미널에 들어간다 우분투 설정 이제 차근차근 설치를 해보자 우선 우분투 업데이트, 기본..

리스트는 사실 배열?(3/3)

리스트 그렇다 파이썬 리스트는 사실 동적 배열이다 C의 배열을 이용해서 구현한 동적 배열이다 리스트를 하나 만들어 보았다 리스트는 동적 배열이므로 내부적으로는 C의 배열이 만들어져 있다 우리는 리스트에 마음대로 값을 추가할 수 있다 동적 배열이기 때문에 상황에 맞게 배열의 크기가 조절되기 때문이다 우리는 리스트 내부에 있는 배열의 크기를 모른다 현재 리스트에 담긴 데이터 수가 5개여도 내부적으로는 5개짜리 배열이 있을 수도 있고 6개짜리 배열이 있을 수도 있고 16개짜리 배열이 있을 수도 있다 현재 num 리스트에는 5개의 데이터가 저장되어 있다 리스트의 길이를 출력해보면 리스트의 길이는 5라고 나온다 실제 내부적으로 사용하고 있는 공간이 더 많을지라도 파이썬은 우리가 저장한 공간에 대해서만 알려준다 파..

리스트는 사실 배열?(2/3) - 정적 배열과 동적 배열

정적 배열 정적 배열은 크기가 고정되어 있는 배열이다 일반적으로 그냥 배열이라고 부르는 배열은 정적 배열이다 길이가 4인 배열에 값이 다 저장되어있는 상황 여기에 새로운 값 5를 넣고 싶으면 어떻게 해야 할까 길이가 5인 새로운 배열을 만들고 기존의 데이터들을 새로운 배열에 옮긴 뒤 5를 저장하면 된다 그런데 이는 너무 비효율적이다 그냥 배열 뒤에 넣으면 안 돼? 배열을 정의하게 되면 메모리에서 쓸 수 있는 공간을 찾아서 저장하려고 하는 데이터 타입과 저장하려는 데이터 수에 따라 연속적인 공간이 정해진다 우리는 배열 바로 뒷부분이 어떤 공간인지 모른다 사용해도 되는 공간인지 알 수 없기 때문에 배열 바로 뒤에 5를 추가하게 되면 위험하다 위험성을 예방하기 위해서 배열은 미리 공간을 고정해 놓는 것이다 그..