CS

[자료구조] 트리와 이진트리, 이진탐색트리(BST)

트리 그래프와 트리, 그리고 BST 87 균형잡힌 트리 : AVL 트리, 레드블랙트리 88 트리는 스택이나 큐, 어레이 같은 선형 자료구조가 아닌 비선형 자료구조. 계층적 관계(hierarchical RelationShip)을 표현하는 자료구조 트리는 표현에 집중한다 무엇인가를 저장하고 꺼내야한다는 사고에서 벗어나 트리라는 자료구조를 보자 트리를 구성하고 있는 요소들 Node (노드) : 트리를 구성하는 각각의 요소 Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node(루트 노드) : 최상위에 있는 노드 Leaf Node(Terminal Node, 단말 노드) : 하위에 자식 노드가 연결되어 있지 않은 노드 내부 노드(Internal Node, 비단말 노드) : 단말 노..

[자료구조] Stack & Queue (스택과 큐)

스택(Stack) 선형 자료구조의 일종으로 LIFO(Last In First Out) 특징을 가지고 있다. -> 나중에 들어온것이 먼저 나오고, FILO(First In Last Out) 먼저 들어간 원소가 나중에 나온다. 차곡차곡 쌓이는 구조로 먼저 들어간 원소는 밑에 깔리게 된다. 재귀적인 특징이 있다. 언제 사용? 함수의 콜 스택, 깊이 우선 탐색(DFS), 문자열 역순 출력, 후위 표기법, 웹 브라우저 방문 기록 스택의 연산 삽입 : push() 데이터 최상위 값삭제 : pop() 비어있는지 확인 : isEmpty() 꽉차있는지 확인 : isFull() push pop할 때는 해당 위치를 알고 있어야 하므로 SP(Stack Pointer)가 필요하다. 기본값은 -1 스택 - 자료구조 - 접기/펼치..

[자료구조]Array & ArrayList &LInkedList

Array & ArrayList & LinkedList 빅오표기법, 시간복잡도와 공간복잡도 빅오 표기법 : ‘가장 영향을 많이 끼치는 높은 승수를 가진 항의 상수 인자를 빼고 나머지 항을 빼서 나타낸 복잡도표기법 공간 복잡도 : 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양 시간 복잡도 : ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 Array(배열) 같은 타입의 연관된 data를 메모리상에 연속적이며 순차적으로 미리 할당되어 정해진 크기만큼 저장하는 자료구조 논리적 저장 순서와 물리적 저장 순서가 일치하고 index로 해당 element(원소)에 접근할 수 있다. 인덱스를 알고있다면 O(1)의 시간 복잡도로 원소에 random access 접근이 가능하다 . 삽입 또는 삭제 과정에서 해..

운영체제 정리

운영체제 목차 프로세스, 스레드 멀티 스레드 vs 멀티 프로세스 프로세스(process) 멀티 프로세스(Multi process) Context Switching( 컨텍스트 스위칭, 문맥 교환) 스레드 멀티 스레드 공유자원 (Shared Resource) 경쟁상태 (Race Condition) 임계 영역(임계구역, Critical Section) 동기화 문제 교착 상태 뮤텍스, 상호배제 세마포어 모니터, Monitor 동기와 비동기 시스템 콜 인터럽트 CPU 스케쥴링 메모리 관리 가상 메모리 페이징 앤 세그맨테이션 캐시 운영 체제(OS, Operating System) 하드웨어를 관리하고, 컴퓨터 시스템의 자원들을 효율적으로 관리해줍니다. 사용자가 컴퓨터를 편리하고 효과적으로 사용할 수 있도록 환경을 제..