프로그램을 실행하는 도중에 예기지 않은 상황이 발생할 경우 현재 실행중인 작업을 즉시 중단하고 발생된 상황을 우선 처리한 후 실행중이던 작업으로 복귀하여 계속 처리하는 것

인터럽트의 종류와 발생 원인

외부 인터럽트

입출력장치, 타이밍 장치, 전원 등 외부적인 요인에 의해 발생하는 인터럽트

전원 이상 인터럽트 : 정전이되거나 전원 이상이 있는경우 발생 기계 착오 인터럽트 : CPU의 기능적인 오류 동작이 발생한 경우 발생 외부 신호 인터럽트 : 타이머에 의해 규정된 시간을 알리는경우, 키보드로 인터럽트 키를 누른 경우, 외부 장치로부터 인터럽트 요청이 있는 경우 발생 입출력 인터럽트 : 입출력 Data의 오류나 이상 현상이 발생한 경우, 입출력장치가 데이터의 전송을 요구하거나 전송을 끝났음을 알릴 경우 발생

내부 인터럽트(Trap)

잘못된 명령이나 데이터를 사용할 때 발생하는 인터럽트

프로그램 검사 인터럽트 : 0으로 나누기가 발생한 경우, OverFlow 또는 UnderFlow가 발생한경우, 프로그램에서 명령어를 잘못 사용한 경우, 부당한 기억장소의 참조와 같은 프로그램 상의 오류가 발생

소프트웨어 인터럽트

프로그램 처리 중 명령의 요청에 의해 발생하는 인터럽트

SVC인터럽트 : 사용자가 SVC명령을 써서 의도적으로 호출한 경우, 복잡한 입출력 처리를 해야하는 경우, 기억장치 할당 및 오퍼레이터와 대화를 해야하는 경우 발생

인터럽트 발생 시 처리과정

1. 프로그램 실행을 중단한다.
2. 현재의 프로그램 상태를 보존한다.
3. 인터럽트 처리 루틴을 실행한다.
4. 인터럽트 서비스 루틴을 실행한다. 5, 인터럽트 요청 신호가 발생했을 때 보관한 PC의 값을 다시 PC에 저장한다.
5. PC의 값을 이용하여 인터럽트 발생 이전에 수행중이던 프로그램을 계속 실행한다.

참고 사이트

인터럽트의 정의와 종류 및 처리과정

낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘 비교 연산을 하지 않으며 정렬 속도가 빠르다. 데이터 전체 크기에 Radix Table 크기의 메모리가 더 필요하다.

정렬 방식

1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다.
2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다.
3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다.
4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.

예시

각 숫자에 해당하는 큐 공간을 할당하고 진행한다.

먼저 1의 자리 숫자부터 시도한다. 데이터 순서대로 각 1의 자리에 해당되는 Queue에 데이터가 들어가게 된다. 15같은 경우는 1의 자리가 5이므로 Queue 5에 들어가는 방식이다.

1의 자리 정렬이 완료되면, 10의 자리에 대해 같은 작업을 반복한다.

각 데이터의 10의 자리에 해당되는 큐에 데이터를 위치시킨다. 0번 큐부터 차례대로 데이터를 가지고 온다.

최종 정렬이 완료된다.

특징

시간복잡도는 O(dn). d는 가장 큰 숫자의 자리수 자리수가 고정되어 있어서 안정성이 있다.

위상정렬 (Topological sort)

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것.

하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라고 한다. 위상 정렬의 과정에서 그래프에 남아있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘이 중단되고, 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다.

위상정렬을 이용한 기본적인 해결 방법

1. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택한다. 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다. 초기에 간선의 수가 0인 모든 정점을 큐에 삽입한다.
2. 선택된 정점과 여기에 부속된 모든 간선을 삭제한다. 선택된 정점을 큐에서 삭제한다. 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소한다.
3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료한다.

허프만 코드

가변 길이 코드를 만들어서 효율적으로 압축한다.

예제

문자열 "ABBCCCDDDDEEEEEFFFFFF"의 가변 길이 코드 만들기

1. 알파벳 별 빈도수를 저장한 노드를 생성한다.

2. 빈도수를 비교하여 노드를 만든다. 가장 작은 빈도수를 가진 노드와 두 번째로 작은 빈도수의 노드를 합쳐 노드를 만든다.

3. 2를 반복한다.

결과

만들어진 허프만 코드를 가지고 문자열을 인코딩한다.

참고 사이트

Radix Sort 위상 정렬 허프만 코드

이전에 Django로 프로젝트 했던 경험이 생각나지 않아서 Django에 대해 복습하기로 했다.

Django 프레임워크

Django는 파이썬으로 작성된 오픈소스 웹 애플리케이션 프레임워크로, Model-View-Controller(MVC) 패턴을 따르고 있다. 고도의 데이터베이스 기반 웹 사이트를 작성하는데 있어서 수고를 더는 것이 장고의 주된 목표이다. 컴포넌트의 재사용성(reusability)과 플러그인화 가능성(pluggability), 빠른 개발을 강조한다. 설정 파일부터 데이터 모델까지 파이썬으로 작성되어 있다.

