본문 바로가기

CS

 (71)
5. 해쉬 테이블(Hash Table) 해쉬 테이블(Hash Table) 해쉬 구조 key에 value를 저장하는 데이터 구조 파이썬에서는 딕셔너리 타입을 사용하면 돼서 구현할 이유가 없음 용어 Hash : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수 : key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값 또는 해쉬 주소 : key를 해싱 함수로 연산해서, 해시 값을 알아내고, 이를 기반으로 해시 테이블에서 해당 key 에 대한 데이터 위치를 일관성 있게 찾을 수 있음 슬롯 : 한 개의 데이터를 저장 할 수 있는 공간 저장할 데이터에 대해 key를 추출할 수 있는 별도 함수도 존재할 수 있음 예 hash_table = list([i for i in..
4. 링크드 리스트(Linked List) 링크드 리스트(Linked List) 링크드리스트 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 파이썬은 리스트 타입이 링크드리스트 기능을 모두 지원 노드 : 데이터 저장 단위 (데이터 값, 포인터)로 구성 포인터 : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 갖고 있음 예 Node 구현 보통 파이썬에서 링크드 리스트 구현 시, 파이썬 클래스를 사용함 class Node : def __init__(self, data) : self.data = data self.next = None class LinkedList : def __init__(self, data, nex..
3. 배열(Array) 배열(Array) 배열 사용 같은 종류의 데이터를 효율적으로 관리 같은 종류의 데이터를 순차적으로 저장 장점 : 빠른 접근 가능(인덱스 번호로 접근) 단점 : 데이터 추가, 삭제가 어려움 파이썬 배열 파이썬은 리스트로 배열 구현 가능 data_list = [1,2,3,4,5] 연습 dataset = ['Braund, Mr. Owen Harris', 'Cumings, Mrs. John Bradley (Florence Briggs Thayer)', 'Heikkinen, Miss. Laina', 'Futrelle, Mrs. Jacques Heath (Lily May Peel)', 'Allen, Mr. William Henry', 'Moran, Mr. James', 'McCarthy, Mr. Timothy J'..
2. 스택 (Stack) 스택 - 데이터를 제한적으로 접근(한 쪽 끝에서만 자료를 넣거나 뺄 수 있음) - 가장 나중에 쌓은 데이터를 가장 먼저 빼내는 데이터 구조 - 컴퓨터 내부 프로세스 구조의 함수 동작 방식 - push() : 데이터를 스택에 넣기 - pop() : 데이터를 스택에서 꺼내기 data_stack = list() data_stack.append(1) data_stack.append(2) print(data_stack) print(data_stack.pop()) [1, 2] 2 stack_list = list() def push(data): stack_list.append(data) def pop(): data = stack_list[-1] # -1 : 마지막 데이터 del stack_list[-1] return..
1. 큐(Queue) 큐 queue - 줄을 서는 것과 비슷 - 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조 FIFO, LILO, 스택과 반대 - 멀티테스킹을 위한 프로세스 스케줄링 방식 구현에 많이 사용됨 - Enqueue : 큐에 데이터를 넣는 기능 - Dequeue : 큐에서 데이터를 꺼내는 기능 파이썬 라이브러리 - Queue() : 가장 일반적인 큐 자료구조 - LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조 - PriorityQueue() : 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터 출력 Queue import queue data_queue = queue.Queue() data_queue.put("str") data_queue.put(123) print(data_queue..
유닉스 프로세스 * 메모리 레이아웃 * getpid, getppid 시스템콜 #include pid_t getpid(void); // returns : the process ID of the calling process pid_t getppid(void); // returns : the parent process ID of the calling process * fork 시스템콜 #include pid_t fork(void) ; // returns : 0 in child, process ID of child in parent, -1 on error * exec family #include int execl (const char *pathname, const char *arg0, ... /*NULL*/); int..
14. 유닉스 - 소켓 Internet model (TCP/IP protocol suite) 소켓은 tcp ip를 사용하기 위한 인터페이스 툴임 네트워크는 osi 7계층 하드웨어레이어, 데이터링크계층, 네트워크계층, 전송계층, 세션계층, 표현계층, 응용계층 tcp ip에서는 전송계층 위에 응용계층 하나만 있음 응용 계층에서 프로세스가 돌아감 그 밑에 전송계층에 tcp 프로토콜 udp 프로토콜 이 있고 그 밑에 ip프로토콜이 있고 그 밑에 데이터링크 레이어에 이더넷 토큰링 토큰버스 이렇게 있음 보통 이더넷을 사용함 우리는 컴퓨터에서 돌아가는 여러 개의 프로세스가 있는데 그 중에서 한 개의 프로세스로 인터넷에 연결된 원격진행이 되는 여러개의 프로세스 중에서 한 개의 프로세스와 소통하기를 원함 내 프로세스가 왼쪽이고 통신할 컴퓨터의..
13. 유닉스 IPC - semaphore, shared memory The semop(2) system call #include int semop(int semid, struct sembuf semoparray[], size_t nops); // returns : 0 if ok, -1 on error semop 세마포어의 오퍼레이션 인데 두개가 있음 wait(p) signal(v) 이 두 개의 오퍼레이션을 semop이라는 시스템콜로 구현을 함 첫번째 semid가 가리키는 세마포어 set이 있고 그 안에 세마포어가 여러 개 있음 semop 함수는 atomic함 id로 가리키는 세마포어 set에 여러 개 sem이 있는데 각 sem에 대해서 wait나 signal 오퍼레이션 수행하는데 그게 여러개 있음. 그것들을 각각 atomic 하게 실행함 wait - signal 세마포어..

티스토리툴바