Computer Science (13) 썸네일형 리스트형 [Algorithm] 해시충돌 해결방법과 각각의 특징 해시 충돌이란?해시 테이블에서 서로 다른 키 값이 동일한 해시 값을 갖는 현상 주요 해결 방법체이닝개방 주소법체이닝 (Separate Chaining)원리해시 테이블의 각 버킷(bucket)이 연결 리스트, 동적 배열, 혹은 트리 구조를 가진다같은 해시값이 나면 그 버킷의 리스트에 추가특징삭제가 간단: 버킷 내부 자료구조에서만 제거하면 됨부하율(α = n / 버킷 수) > 1도 가능최악의 경우(모두 같은 해시값) 한 버킷에 n개가 몰려 O(n)장점구현 단순, 삭제 용이확장/축소 시 기존 요소 재배치 없이 버킷만 늘려 재해싱 가능단점포인터/메모리 오버헤드캐시 적중률 낮음(리스트 노드들이 흩어져 있을 수 있음)개방 주소법 (Open Addressing)원리충돌이 발생하면, 테이블 내부의 다른 빈 슬롯을 찾아.. [Algorithm] B Tree, B+ Tree 개념차이점삽입과 삭제 과정시간복잡도B Tree 개념B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 모든 키는 정렬돼 있고, 탐색·순차접근·삽입·삭제가 모두 O(log n)에 가능하도록 높이(h)를 매우 낮게 유지한다.이 구조는 디스크/페이지 I/O를 최소화하려고 고안됐고, DB와 파일시스템 인덱스의 표준이다. 최대 M개 자식을 가질 수 있는 B-Tree를 M차 B-Tree라고 부른다. [ DB 인덱스로 B(+)-트리를 채택하는 이유 ]메모리는 랜덤 접근이 빠르지만, 디스크/SSD는 페이지 단위 접근 비용이 크다.B-트리는 한 노드(=한 페이지)에 많은 키를 .. [Algorithm] 이진 최소 힙 Binary Min-Heap 1. 이진최소힙 개념2. 삽입과 삭제 과정3. 각 경우의 시간복잡도 정리개념완전이진트리 형태의 힙이며, 각 노드가 부모 보통 배열로 구현 (인덱스 i의 왼/오 자식 : 2i, 2i+1)* python의 heapq 모듈은 이진 최소 힙을 기반으로 동작함 삽입 과정def insert_min_heap(heap, value): heap.append(value) idx = len(heap) - 1 while idx > 0 and heap[(idx-1)//2] > heap[idx]: heap[idx], heap[(idx-1)//2] = heap[(idx-1)//2], heap[idx] idx = (idx-1)//2 heap = []values = [10, 7, 11, 5,.. (공부중) 객체지향 디자인패턴 OOP (객체지향 프로그래밍)특성캡슐화상속추상화다형성설계원칙 (SOLID)Single Responsibility Principle (SRP) : 클래스는 하나의 역할만 해야한다Open Close Principle (OCP)The Liskov Substitution Principle (LSP)Interface Segration Principle (ISP)Dependency Inversion Principle (DIP)디자인 패턴각 패턴이 무엇이며, 어떤 경우에 사용하는지 예시 정도 알아두기생성 패턴1) Singleton객체가 하나만 만들어져야 하는 경우 사용e.g) 전체 페이지에 똑같이 적용되는 다크모드클래스 안의 static이 아닌 변수나 메소드들은 객체가 생성될 때마다 메모리 공간을 새로 차지하지만st.. [운영체제] 프로세스와 스레드 꼬리 질문 에서 나온 내용 참고하여,[기본 질문에서 나올 수 있는 꼬리 질문들 공부](GPT3.5 내용이라 틀린 내용 있을 수 있음. 추후 검증 필요) > 프로세스와 스레드 차이실행 중인 프로그램을 프로세스라고 하고, 스레드는 프로세스 내에서 실행되는 기본 단위이다. > 멀티프로세싱과 멀티스레딩의 차이멀티프로세싱은 독립적인 프로세스를 여러 개 사용하여 작업을 병렬로 처리하는 방식이고,멀티스레딩은 한 프로세스 내에서 여러 스레드를 사용하여 작업을 병렬로 처리하는 방식이다.파이썬에서, CPU-bound 작업은 멀티프로세싱이 더 적합하고, I/O-bound 작업은 멀티스레딩이 더 적합하다.왜냐하면 파이썬 인터프리터는 GIL (Global Interpreter Lock)을 사용하여 동시에 하나의 스레드만 실행되도록 제한하.. 개발자 맥북 어떤 사양으로 사야할까? [목차]RAM (통합 메모리) 크기SSD 저장 장치M3 / M3 Pro / M3 Max 칩 차이CPU 코어 (성능 코어, 효율 코어) 개념GPU 코어 개념지금 내 컴퓨터 : 2018년도 구입한 6년 반 된 LG 그램 크롬 창 몇개, VSCode, 노션 띄워놓으면 가끔 디코나 게더에서 화면 공유나 마이크 입력 안될 때 있음노션 동시 작업할 때 렉 많이 걸림.갑자기 팬이 돌아가면서 소음이 나는 경우 허다하고, 충전기 없이는 1시간정도 쓸 수 있으려나.노트북을 바꿀 시기가 와서, 맥북 사양을 알아봤다. 앞으로 일하는 데 쓸만한 최소 사양이 어느정도 될지 하나씩 따져보자.RAM (Random Access Memory, Volatile Memory)활성 상태의 데이터와 프로그램을 일시적으로 저장하는데 사용하는 휘.. [네트워크] HTTP HTTP (HyperText Transfer Protocol)웹 서비스 통신(서버와 클라이언트 간의 데이터 송수신)에 사용되는 통신 규약, 애플리케이션 계층HTTP의 역사HTTP/0.9 : GET 메서드만 지원, HTTP 헤더 XHTTP/1.0 : 메서드, 헤더, 상태코드 추가요청 헤더 : http 버전이 생김응답 헤더 : 상태코드와 content-type이 생겨 html 파일 외 다른 타입의 파일도 전송단기커넥션 (Short-lived connection) : connection 하나당 1 요청, 1 응답만 처리 가능, 매번 새로운 연결로 성능 저하 (RTT 증가) 및 서버 부하 비용 증가RTT 개선 방법이미지 스플리팅 : 한 이미지를 background - position 이라는 CSS 설정을 통해 .. [네트워크] 비동기 메시지 전송하기 보이저엑스 백엔드 기술 질문 중 동시 사용자 1만명을 지원하는 채팅 서버를 어떻게 만들겠는가? 에 대해 공부하다가 "비동기 메시지 전달"에 대해 더 자세히 학습한 내용, 추후 실습 진행 예정 비동기 메시지 전달 방식메시지 생성 및 전송 : 클라이언트 또는 애플리케이션 서버가 메시지 생성하여 브로커 전달메시지 브로커의 역할 : 메시지 브로커가 메시지 수신하여 큐(queue)나 토픽(topic)에 일시적으로 저장, 수신자가 메시지를 처리할 준비가 될 때까지 보관메시지 수신 및 처리 : 수신자는 메시지 크로커에 연결되어 대기하다가 준비가 되면 브로커로부터 메시지를 가져와서 처리 ex) 다른 사용자에게 메시지를 전달하거나 데이터베이스에 저장비동기 메시지 전달이 효율적인 이유비동기성송신자와 수신자가 동시에 작동할.. 이전 1 2 다음
