교대최소제곱법

이 글은 이전 글인 "[pintOS] 운영체제와 cpu 아키텍쳐의 관계 그리고 펭귄" 의 후속 글 입니다 재밌는 이야기를 보기 전에 이전 글을 보면 더 재밌습니다! https://changjohwang.tistory.com/53 여기서는 정말 재밌는 이야기를 할 것이다 windows와 리눅스 원래 운영체제 시장은 x86 아키텍쳐를 사용한 마이크로 소프트의 Windows가 독점하다시피 하고 있었다 운영체제 = windows가 성립하던 시대였다 하지만 unix의 자손들이 하나 둘 떠오르기 시작되었고 리눅스는 그 중 최고라고 볼 수 있다 우리가 잘 아는 안드로이드, 타이젠도 이 리눅스 기반의 모바일 운영체제이다! 여기에 unix기반의 macOS까지 해서 windows, macOS, linux 삼대장의 시대가 ..

문제 정의 우리가 만든 pintOS는 ec2의 우분투 x86_64 환경 위에서 작동한다 amazon/ubuntu/images/hvm-ssd/ubuntu-bionic-18.04-amd64-server-20230329 이미지를 보면 우분투인 것은 알겠는데 뒤에 amd64가 붙어 있는 것을 볼 수 있다. 그 전에는 운영체제는 소프트웨어고 cpu아키텍쳐는 하드웨어라 연관성을 못 느꼈는데 최근 pintOS를 만들면서 이 둘의 관계가 궁금해졌다 + 사실 친구가 리눅스 마스코트인 턱스가 귀엽다는 말을 해서 리눅스가 궁금해졌다 일단 우분투란 무엇일까? = 우분투는 debian 기반의 linux 배포판이다 그럼 debian이란? = 커뮤니티인 데비안 프로젝트에서 개발하고 있는 linux 배포판 아무튼 우분투는 linux..

2019년 유해사이트를 막는다는 명목으로 HTTPS를 차단하는 사건이 있었다. 당시에는 그냥 HTTPS가 막혀서 https가 들어가는 주소는 우회해야 되는구나로 이해했지만 이번에 네트워크를 공부하면서 사건의 전말을 이해 할 수 있었다. HTTPS 차단 사건의 시작 대한민국은 국민들의 유해 사이트 접근을 막기 위해 방통위 주관으로 http 주소로 접근을 시도하면 도메인 주소를 IP로 DNS resolution 할 때 도메인 주소에 유해 사이트의 도메인이 포함되어 있으면 warning.or.kr로 리턴하는 방식으로 납치(?)했다 이를 DNS Sinkhole이라고 부른다 DNS Sinkhole은 DNS와 transaction하는 과정에서 생기기 때문에 그냥 DNS를 싱크홀이 없는 DNS로 바꿔주면 손쉽게 우회..

디스크 조각모음 보조 기억 장치의 단편화를 해결하기 위한 최적화 프로그램 과거에는 저장장치가 구리고 단편화 문제가 실제로 체감되었기 때문에 디스크 조각모음 프로그램을 따로 설치하여 돌려주고는 했었다. 최근에는 이런 사설 프로그램을 설치할 필요 없이 기본적으로 운영체제에서 해결해준다. 찾아보니까 매주 자동으로 하드디스크를 정리해주는 모양이다. 과거에는 디스크 조각모음이 중요했으나 캐시 메모리의 대형화, 자기 디스크에 대한 기술 발전으로 처리 속도, 저장 용량 등의 성능이 향상되면서 중요성이 다소 떨어졌다. SSD는 디스크 조각모음이 필요없다 정확히는 플래시 메모리 저장매체들은 디스크 조각 모음이 필요없다. 그 이유는 메모리 할당 과정을 통해 알 수 있는데 malloc 구현을 하다보면 find_fit라는 함..

파이썬 라이브러리는 어떻게 구현할까? 무조건 작은 숫자가 0번 인덱스, 1번이 트리의 루트는 고정이다. 그리고 부모가 인덱스 k일 때 2k의 값은 2k+1보다 크다는 공식을 통해 구현된다 + 23.11.14 왜 트리의 루트를 0번 인덱스부터 시작하지 않을까? 루트를 1에서 시작하면 부모 노드를 찾을 때 단순히 i // 2만 해주면 되는 반면 루트를 0에서 시작하면 (i-1) // 2를 해야하는 번거로움이 있다. 삽입 연산은 → heappush 가장 마지막 인덱스에 값을 넣고 (현재 인덱스) // 2로 부모 인덱스를 찾아서 비교한다 이때 비교의 기준이 작은 것이 올라가면 최소힙, 큰 것이 올라가면 최대힙이 된다. 삭제 연산은 → heappop 파이썬 같은 경우 이미 하나를 빼서 0번 인덱스에 넣어놓는다 0..

B- tree가 무엇인가? 자료구조 중 하나 이진트리와 다르게 하나의 노드에 최대 M개의 자식을 가지는 트리 예를들어 값이 [10, 20]이 있으면 10보다 작은 서브트리, 10과 20 사이의 서브트리, 20보다 큰 서브트리 이렇게 3개의 자식이 생기는 트리가 B-트리이다. 삽입의 경우 M개의 제한을 걸어두고 값이 M개 이상이 되면 (노드는 최대 M-1개 까지 값을 가질 수 있다) 분할이 이루어진다 분할 과정은 가운데 값이 부모 노드로 올라가서 합쳐지는 방식으로 부모노드도 초과할 경우 계속 올라가는 방식으로 삽입이 진행된다 삭제는 더 어렵다, 자세한 것은 블로그 참조 [자료구조] 그림으로 알아보는 B-Tree [자료구조] 그림으로 알아보는 B-Tree B트리는 이진트리에서 발전되어 모든 리프노드들이 같은..

해시 함수란? 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 수학적 연산을 통해 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값을 해시 코드, 해시라고 한다. → 데이터를 효율적으로 관리하기 위한 방법 + 해시값(hash value) = 해시 코드(hash code) = 다이제스트(digest) = 해시(hash) 그럼 해시 테이블은? 바꾸기만 하면 의미가 없기 때문에 키와 값을 연결해 놓은 테이블이다. 왜 쓰나요? 무결성 검사, 비밀번호 저장 같은 보안이 필요한 경우 사용 해시 테이블의 종류 Direct Addressing Table 가장 간단한 해시테이블, 최대 키 값만큼 리스트를 만들어서 기억하는 방식 (DP에서 활용하는 방식) → 메모리 낭비가 심하다 Hash ..

자료구조 종류 배열(리스트) 링크드 리스트 스택 큐 우선순위 큐 그래프 인접 행렬 그래프 → 2차원 배열 지도나 행렬이 주어졌을 때 ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] 인접 리스트 그래프 → 링크드 리스트 일부 간선의 정보만 주어졌을 때 ex) [(a, b, d1), (a, c, d2), (b, d, d3)] 트리 이진트리 힙 트리의 변형으로 최대, 최소 값을 찾기 위해 고안됨 → 우선순위 큐 해쉬 + 해쉬와 링크드 리스트 링크드는 리스트 안에 각자 다음 노드를 표시해 놓는 것 해쉬는 키와 밸류를 이어 놓은 테이블을 따로 생성하는 것 정렬 종류 선택 정렬, selection sort 전체를 순회하면서 가장 작은 값을 저장해서 순회가 끝났을 때 저장 시간복잡도 무조건 O(n..