📚 Computer Science

[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이 된 노드를 큐에 넣..