MVC / MVT

MVC는 일반적인 프레임워크가 가지는 패턴이다. 장고는 MVT 패턴을 가진다.

Model : 데이터베이스 서버에 저장이 되는 데이터를 다룬다. View, Template(Django) : 유저가 원하는 형태로 데이터를 적절하게 만들어서 보내주는 역할 Control, View(Django) : 사용자의 입력과 이벤트에 반응하여 Model과 View를 업데이트한다.

Model은 어플리케이션이 무엇을 할 지에 대한 정의한다. 처리되는 데이터, 데이터베이스, 내부 알고리즘 등 내부 비즈니스에 관한 로직의 처리를 수행한다.

View는 사용자에게 보여지는 영역이다. JSP등 사용자 인터페이스를 담당한다.

Controller는 모델에게 어떻게할 것인지를 알려주며, 모델과 뷰 사이를 연결하는 역할을 한다. 사용자의 입출력을 받아 데이터를 처리한다.

MVC, MVT는 거의 동일하다.

Django 동작

1. 사용자가 브라우저에서 Url로 요청을 보낸다.
2. View가 요청을 확인하고 Model에게 알려준다.
3. Model은 DB에서 요청한 정보를 찾아서 View로 돌려준다.
4. View는 요청한 정보를 Templates에 전달하고 html과 조합되서 브라우저 사용자에게 보여진다.

Django의 파일들

녹색으로 표시된 파일이 개발자가 직접 다루는 파일이다.

Project

서비스 명 또는 서비스 자체를 말한다. 프로젝트를 만들면 기본 폴더와 파일이 생성된다.

App

웹 서비스에 추가되는 기능. 블로그, 게시판, 설문 등이 될 수 있다. 앱을 만들면 앱 이름으로 된 폴더에 기본 파일들이 생성된다.

Model(models.py)

앱을 만들면 해당 폴더 안에 models.py 파일이 생성된다. 파일에서 코드를 통해 모델(데이터)의 구조를 결정하고 관리할 수 있다. 데이터베이스와 관련된 다양한 동작을 수행한다.

View(view.py)

실질적으로 파이썬 코드를 많이 작성하는 곳. 앱을 만들면 해당 폴더 안에 views.py 파일이 생성된다. 데이터를 어떻게 보여주고 처리할 것인지에 대한 로직을 짤 수 있다. models.py에 신호를 보낸다. 주로 클래스 안에 http 메소드 함수를 포함하고 있다.

Template(html file)

데이터의 구현 부분 html 파일 안에 다양한 로직을 삽입할 수 있다. 사용자의 인터페이스에 적절하게 구성을 해주고, 그 정보가 web server로 간다.

controller

일반적인 MVC 패턴에서 장고 view의 역할을 하는 영역이다.

WSGI(wsgi.py)

Web Server Gateway Interfase의 약자로 웹서버와 장고를 적절히 결합시켜준다.

URL Resolution(urls.py)

wsgi.py에서 신호가 들어오면 가장 먼저 받는 곳이다. 정규표현식으로 구현되어 있다.

asgi

Asynchronous Server Gateway Interface의 약자로 wsgi가 동기식이라면 asgi는 동기, 비동기식 모두를 지원한다.

참고 사이트

Make a Simple Blog with Django(1) REST API Django란? 장고 개념 정리 장고 동작원리

Prefix

순회

• 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문
• 중위 순회(inorder traverse) : 왼쪽 하위 트리를 방문 후 뿌리(root)를 방문
• 후위 순회(postorder traverse) : 하위 트리 모두 방문 후 뿌리(root)를 방문
• 층별 순회(level order traverse) : 위 쪽 node들 부터 아래방향으로 차례로 방문

큐

우선순위 큐

큐는 연산의 결과로 먼저 들어간 데이터가 먼저 나오지만 우선순위 큐는 다르다. 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다.

우선순위 큐를 구현하는 방법

• 배열을 기반으로 구현하는 방법
• 연결리스트를 기반으로 구현하는 방법
• 힙을 이용하는 방법 -> 주로 사용됨

선형 큐

초기 상태의 공백 큐는 저장된 원소가 없으므로 front와 rear를 -1로 설정한다. rear = n-1이면 포화상태

원형 큐

배열의 처음과 끝이 연결되어 있다고 생각하는 것 초기 공백 상태일 때 front와 rear값이 0 공백 상태 조건 front = rear 포화 상태 조건 (rear+1) % n = front 삽입 rear = (rear+1) % n 삭제 front = (front+1) % n

Dequeue

큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐. 스택과 큐의 성질을 모두 가지고 있다.

큐의 사용

작업 버퍼 큐, 프로세스 스케줄링, 대기 행렬을 모델링하는 시뮬레이션(큐잉이론)에서 사용한다.

