전체 글

[백준 / BOJ] C++ 1766 문제집

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 위상 정렬이라는 개념도 제대로 모르고있었던 위상정렬 문제이다... 그래서 공부하며 포스팅하고 문제를 다시 풀어보았다. 입력란에 첫줄은 문제의 갯수와 조건의 갯수를 나타내고, 두번째줄 세번째줄을 보면 먼저 풀어야하는 문제 조건을 나타낸다. => (4 - 2), (3 - 1) degree 배열에 해당 번호에 들어오는 선의 수를 저장하고 2차원 벡터에 간선의 방향을 ..

[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에 대한 첫 번째 비교시 다..

[Algorithm] C++ Bubble Sort (거품정렬)

거품정렬 두개의 인접한 원소를 비교하는 정렬이다. 선택정렬과 유사하나, 다른점은 앞에서부터 차례로 정렬하기때문에 '안정정렬' 이라고도 한다. 정렬 방식중 가장 간단하며 쉬우나, 다른 정렬보다 원소의 교환이 많아, 소요되는 시간이 길다. 원소들의 정렬과정에서 원소의 이동이 거품처럼 수면위로 올라온다는 뜻으로 거품 정렬이라는 이름이 붙기도하였다. 거품정렬 알고리즘 앞에서부터 현재 원소와 바로 다음 원소를 비교한다. 현재 원소가 바로 다음의 원소보다 클 경우 교환한다. (오름차순 기준) 그 이후 바로 다음 원소로 이동하여, 해당 원소와 다음 원소를 비교한다. 예시 원소들 정렬 흐름은 아래 gif 파일로 확인할 수 있다. 거품정렬 특징 추가적인 메모리 소비가 적다. 구현이 매우 간단하다. 안정정렬이 가능하다. ..

[Algorithm] C++ Selection Sort (선택정렬)

선택정렬 주어진 리스트에서 최솟값을 맨 앞으로 보내는 방법이다. 원소들을 큰순이나, 작은순으로 정렬하는 알고리즘 중 하나이다. 선택정렬 알고리즘 Selection Sort는 Bubble Sort와 유사한 알고리즘이다. 해당 순서에 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 진행 Process는 다음과 같다. 1. 주어진 배열 중 최소값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. 예시 선택정렬 특징 Bubble Sort와 마찬가지로 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환횟수가 적기에 많은 교환이 일어나야하는 자료에서는 비효율적이다. 내부 배..

[Algorithm] C++ Topology Sort (위상정렬)

위상 정렬 사이클이 없는 방향 그래프의 모든 노드를 방향성에 맞게 순서대로 나열하는것 예시) 학과목을 고려한 학습 순서 설정 위 사진의 세 과목을 모두 듣기 위한 적절한 학습 순서는?? 자료구조 - 알고리즘 - 고급 알고리즘 (O) 자료구조 - 고급알고리즘 - 알고리즘 (X) 진입차수와 진출차수 진입차수 (Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수 (Outdegree) : 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 큐를 이용하는 위상 정렬 알고리즘 동작 과정은 다음과 같다. 진입차수가 0인 모든 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내어 해당 노드에서 나가는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣..