w3 요약
자료구조
여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의한 것 → 데이터의 효율적인 관리 및 사용을 위해 자료구조가 필요함
데이터: 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
종류
- 단순구조
- 자료값 사용을 위해 T/F, 정수, 실수, 문자 및 문자열 같이 컴퓨터가 기본적으로 제공하는 자료형
- 선형구조
- 자료를 구성하는 데이터를 순차적으로 나열시킨 형태로 자료들간의 관계가 1:1인 자료
- 비선형구조
- 하나의 자료 뒤에 여러 개의 자료가 존재할 수 있는 것으로 계층 구조나 망 구조로 이루어짐
- 파일구조보조기억 장치에 데이터가 실제로 기록되는 형태로 메모리에 한 번에 올릴 수 없는 대용량을 다룸
- 서로 관련있는 필드로 구성된 레코드 집합인 파일에 대한 자료구조
스택 LIFO
데이터 삽입과 추출이 한쪽 방향만 가능한 구조
push: 스택에 데이터를 넣는 작업
pop: 스택에서 데이터를 꺼내는 작업
큐 FIFO
양쪽 모두 뚫려있는 구조
데이터 삽입과 추출이 양방향으로 가능한 구조
리스트
구현 방법에 따라 순차리스트와 연결리스트로 구분
순차리스트: 순차적인 메모리 공간을 할당하여 구현하는 리스트, 보통 배열로 구현
연결리스트: 데이터가 불연속 공간에 흩어져있는 상태에서 다음 데이터의 위치 정보를 보유하게 하는 자료구조. 메모리 동적할당 기법을 사용하여 구현
트리
계층적인 구조를 나타내는 비선형 자료구조로 그래프의 특수한 형태
하나의 루트노드를 가지고 있으며 각 노드는 0개 이상의 자식 노드를 가질 수 있음 → 데이터를 계층적으로 표현 가능
정렬 알고리즘
- 선택 정렬: 선택된 값과 나머지 데이터 중에 비교하여 알맞은 자리를 찾는 알고리즘
- 삽입 정렬: 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 다시 적당한 곳으로 삽입하는 알고리즘
- 버블 정렬: 인접한 두 수를 비교하여 오름차순/내림차순으로 정렬하는 알고리즘
- 병합 정렬: 둘 이상의 부분집합으로 가르고 각 부분 집합을 정렬한 다음 부분 집합들을 다시 정렬된 형태로 합치는 알고리즘
- 힙 정렬: 트리 기반으로 최대 힙 트리/최소 힙 트리를 구성해 정렬을 하는 알고리즘
- 퀵 정렬: 데이터 집합 내에 임의의 기준값을 정하고 해당 피봇으로 집합을 두 개의 부분 집합으로 나누어 정렬하는 알고리즘
컴퓨터 구조
컴퓨터가 효율적으로 작동할 수 있도록 하드웨어 및 소프트웨어의 기능을 고안하고 구성하는 방법
폰 노이만 구조
컴퓨터 핵심 기능(연산, 제어, 저장)이 필요하다고 생각함. 근대의 컴퓨터는 연산과 제어를 위해 중앙처리장치를, 저장을 위해 기억장치를 사용. 장치 간 데이터나 제어 신호를 교환할 수 있도록 버스라는 전자 통로를 사용
- CPU: 산술논리장치, 제어장치, 레지스터
- 기억장치: 컴퓨터가 동작하는데 필요한 여러 데이터를 저장하기 위해 사용. 주기억장치와 보조기억장치로 나뉨
- 버스: 컴퓨터 부품들 간, 컴퓨터 간 신호 전송 통로
- 명령어 집합 구조: 어떤 구조의 메모리와 호환이 가능한지 명시. 프로그램 실행 시 기계어 명령어들을 CPU가 읽기 및 처리
Intel x86-64
레지스터: CPU가 데이터를 빠르게 저장하고 사용할 때 이용하는 보관소
- 범용 레지스터앞에 e가 붙으면 32비트, r이 붙으면 64비트
- 주용도는 있으나 그 외의 다양한 용도로 사용될 수 있는 레지스터
- 세그먼트 레지스터각 레지스터의 크기: 16비트
- cs, ss, ds, es, fs, gs 총 6가지 세그먼트 레지스터 존재
- 명령어 포인터 레지스터x64 아키텍처의 명령어 레지스터는 rip이며 크기는 8바이트
- 이 중에서 CPU가 어느 부분의 코드를 실행할 지 가리킴
- 플래그 레지스터RFLAGS라고 불리는 64비트 크기의 플래그 레지스터 존재
- 프로세서의 현재 상태를 저장하고 있는 레지스터
Linux
Unix OS: 다중 사용자 및 다중 작업 운영체제. 여러 사용자가 동일한 리소스를 공유 가능. 다른 사용자가 정보를 쉽게 교환 가능. 고수준 언어로 작성된 최초의 운영체제
Linux: 유닉스에서 파생된 운영체제. 뛰어난 신뢰성. 다중 사용자, 다중 처리 시스템. 오픈소스 기반 운영체제
명령어
ls: 디렉토리에 있는 파일의 목록을 나열
pwd: 현재 디렉토리의 전체 경로 출력
cd: 디렉토리 이동
cat: 파일 내용 출력
vi: 새로운 문서 편집
file: 어떤 종류의 파일인지 출력
mkdir: 새로운 디렉토리 생성
rm: 파일이나 디렉토리 삭제
cp: 파일이나 디렉토리 복사
find: 특정 파일의 위치 검색
id: uid, gid 등을 출력
whoami: 현재 사용자 이름 출력
*(와일드카드): 임의의 문자에 대응시키기 위하여 사용하는 문자
|(파이프라인): 한 데이터 처리 단계의 출력이 다음 단계의 입력으로 이어지는 형태로 연결된 구조
grep: 파일 내에서 문자열 검색
option: 출력 옵션
Linux process memory layout
프로세스의 메모리를 크게 5개의 세그먼트로 구분
세그먼트: 적재되는 데이터의 용도 별로 메모리의 구획을 나눈 것
- 코드 세그먼트: 실행가능한 기계코드가 위치하는 영역
- 데이터 세그먼트: 컴파일 시점에 값이 정해진 전역변수 및 전역상수들이 위치. CPU가 읽을 수 있어야 하므로 읽기 권한이 부여됨
- BSS 세그먼트: 컴파일 시점에 값이 정해지지 않은 전역 변수가 위치하는 메모리 영역
- 스택 세그먼트: 프로세스의 스택이 위치하는 영역. 실행 중에 동적으로 할당될 수 있음. 함수의 인자나 지역변수 같은 임시 변수들이 실행중에 여기에 해당됨
- 힙 세그먼트: 힙 데이터가 위치하는 세그먼트. 스택과 마찬가지로 동적으로 할당될 수 있음
Web
server-client: 웹 서버에 있는 리소스를 클라이언트가 받아보려면 클라이언트는 웹에게 특정 리소스를 지정하여 제공해달라고 요청해야 함. 이때 서버는 해당 요청을 이해하고 대응되는 동작을 통해 클라이언트에게 리소스 반환
쿠키 cookie: 클라이언트의 정보 기록과 상태 정보를 표현하는 용도로 사용. 클라이언트는 서버에 요청을 보낼 때마다 쿠키를 포함하고, 서버는 해당 쿠키를 통해 클라이언트를 식별
세션 session: 일정 기간동안 같은 사용자롤부터 들어오는 일련의 요구를 하나의 상태로 보고 그 상태를 유지시키는 기술. 쿠키에 인증 상태를 저장하지만 클라이언트가 인증정보를 변조할 수 없도록 하기 위해 사용
포트: 호스트 내에서 실행되고 있는 프로세스를 구분짓기 위한 16비트의 논리적 할당. 0~65536개의 개수를 가짐. IP주소는 컴퓨터를 찾을 때 필요한 주소를 나타내는 것이고 포트는 컴퓨터 안에서 프로그램을 찾을 때 나타내는 것