트리

비선형 자료구조 중에서 계층관계를 가진 계층형 자료구조

이진트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리

포화 이진트리(Full binary tree)

높이가 5인 포화 이진트리의 노드 수 = 31개

완전 이진트리(Complete binary tree)

레벨 1부터 k-1까지 노드가 채워져 있고 마지막 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

Minimum spanning tree

spanning tree : 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프 Minimum spanning tree : 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 스패닝 트리

크루스칼 알고리즘

무방향 연결 그래프가 주어질 때, 최소 스패닝 트리라고 부르는 서브 그래프를 찾는 알고리즘. 유니온 파인드 자료구조를 사용한다.

1. 모든 간선을 끊어 놓는다.

2. 가중치 순으로 간선을 정렬한다.

3. 정렬된 간선을 순서대로 선택한다.

4. 선택한 간선의 두 정점이 연결되어 있지 않으면, 해당 간선을 최소 스패닝 트리에 포함 시키고 두 정점을 연결한다.

5. 3, 4 반복

결과

시간복잡도

간선 E개 정렬 = O(elog₂e) union-find를 통한 vertex 비교 O(V) 따라서 O(elog₂e) Edge 정렬이 적을수록 빠르다.

프림 알고리즘

예시 그래프

1. 임의의 정점을 선택하여 비어있는 T에 포함시킨다. T is tree

2. T에 있는 노드와 T에 없는 노드 사이의 간선 중 가중치가 최소인 간선을 찾는다.

3. 찾은 간선이 연결하는 두 노드 중, T에 없는 노드를 T에 포함시킨다.

4. 모든 노드가 T에 포함될 때 까지 2,3을 반복한다.

시간복잡도

주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 O(n^2) 그래프에 간선이 많이 존재하는 ‘밀집 그래프(Dense Graph)’ 의 경우는 Prim 알고리즘이 적합하다.

힙

최대힙, 최소힙 힙소트

그래프

연결되어있는 원소간의 관계를 표현하는 자료구조 연결할 객체를 나타내는 정점과 객체를 연결하는 간선의 집합으로 구성된다. 그래프 G를 G=(V,E)로 정의하는데 V는 정점들의 집합, E는 간선들의 집합이다.

그래프 구현 방법

• 순차 자료구조 방식 (인접 행렬)
• 연결 자료구조 방식 (인접 리스트)

DFS

시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색하다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길 간전이 있는 정점으로 되돌아와서 다른 방향의 간선으로 재탐색

• 스택사용

BFS

시작 정점에서 인접한 정점들을 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법. 가까운 정점을 먼저 방문하고 멀리있는 정점들은 나중에 방문하는 순회방법

• 큐 사용

그래프 종류

방향 그래프

무방향 그래프

연결 그래프

단절 그래프

완전 그래프

가중치 그래프

참고 사이트

수기 표기법 순회 프림 알고리즘 크루스칼 알고리즘 자료구조 정리

문제 설명

대기목록에서 우선순위가 높은 문서부터 출력할 때, 내가 요청한 문서가 몇 번째로 인쇄되는지 return 하기

제한사항

대기목록에는 1개 이상 100개 이하의 문서가 있다. 인쇄 작업의 중요도는 1~9로 표현하고, 숫자가 클수록 중요하다. location은 대기목록의 index를 의미한다.

문제풀이

1. 대기목록에 맨 앞에 있는 문서보다 더 중요한 문서가 뒤에 있는지 확인한다.
2. 더 중요한 문서가 뒤에 있으면 맨 앞의 문서를 맨 뒤로 보낸다.
3. 더 중요한 문서가 없으면 맨 앞의 문서를 출력한다.

코드

#include <string>
#include <vector>
#include <list>

using namespace std;

list <pair<int, int>> waiting_list;

void Make_list(vector<int> priorities){
    for(int i=0; i<priorities.size(); i++){
        waiting_list.push_back(make_pair(i,priorities[i]));
    }
}

bool Is_first(){
    int front = waiting_list.front().second;
    bool is_first = true;

    list <pair<int, int>>::iterator iter;
    for(iter=waiting_list.begin(); iter!=waiting_list.end(); iter++){
        if(front < iter->second){
            is_first = false;
            break;
        }
    }

    return is_first;
}

int solution(vector<int> priorities, int location) {
    int answer = 0;
    bool is_first;
    Make_list(priorities);

    while(1){
        is_first = Is_first();
        if(!is_first){
            pair<int, int> new_back = waiting_list.front();
            waiting_list.push_back(new_back);
        }
        else{
            answer ++;
            if(waiting_list.front().first == location) break;
        }
        waiting_list.pop_front();
    }

    return answer;
}

시간 복잡도

Worst case : 대기목록이 descending order 되어 있는 경우 + 맨 마지막 문서의 출력 순서를 return하는 경우 시간복잡도 : O(N^2) N : 대기목록의 크기

스택/큐 문제에 list를 사용한 이유

