데이터과학 삼학년

삽입 정렬각 숫자를 적절한 위치에 삽입하는 정렬 기법들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번??? → O(N^2)의 시간 복잡도

선택 정렬가장 작은 것을 선택하여 앞으로 보내는 정렬 기법선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산 → O(N^2)의 시간 복잡도1회전: 첫 번째 자료 9를 두 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 4번 비교한다. 2회전: 두 번째 자료 6을 세 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 3번 비교한다. 3회전: 세 번째 자료 7을 네 번째 자료부터 마지막 자료까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다. 이 과정에서 자료를 2번 비교한다. 4회전: 네 번째 자료 9와 마지막에 있는 7을 비교하여 서로 교환한다.

스택 LIFO(Last In First Out) 나중에 들어온 녀석이 먼저 나가는 구조 OS에서 함수내에 잠깐 쓰이는 변수(휘발성)는 스택으로 처리됨 파이썬으로 stack 구현 class Stack: def __init__(self): self.stack = [] def pop(self): pop_value = self.stack[-1] self.stack = self.stack[:-1] return pop_value def push(self,value): self.stack.append(value) def is_empty(self): if len(self.stack) ==0: return True else : return False def check(self): return self.stack 큐 FI..

연결리스트 연결 리스트의 필요성 배열을 사용하는 경우 메모리 공간이 불필요하게 낭비될 수 있음 이때 연결 리스트를 사용하여 메모리 낭비 현상 방지 가능 배열 기반 리스트의 특징 배열로 만들었으므로 특정한 위치의 원소에 즉시 접근할 수 있다는 장점이 있음 데이터가 들어갈 공간을 미리 메모리에 할당해야 한다는 단점 원하는 위치로의 삽입이나 삭제가 비효율적 연결 리스트 구조체와 포인터를 함께 사용하여 구현 중간지점에 노드를 추가하거나 삭제할 수 있어야 함 필요할 때마다 메모리 공간을 할당받음 단일 연결 리스트 일반적으로 연결리스트의 시작노드를 Head라고 함 끝 노드의 next에는 null이 들어갈 수 있도록 연결 리스트 삽입 연결 리스트 삭제 연결 리스트의 특징 삽입과 삭제가 배열에 비해서 간단하다는 장점이..

자료구조 - 자료구조를 제대로 이해하지 못하면 불필요하게 메모리와 성능을 낭비할 여지가 있다! - 기본적인 자료구조들 선형구조 배열 연결 리스트 스택 큐 비선형 구조 트리 그래프 - 시간복잡도 알고리즘에 사용되는 연산 횟수 - 공간복잡도 알고리즘에 사용되는 메모리의 양 - 일반적으로 시간복잡도, 공간복잡도는 반비례 관계 시간복잡도를 표기할 때는 Big-O 표기법을 사용 공간복잡도를 표기할 때는 일반적으로 MB단위로 표기

시스템 프로그래밍 핵심 기술 - 시스템콜과 API 시스템 프로그래밍의 기반요소 시스템 콜 (System call) C 라이브러리 C 컴파일러 → 사용자 영역에서의 시스템 프로그래밍 시스템 콜 : 운영체제 리소스나 서비스 요청을 위해, 사용자 영역에서 커널영역으로 들어가는 함수 주요 시스템 콜 : read(), write(), open() 등 리눅스/유닉스는 C언어로 만들어져 있어서 시스템콜도 C언어로 구현 시스템 콜 구현 방법 eax 레지스터에 시스템 콜 번호 넣고 ebx 레지스터에 시스템 콜에 해당하는 인자값을 넣고 소프트웨어 인터럽트 명령을 호출하면서 0X80 값을 넘겨줌 CPU는 사용자 모드를 커널 모드로 바꿔줌 IDT(Interrupt Descripotr Table)에서 0X80에 해당하는 주소함..

파일 관련 쉘 명령어 - 하드링크 cp : 파일 복사 -r recursibe, f는 덮어쓸지 말지 묻지말고 y로 처리 윈도우의 바로가기 아이콘 같은 것 → 하드 링크, 소프트 링크 ln link.txt hard.txt → link.txt와 hard.txt 는 동일한 것(마치 cp 와 비슷) 차이 : 파일명이 다른데 inode의 번호가 같음(원래는 파일별 inode번호가 다르지) → cp 는 inode번호가 다름..structure 자체가 다를 것(복사) 하드링크 vs 소프트 링크 하드 링크는 완전 동일한 파일 생성(inode는 같음) 원본 파일을 삭제해도 하드링크로 만든 파일로 접근 가능 하드링크 파일 데이터 수정하면 원본 파일로 수정됨 하드링크의 장점 공간을 효율적으로 활용할 수 있다 (copy에 비해..

리눅스 파일 시스템 운영체제 복습(가상 파일 시스템) 하위단은 다양한 것을 받아오고, 상위단은 정해진 동작들을 수행하는 방식으로 구성 리눅스에서 모든 것은 파일이라는 철학으로 읽고 쓰는 것처럼 이루어져 있음 마우스, 키보드 같은 디바이스 관련 기술도 파일과 같이 다루어짐 즉, 모든 자원에 대한 추상화 인터페이스로 파일 인터페이스를 활용 input을 blackbox에 넣었을때 어떤 output이 나오는지 익히는 것 필요(추상화) 가상파일 시스템 파일 네임스페이스 window → C:/windows linux → 전역 네임스페이스(root 디렉토리 기본) 사용 /home/bdh/yomann.jpg 슈퍼블록, inode와 파일 슈퍼블록 : 파일 시스템의 정보 파일 : inode 고유값과 자료구조에 의해 주요정..