📚 Computer Science

[Algorithm] C++ DFS & BFS 이해 및 구현

DFS : Depth First Search (깊이 우선 탐색) 이동할 수 있는 모든 노드를 이동하다가 더이상 이동할 수 없으면 뒤로 다시 돌아와 탐색 스택이나 재귀함수로 구현가능 노드 방문 시, 해당 노드의 방문 여부를 체크해야만 한다. (isVisited) DFS로 구현한 경로가 최단 경로인지 확인은 불가능하다. DFS의 시간복잡도 DFS(idx)는 해당되는 idx에 방문하는 함수이다. 그렇기에 해당 트리의 차수만큼 함수가 호출된다. 즉 DFS는 시간복잡도 * 차수가 DFS 알고리즘의 시간복잡도이다. 하지만 구현 방법에 따라 시간복잡도가 달라지며, 재귀함수로 구현하였을 경우 별도의 자료구조를 필요로 하지않기에 메모리를 아낄 수가 있다. 아래는 DFS의 진행되는 이미지이다. Code ( C++ ) - ..

[Algorithm] C++ Queue (큐) 클래스 구현

큐 ( Queue ) FIFO(First In First Out) - 선입선출 이라고 불린다. 삽입연산을 Push라고 하고, 삭제연산을 Pop이라 한다. 보통 BFS (너비 우선 탐색)에 쓰인다. 나중에 집어넣은 원소가 먼저나오는 스택 (Stack)과는 반대되는 개념이다. 예시 가장 쉽게 이해되는 구문이 위키백과에 잘 설명이 되어있다. " 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. " 아래는 큐의 이해를 돕기위한 예시이다. 은행 업무 너비 우선 탐색(BFS, Breadth-First Search) 캐시(Cache) 구현 프로세스 관리 Code #include using namespace std; ..

[Algorithm] C++ Stack (스택) 클래스 구현

스택 (Stack) 자료구조에서 무언가를 쌓는다는 의미로 쓰인다. LIFO(Last In First Out) - 후입선출 이라고 불린다. 삽입연산을 Push라고 하고, 삭제연산을 Pop이라 한다. 보통 DFS (깊이 우선 탐색)에 쓰인다. 예시 웹 브라우저 (뒤로 가기) : 가장 나중에 열린 페이지부터 다시 보여준다. 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행을 취소한다. 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사) Code #include using namespace std; class Stack { private: int _count; int _size; short* m_data; public : // 생성자 Stack() { _size = 0; _count = 0; ..

[Design Pattern] MVVM 패턴

MVVM 패턴 MVVM 패턴은 흔히 알려진 MVC 패턴에서 Controller를 빼고 ViewModel을 추가한 패턴이다. MVVM 패턴의 장점 View와 Model이 서로 전혀 알지 못하기에 독립성을 유지할 수 있다. 독립성을 유지하기에 효율적인 유닛 테스트가 가능하다. View와 ViewModel을 바인딩하기에 코드의 양이 줄어든다. View와 ViewModel의 관계가 N:1이다. MVVM 패턴의 단점 간단한 UI에서 오히려 ViewModel을 설계하는데 어려움이 있을 수 있다. 데이터 바인딩이 필수적으로 요구된다. 복잡해 질수록 Controller처럼 ViewModel이 빠르게 비대해진다. 표준화된 틀이 존재하지 않아 사람마다 이해하는게 다르다. View - 사용자의 눈에 보이는 UI를 담당하는곳..

[Design Pattern] 싱글톤 패턴 (Singleton Pattern)

싱글톤 패턴 싱글톤패턴(Singleton Pattern)은 오직 한개의 인스턴스만을 갖도록 보장하고, 이에대한 전역적인 접근점을 제공하는 패턴이다. 싱글톤 패턴 장점 1. 인스턴스 유일성을 보장한다. - 싱글톤 패턴은 인스턴스가 유일하게 컴파일 단계에서 강제한다. 인스턴스 개수를 늘리고싶을때도 유연하게 바꿀 수 있다. 2. 게으른 초기화(Lazy Initialization)가 일어난다. - 사용하지 않는다면 생성되지 않을 뿐더러 런타임에 초기화가 된다. 3. 어디서든 접근성이 쉽다. - 전역적인 접근점을 제공하기 때문이다. 싱글톤 패턴 단점 1. 객체지향의 의도와 맞지 않는다. - Singleton의 사용은 Global state를 만들 수 있기 때문에 바람직한 방법은 아니다. - 아무객체나 자유롭게 접..

[Algorithm] C++ Merge Sort (병합정렬)

병합정렬 List를 반으로 더이상 나눌 수 없을때까지 반으로 나누고(Divide - 분할), 나누어진 부분 List들을 두개씩 짝지어 정렬(Conquer - 정복)하며 합치는(Combine - 결합)과정을 반복하는 방법 병합정렬 알고리즘 하나의 List를 더 이상 나눠질 수 없을 때 까지 반으로 분할한다. 더 이상 나눌 수 있는 List가 없을 경우, 반복적으로 나뉘어진 부분 List들을 정렬하며 합친다. 예시 병합정렬의 알고리즘은 기본적으로 분할정복을 사용한다. 원소들의 List를 계속하여 나뉘어지지 않을때 까지 반으로 나누는 재귀 알고리즘을 이용한다. 원소 List에 둘 이상의 원소가 있는 경우 List를 분할하고, 양쪽 절반에 대해 병합정렬을 재귀적으로 호출하여 진행한다. 아래의 그림은 분할한 원소..

[Algorithm] C++ Quick Sort (퀵정렬)

퀵정렬 List에서 하나의 피벗을 정하고 이를 기준으로 피벗보다 작은 요소들, 큰 요소들로 두개의 부분 List를 만들어(Divide 분할) 정렬 후 다시 결합(Conquer 정복)을 재귀적으로 반복하는 방법 퀵정렬 알고리즘 1. 리스트 안에 있는 한 요소를 피벗(Pivot)으로 설정한다. 2. 피벗을 기준으로 왼쪽에서부터는 피벗보다 큰 값(a)을 찾고, 오른쪽에서부터는 피벗보다 작은 값(b)을 찾는다. 3. a와 b를 교한한다. 4. 왼쪽에서부터 찾은 a값의 위치와 오른쪽에서부터 찾은 b값의 위치가 엇갈리지 않을 때까지 2~3번 과정을 반복한다. 5. 엇갈린 경우에는 오른쪽에서부터 찾은 피벗보다 작은 값(b)과 피벗값을 교환한다. 6. 위의 과정에서 한 번의 분할이 이루어졌고, 두 개의 부분리스트에 대..

[Algorithm] C++ Insertion Sort (삽입정렬)

삽입정렬 앞의 원소들이 정렬되어 있다는 가정 하에 적절한 위치에 삽입하는 방법 삽입정렬 알고리즘 i번째 원소를 1부터 k - 1번째 까지와 비교하여 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식 1. 각 패스에서 1부터 각 원소에 대해 하나씩 (n - 1) 비교한다. 2. 현재 원소는 이미 정렬된 하위 목록에 있는 원소와 비교하여 확인된다. 3. 이미 정렬된 하위 목록들을 살펴보면서 더 큰 원소를 오른쪽으로 이동한다. 예시 아래 예시는 위의 예시의 다섯 번째 패스를 자세히 보여준다. 알고리즘의 이 지점에서 17, 26, 54, 77, 93으로 구성된 5개 원소의 정렬된 하위 원소들이 존재한다. 이때 이미 정렬된 항목에 31을 다시 삽입하려고 할 경우, 93에 대한 첫 번째 비교시 다..