처음에 큐를 사용하려고 했으나, 반복문으로 큐 안의 모든 원소들에게 접근해서 값을 확인해야 했다. 하지만 큐는 index를 사용해서 원소에 접근할 수 없어서 불편했다. 원소 접근이 많은 경우에는 스택/큐보다 list를 사용하면 pop, push가 자유롭고, index를 사용해서 원소에 접근할 수 있어서 더 편하다는 글을 보고 list를 사용하게 되었다.

참고 사이트

List of C++

프로그래머스 - 다리를 지나는 트럭

문제 설명

트럭 여러대가 일차선 다리를 건널 때, 모든 트럭이 다리를 건너기 위해 최소 몇 초가 걸리는지 return 하기

제한사항

트럭은 1초에 1만큼 움직인다. 다리의 길이는 bridge_length이다. 다리는 최대 weight만큼의 무게를 견딜 수 있다. 트럭은 대기하고 있는 순서대로 다리를 건넌다.

문제풀이

1. 트럭을 다리에 올릴 수 있는지 확인한다.
2. 트럭에 다리를 올릴 수 있을 때 다리에 올라간 트럭 큐에 push 하고, 다리 위 트럭의 무게에 트럭의 무게를 추가한다.
3. 트럭에 다리를 올릴 수 없을 때 다리가 채워지지 않았을 때 : 다리에 올라간 트럭 큐에 0을 추가한다. 다리가 꽉 찼을 때 : 다리에 올라간 트럭 큐의 맨 앞 트럭을 pop 한다.

코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int idx = 0;

    queue<int> on_bridge;
    int on_bridge_weight = 0;

    while(1){
        if(idx == truck_weights.size()) break;

        int current_truck_weight = truck_weights[idx];
        answer ++;

        if(on_bridge.size() == bridge_length){
            on_bridge_weight -= on_bridge.front();
            on_bridge.pop();
        }

        if(on_bridge_weight + current_truck_weight <= weight){
            on_bridge.push(current_truck_weight);
            on_bridge_weight += current_truck_weight;
            idx ++;
        }
        else{
            on_bridge.push(0);
        }
    }

    answer += bridge_length;
    return answer;
}

맨 마지막 트럭이 다리 위로 올라가면 while문이 종료된다. 마지막 트럭이 다리 위로 올라간 다음, 다리를 빠져나올 때까지 bridge_length만큼 시간이 소요되므로 맨 마지막 트럭이 다리 위로 올라갈 때 까지 걸린 시간 + bridge_length가 답이 된다.

시간 복잡도

O(N) N : answer - bridge_length

문제 풀 때 참고 사이트

• 탐색 범위를 두 부분으로 분할하면서 찾는 방식.
• 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠르다.

Process(Ascending)

1. 정렬을 한다. 오름차순으로 정렬한다고 가정한다.
2. mid 값을 정한다. mid = (left+right)/2
3. mid 와 찾고자 하는 값을 비교한다.
4. 구할 값이 mid보다 Index가 높으면 left = mid + 1 구할 값이 mid보다 Index가 낮으면 right = mid - 1
5. left가 right보다 커질 때 까지 반복한다.

C++ Code(Ascending)

int binarySearch(vector<int> arr, int target){
  int low = 0;
  int high = arr[arr.size()-1];

  while(low <= high){
    int mid = (low+high)/2;

    if(arr[mid] == target)
      return mid;

    if(arr[mid] > target)
      high = mid - 1;
    else 
      low = mid + 1;
  }
  return high;
}

GIF로 이해하는 Binary Search

시간복잡도

O(log₂n)

공간복잡도

O(n)

참고 사이트

Binary Search 설명 Binary Search Code Binary Search Image

• 완전 이진 트리(Complete binary tree)를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식

Complete binary tree 삽입 시 왼쪽부터 차례대로 추가하는 이진 트리

Heap 큰 키(우선 순위)에 자주 엑세스 하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조이다.

Heap property

heap order property

각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다. Max heap 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다. Min heap

heap shape property

완전 이진 트리 모양으로, 마지막 레벨의 모든 노드는 왼쪽에 쏠려 있다.

Process(Ascending)

1. 주어진 원소들로 최대 힙을 구성한다.
2. 최대 힙의 루트노드와 말단노드를 교환하고 말단노드를 꺼낸다. 루트노드 현재 배열의 첫번째 요소 ➡ 최댓값 말단노드 현재 배열의 마지막 요소
3. 새 루트노드에 대해 최대 힙을 구성한다.
4. 원소의 개수만큼 2번과 3번을 반복 수행한다.

C++ Code(Ascending)

HeapSort

