전체 글

OCP와 전략 패턴

유튜브 우아한 Tech 채널에서 10분 테코톡을 듣고 공부한 내용입니다. 10분 테코톡 - 베디의 OCP와 전략 패턴 목차 if-else의 문제점 OCP OCP란? 적용 장점 전략패턴 연습문제 추천 1. If-else의 문제점 변경, 확장이 될수록 코드가 복잡해진다 코드를 수정하거나 수정할 위치를 찾는데 점점 오래걸린다 실수로 추가하지 않고 누락하는 부분이 생길 가능성이 있다. if-else 블록이 커지므로 코드는 복잡하면서 추가 수정이 힘들어진다. 즉, 유지보수가 점점 어려워진다. 2. OCP(Open Close Principle) - 개방 폐쇄의 원칙 시간이 지나도 유지보수와 확장이 쉬운 시스템을 만들고자 로버트 마틴이 명령한 객체지향 설계 5원칙 SOLID중 하나 소프트웨어 구성요소(컴포넌트, 클래..

[자료구조] 그래프와 DFS, BFS

그래프(Graph) 그래프란 정점(Vertex)과 간선(Edge)로 이루어진 자료구조이다. 트리 또한 그래프이며, 트리는 사이클이 허용되지 않고, 그래프는 사이클이 허용된다. 사이클 : 그래프의 특정 정점에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있으면 사이클이 있다고 한다. 그래프 용어 정점 (Vertext, V) : 노드 라고도 하며 데이터가 저장되는 그래프의 기본 원소 간선 (Edge, E) : 정점(V, Node)를 연결하는 선, link, brach 라고도 부름 인접 정점 (adjacenct vertex, adj) : 간선에 의해 연결된 정점(그림 0, 3 등 이어진 정점) 단순 경로 (simple path) : 경로 중에서 반복되는 정점이 없는 경우. 동일한 간선을 지..

[자료구조] Heap 힙, 우선순위 큐

힙(Heap) 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다. 힙에는 두가지 종류가 있다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 : 최대 힙(Max Heap) 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 : 최소 힙(Min Heap) 우선 순위 큐(Priority queue)를 위해서 만들어졌다. - 힙 자체가 우선순위 큐이다. 큐는 FIFO(First In First Out, 선입선출) 자료구조인데, 우선순위큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다. Queue의 시간 복잡도는 enqueue = O(1), dequeue O(1) 이고 Priority queue 의 시간 복잡도는 push(삽..

[자료구조] 트리, B Tree, B+Tree

B Tree & B+ Tree 검색을 위한 자료구조중에서 이진트리는 한 부모가 두 개의 자식밖에 가지질 못하고, 균형이 맞지 않으면 검색 효율이 선형(O(n)) 급으로 떨어지지만, 균형이 잘맞으면 성능이 O(log N) 수준으로 보이는 장점이 있어 이를 바탕으로 개선하고자 하는 자료구조들이 나왔습니다. B Tree는 이진트리를 확장해서 더 많은수의 자식을 가질 수 있고, 균형이 맞지 않는 편향트리가 되지 않도록 균형을 맞추는 구조를 갖고 있습니다. 데이터베이스, 파일 시스템에서 널리 사용되는 트리 자료구조의 일종입니다. 단순하고 효율적이며 레벨로만 따지면 완전히 균형을 맞춘 트리입니다. 대량의 데이터를 처리할 때 하나의 노드에 많은 데이터를 가질 수 있으므로 큰 장점을 갖고 있습니다. B Tree의 규칙..

[자료구조] 트리, AVL 트리

AVL Tree (AVL은 발명자 세명의 이름에서 따왔다) 자가 균형 이진 탐색 트리. 이진 탐색 트리에서, 노드들이 삽입시 한쪽으로 편향되면 결국 탐색에서 O(N)의 시간이 걸리게 된다. * 그림 : 편향트리. 이진 탐색 트리의 편향트리를 극복하기 위해 재구성(회전, Rotate)을 통해 트리를 균형있게 만든다. AVL 트리는 다음과 같은 특징을 가진다. 이진 탐색 트리(BST)의 속성을 가진다. 왼쪽, 오른쪽 서브 트리의 높이차이가 최대 1이다. 삽입, 삭제 등 어떤 시점에서 높이 차이가 1보다 커지면 회전(Ratation)을 통해 균형을 맞춰 높이를 1로 맞춘다. AVL 트리는 높이를 logN으로 유지하기 떄문에 삽입, 검색 ,삭제의 시간 복잡도는 O(log N) 이다. AVL 트리는 균형이 무너졌..

[자료구조] 트리, 레드블랙 트리 (Red-Black-Tree)

Red-Black Tree Binary Search Tree를 기반으로 하는 자료구조. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어. 연산 삽입 insert : O(lon N) 조회 search : O(log N) 삭제 delete : O(log N) 정의 레드 블랙 트리는 다음의 성질들을 만족하는 BST(이진 탐색 트리) 이다. 모든 노드는 Red(빨강) or Black(검정) 의 색을 갖는다. 루트 노드는 검정색이다. 모든 리프 노드들은 검정색이다. 레드 노드의 자식은 모두 검정색이다 모든 리프 노드에서 Black Depth는 같다. 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 각 노드에 대해서 노드로부터 descendan..

[자료구조] 트리와 이진트리, 이진탐색트리(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) 하드웨어를 관리하고, 컴퓨터 시스템의 자원들을 효율적으로 관리해줍니다. 사용자가 컴퓨터를 편리하고 효과적으로 사용할 수 있도록 환경을 제..