void heapSort(int arr[], int arrSize){
  int n = arrSize;

  // Build Max Heap : 1단계
  for(int i=n/2-1; i>=0; i--){
    heapify(arr, n, i);
  }

  // 힙 크기를 줄이고 자리 이동 : 2~4단계
  for (int i=n-1; i>0; i--){
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

Heapify

주어진 자료구조에서 힙 성질을 만족하도록 하는 연산

void heapify(int arr[], int n, int i){
  int p = i;
  int l = i*2 + 1;
  int r = i*2 + 2;

  // 왼쪽 자식 노드
  if (l < n && arr[p] < arr[l]){
    p = l;
  }
  // 오른쪽 자식 노드
  if (r < n && arr[p] < arr[r]){
    p = r;
  }

  // 부모노드 < 자식노드
  if(i != p){
    swap(arr[p], arr[i]);
    heapify(arr, n, p);
  }
}

GIF로 이해하는 Heap Sort

시간복잡도

• Heapify : log₂n 말단 노드(최댓값)이 루트 노드에 올라오기까지 트리의 높이만큼 자리를 이동해야 하므로 log₂n 만큼 이동해야 한다.

• Heapify를 해야 하는 노드 개수 : n

따라서 시간복잡도는 Heapify * Heapify를 해야 하는 노드 개수 = nlog₂n가 된다.

Best case : O(nlog₂n) Worst case : O(nlog₂n) Average case : O(nlog₂n)

공간복잡도

O(n)

장점

• 가장 크거나 작은 값을 구할 때 최소 힙, 최대 힙의 루트 값이기 때문에 한 번의 힙 구성으로 값을 구할 수 있다.
• 최대 k만큼 떨어진 요소들을 정렬할 때, 삽입 정렬보다 더욱 개선된 결과를 얻을 수 있다.

단점

• 불안정 정렬(Unstable Sort)이다.

참고 사이트

Heap Sort1 Heap Sort2 최대 힙과 최소 힙 Heap Sort Image

• Merge Sort는 분할 정복(Divide and Conquer) 방법을 통해 주어진 배열을 정렬한다.

*Divide and Conquer * 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

Process(Ascending)

1. 영역을 두개의 sub problem으로 쪼갠다. 이때, 쪼갠 영역의 크기는 최대한 같게 한다. ➡ MergeSort
2. 쪼갠 영역을 합병하면서 정렬한다. ➡ Merge

C++ Code(Ascending)

MergeSort

void mergeSort(int arr[], int left, int right){
  if(left < right){
    int mid = (left+right) / 2;

    mergeSort(arr, left, mid);
    mergeSort(arr, mid+1, right);
    merge(arr, left, mid, right);
  }
}

Merge

void merge(int arr[], int left, int mid, int right){
  int ll = mid-left+1; // left array length
  int rl = right-mid; // right array length
  int L[ll], R[rl];

  for(int i=0; i<ll; i++){
    L[i] = arr[left+i];
  } 
  for(int j=0; j<rl; j++){
    R[j] = arr[mid+1+j];
  }

  int i=0, j=0, k=left;
  while(i<ll && j<rl){
    if(L[i] <= R[j]){
      arr[k] = L[i++];
    }
    else{
      arr[k] = R[j++];
    }
    k++;
  }

  while(i<ll){
    arr[k++] = L[i++];
  }
  while(j<rl){
    arr[k++] = R[j++];
  }
}

GIF로 이해하는 Merge Sort

시간복잡도

• 비교횟수 : log₂n 레코드의 개수 n이 2의 거듭제곱이라고 가정했을 때, n = 2^k라고 표현할 수 있다. n = 2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3이다. 이를 일반화 하면, n = 2^k 이므로 호출의 깊이는 k이다. 이 때, k = log₂n 이므로 비교횟수는 log₂n 이다.

• 각 순환 호출 단계의 비교 연산 : n 각 순환 호출에서 전체 리스트의 거의 모든 레코드를 비교해야 하므로 n번의 비교가 발생한다.

따라서 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계 비교 연산 = nlog₂n가 된다.

Best case : O(nlog₂n) Worst case : O(nlog₂n) Average case : O(nlog₂n)

공간복잡도

O(n)

장점

• 안정 정렬
• 빠르다

단점

• 제자리 정렬을 하지 않고 새로운 메모리에 정렬 후에 원래 리스트에 결과를 저장한다.
• 실제 사용시 퀵 소트와 힙 소트보다 느린 경우가 많다.

참고 사이트

Merge Sort1 Merge Sort2 Merge Sort3

문제 설명

기능을 배포할 때, 각 배포마다 몇 개의 기능이 배포되는지 return하기.

제한사항

상대적으로 뒤에 있는 기능이 먼저 개발되면, 앞에 있는 기능이 배포될 때 함께 배포된다. 작업의 개수(progresses, speeds배열의 길이)는 100개 이하이다. 작업 진도는 100 미만의 자연수이다. 작업 속도는 100 이하의 자연수이다. 배포는 하루에 한 번만 할 수 있으며, 하루의 끝에 이루어진다고 가정한다.

문제풀이

1. 각 작업을 배포하기 위해 걸리는 시간을 계산한다.
2. 가장 앞선 기능보다 더 늦게 개발되는 기능을 찾는다.
3. 가장 앞선 기능부터 더 늦게 개발되는 기능 전까지의 기능 개수를 answer에 넣어준다. ➡ 배포
4. 더 늦게 개발되는 기능을 가장 앞선 기능으로 선택하여 새로운 배포를 한다.

코드

#include <string>
#include <vector>
#include <math.h>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    int maxDay = 0;
    int maxDaysIdx = 0;
    int day;
    int restTask;

    for(int i=0; i<progresses.size(); i++){
        restTask = 100 - progresses[i];
        day = floor(restTask / speeds[i]);

        if(restTask % speeds[i] > 0) day ++;

        if(maxDay < day){
            if(i!=0){
                answer.push_back(i - maxDaysIdx);
                maxDaysIdx = i;
            }
            maxDay = day;
        }
    }
    answer.push_back(progresses.size() - maxDaysIdx);
    return answer;
}

시간 복잡도

Θ(N) N : 작업 개수

문제 풀 때 참고 사이트

• Quick Sort는 분할 정복(Divide and Conquer) 방법을 통해 주어진 배열을 정렬한다.
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다.
• 배열을 비균등하게 분할한다.

*Divide and Conquer * 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략

Process(Ascending)

1. 배열에서 하나의 원소를 고른다. ➡ 피벗(pivot)
2. 피벗 앞에는 피벗 보다 작은 모든 원소들이 오고, 뒤에는 큰 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다. 재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종 위치가 정해지므로, 알고리즘이 반드시 끝난다는 것을 보장할 수 있다.

C++ Code(Ascending)

Quick Sort는 Divide와 Conquer로 이루어져 있다.

정복 (Conquer)

부분 배열을 정렬한다. 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

void quickSort(int arr[], int left, int right){
  if(left >= right) return;

  int pivot = partition(arr, left, right); // 분할

  // pivot을 제외한 2개의 부분 배열을 대상으로 순환 호출
  quickSort(arr, left, pivot-1);  // left Conquer
  quickSort(arr, pivot+1, right); // right Conquer
}

분할 (Divide)

입력 배열을 피벗 기준으로 비균등하게 2개의 부분 배열로 분할한다. 피벗을 중심으로 왼쪽은 작은 요소들, 오른쪽은 큰 요소들이 오게 한다.

int partition(int arr[], int left, int right){
  int mid = (left + right) / 2;
  swap(arr[left], arr[mid]);

  int pivot = arr[left]; //가장 왼쪽 값을 pivot으로 설정
  int i = left, j = right;

  while(i<j){
    while(pivot < arr[j]){ //오른쪽부터 작은 값을 찾는다.
      j--;
    }
    while(i<j && pivot >= arr[i]){ //왼쪽부터 큰 값을 찾는다.
      i++;
    }
    swap(arr[i], arr[j]); //교환
  }

  arr[left] = arr[i];
  arr[i] = pivot;
  return i;
}

Quick Sort 개선

partition()에서 피벗 값이 최소나 최대값으로 지정되어 파티션이 나누어지지 않을 때, O(n^2)에 대한 시간복잡도를 가진다. 즉, 배열이 오름차순 또는 내림차순으로 정렬되어 있는 경우에 O(n^2)를 갖게 된다. 배열에서 가장 앞에 있는 값과 중간 값을 교환한다면, 확률적으로 시간복잡도를 O(nlog₂n)으로 개선할 수 있다. 하지만 이 방법으로도 Worst case의 시간복잡도를 O(nlog₂n)로 만들 수 없다.

GIF로 이해하는 Quick Sort

시간복잡도

Best case : T(n) = O(nlog₂n)

• 비교횟수 : log₂n 레코드의 개수 n이 2의 거듭제곱이라고 가정했을 때, n = 2^k라고 표현할 수 있다. n = 2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3이다. 이를 일반화 하면, n = 2^k 이므로 호출의 깊이는 k이다. 이 때, k = log₂n 이므로 비교횟수는 log₂n 이다.

• 각 순환 호출 단계의 비교 연산 : n 각 순환 호출에서 전체 리스트의 거의 모든 레코드를 비교해야 하므로 평균 n번 정도의 비교가 발생한다.

따라서 Best case의 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계 비교 연산 = nlog₂n가 된다.

Worst case : T(n) = O(n^2)

최악의 경우 : 배열이 이미 정렬되어 있는 경우

• 비교횟수 : n 레코드의 개수 n이 2의 거듭제곱이라고 가정했을 때, n = 2^k라고 표현할 수 있다. 이 때, 순환 호출의 깊이는 n이다.

• 각 순환 호출 단계의 비교 연산 : n 각 순환 호출에서는 전체 리스트의 대부분 레코드를 비교해야 하므로 평균 n번 비교한다.

따라서 Worst case의 시간복잡도는 순환 호출의 깊이 * 각 순환 호출 단계 비교 연산 = n^2가 된다.

Average case : T(n) = O(nlog₂n)

공간복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n).

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환한다.
• 한 번 결정된 피벗들이 추후 연산에서 제외된다.
• 정렬하려는 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. 제자리 정렬

단점

• 불안정 정렬(Unstable Sort)이다.
• 정렬된 배열에서는 Quick Sort의 불균형 분할에 의해 수행시간이 많이 걸린다.

참고 사이트

Quick Sort 안정 정렬과 불안정 정렬

Selection Sort는 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 이다.

Process(Ascending)

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 제외한 나머지 배열을 같은 방법으로 교체한다.

C++ Code(Ascending)

#include <iostream>
#include <vector>
using namespace std;

void SelectionSort(vector<int> arr){
  int indexMin, temp = 0;
  for(int i=0; i<arr.size()-1; i++){    // 1
    indexMin = i;
    for (int j=i+1; j<arr.size(); j++){ // 2
      if(arr[j] < arr[indexMin]){       // 3
        indexMin = j;
      }
    }
    swap(arr[indexMin], arr[i]);        // 4
  }
}

주석 설명

1. 범위에서 가장 작은 값이 들어갈 위치를 선택한다.
2. i+1번째 인덱스에서부터 끝까지 값을 확인한다.
3. 범위에서 가장 작은 값을 찾아서 인덱스를 indexMin에 저장한다.
4. indexMin 위치의 값과 가장 작은 값이 들어갈 위치의 값을 교환한다.

GIF로 이해하는 Selection Sort

시간복잡도

(n-1) + (n-2) + (n-3) + ... + 2 + 1 ➡ n(n-1)/2 이므로 시간복잡도는 O(n^2). 정렬 여부에 상관없이 비교를 하기 때문에 최선, 평균, 최악의 경우 모두 O(n^2).

공간복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n).

장점

• 구현이 매우 간단하고 소스코드가 직관적이다.
• 정렬하려는 배열 안에서 교환하는 제자리 정렬(in-place sorting) 방식이므로 다른 메모리 공간이 필요하지 않다.
• 정렬을 위한 비교횟수는 많지만, Bubble Sort 에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로 비효율적이다.
• 동일한 값에 대해 기존의 순서가 유지되지 않는 불안정 정렬(Unstable Sort) 입니다.

참고 사이트

선택 정렬 안정 정렬과 불안정 정렬

Bubble Sort는 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.

정렬 과정이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 Bubble라는 이름이 붙었다.

Process(Ascending)

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, ... 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.

2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

C++ Code(Ascending)

#include <iostream>
#include <vector>
using namespace std;

void BubbleSort(vector<int> arr){
  int temp = 0;
  for(int i=0; i<arr.size(); i++){     // 1
    for(int j=1; j<arr.size()-i; j++){ // 2
      if(arr[j-1] > arr[j]){            // 3
        swap(arr[j-1], arr[j]);
      }
    }
  }
}

주석 설명

1. 제외될 원소의 개수를 의미한다. 1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 하나씩 증가시켜준다.
2. 원소를 비교할 인덱스를 뽑는 반복문이다. j는 현재 원소를 가리키고, j-1은 이전 원소를 가리킨다.
3. 현재 가리키고 있는 두 원소의 대소를 비교한다. 오름차순으로 정렬하기 위해 현재 원소 보다 이전 원소가 더 크다면 자리를 교환한다.

GIF로 이해하는 Bubble Sort

시간복잡도

(n-1) + (n-2) + (n-3) + ... + 2 + 1 ➡ n(n-1)/2 이므로 시간복잡도는 O(n^2). 정렬 여부에 상관없이 비교를 하기 때문에 최선, 평균, 최악의 경우 모두 O(n^2).

공간복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n).

장점

• 구현이 매우 간단하고 소스코드가 직관적이다.
• 정렬하려는 배열 안에서 교환하는 제자리 정렬(in-place sorting) 방식이므로 다른 메모리 공간이 필요하지 않다.
• 동일한 값에 대해 기존의 순서가 유지되는 안정정렬(stable sort) 이다.

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)로 비효율적이다.
• 정렬되지 않은 원소가 정렬되기 위해 swap이 많이 일어난다.

참고 사이트

Bubble Sort 안정 정렬과 불안정 정렬

프로그래머스 - 베스트앨범

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래 두 개씩 모아 베스트 앨범 출시하기

제한사항

속한 노래가 많이 재생된 장르부터 수록한다. 장르 내에서 많이 재생된 순서로 노래를 수록한다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래부터 수록한다. genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하이다. 고유번호는 index이다. 장르 종류는 100개 미만이다. 장르에 속한 곡이 하나라면, 하나의 곡만 선택한다. 모든 장르는 재생된 횟수가 다르다.

문제풀이

장르 별 총 재생 횟수가 많은 것부터 적은 순서로 정렬해서 이 순서로 노래를 수록한다. 같은 장르 속 노래들을 재생 횟수가 많은 것부터 적은 순서로 정렬해서 이 순서로 노래를 수록한다. 재생 횟수가 같다면 인덱스가 작은 것부터 큰 순서로 정렬한다. 만약 장르 속 노래가 하나라면 하나만 선택한다. 두개 이상이면 가장 재생이 많이 된 노래 2개를 선택한다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

bool cmp_genres(const pair<string,int>& a, const pair<string,int>& b) {
    return a.second > b.second;
}

bool cmp_plays(const pair<int,int>& a, const pair<int,int>& b) {
    if(a.second == b.second)
        return a.first < b.first;
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    unordered_map<string, vector<pair<int, int>>> gp_map;
    unordered_map<string, int> gp_sum;

    for(int i=0; i<genres.size(); i++){
        gp_sum[genres[i]] +=plays[i];
        gp_map[genres[i]].push_back(pair(i, plays[i]));
    }

    vector<pair<string,int>> gp_sumV(gp_sum.begin(), gp_sum.end());
    sort(gp_sumV.begin(), gp_sumV.end(), cmp_genres);

    for(int i=0; i<gp_sumV.size(); i++){
        string genre = gp_sumV[i].first;

        if(gp_map[genre].size() == 1){
            answer.push_back(gp_map[genre][0].first);
        }
        else{
            sort(gp_map[genre].begin(), gp_map[genre].end(), cmp_plays);
            answer.push_back(gp_map[genre][0].first);
            answer.push_back(gp_map[genre][1].first);
        }
    }

    return answer;
}

시간 복잡도

O(N*MlogM) N : 장르 개수 M : 장르 속 노래 최대 개수

문제 풀 때 참고 사이트

C++ Map을 value 기준으로 정렬하기

프로그래머스 - 위장

문제 설명

스파이가 가진 서로 다른 옷의 조합의 수 return하기

제한사항

스파이가 가진 의상의 수는 1개 이상 30개 이하이다. 모든 문자열의 길이는 1 이상 20 이하인 자연수이다. 모든 문자열은 알파벳 소문자 또는 _ 로만 이루어져 있다. 스파이는 하루에 최소 한 개의 의상은 입는다.

문제풀이

옷의 종류를 나눠서 map을 만든다. (모자, 상의, 하의끼리 나눈다.) map에서 key는 옷의 종류이고 value는 종류의 개수이다.

*각 종류의 개수 + 1 * 한 값을 모두 곱한다. 1을 더하는 이유는 해당 종류의 옷을 선택하지 않는 경우를 포함하기 위해서! 결과에 1을 빼주면서 아무 옷도 입지 않는 경우를 제외시킨다.

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<vector<string>> clothes) {
    int answer = 1;
    map <string, int> Clothes;
    vector<string> clothesKinds;

    for(int i=0; i<clothes.size(); i++){
        if(Clothes[clothes[i][1]] == 0){
            Clothes[clothes[i][1]] = 1;
            clothesKinds.push_back(clothes[i][1]);
        }
        else{
            Clothes[clothes[i][1]]++;
        }
    }

    map <string, int>::iterator iter; 
    for(iter=Clothes.begin(); iter!=Clothes.end(); iter++){
        answer*=iter->second+1;
    }

    return answer-1;
}

시간 복잡도

Θ(N)

문제 풀 때 참고 사이트

map container 정리 및 사용법 vector container 정리 및 사용법

프로그래머스 - 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우 확인하기. 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return.

제한사항

phone_book의 길이는 1 이상 1,000,000 이하이다. 각 전화번호의 길이는 1 이상 20 이하이다.

문제풀이

phone_book 을 정렬하고 바로 다음에 오는 값의 접두사인지 확인한다. 사전순으로 정렬했기 때문에 바로 다음 값만 확인하면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;

    sort(phone_book.begin(), phone_book.end());

    for(int i=0; i<phone_book.size()-1; i++){
        if (phone_book[i] == phone_book[i+1].substr(0, phone_book[i].size())){
            answer = false;
            break;
        }
    }

    return answer;
}

시간 복잡도

O(nlogn)

문제 풀 때 참고 사이트

map container 정리 및 사용법 vector container 정리 및 사용법

프로그래머스 - 완주하지 못한 선수

문제 설명

participant과 completion을 비교해서 완주하지 못한 선수의 이름을 return한다.

제한사항

완주하지 못한 선수는 항상 1명이다. 마라톤 경기에 참여한 선수의 수 는 1 ~ 100,000명이다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자. 동명이인이 존재한다.

문제풀이

participant과 completion을 정렬하고 같은 index에 같은 값이 있는지 확인한다.

다른 경우 participant에 있던 값을 answer에 저장한다.

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    answer = participant[participant.size()-1];

    for(int i=0; i<completion.size(); i++){
        if(completion[i] != participant[i]){
            answer = participant[i];
            break;
        }
    }

    return answer;
}

문제 풀 때 참고 사이트

map container 정리 및 사용법 vector container 정리 및 사용법