병합/퀵 정렬, 이분/순차 검색, 최소비용 그래프

병합 정렬

오름차순으로 정렬된 배열 A(M)과 내림차순으로 정렬된 배열 B(N)을 병합 정렬하여 오름차순의 배열 C(M+N)을 생성하는 알고리즘(단, 배열 A(M)과 배열 B(N)에는 900000 이하의 정수가 저장되어 있으며, 모든 배열의 첨자는 1부터 시작한다).

• 오름차순 배열 A은 가장 첫번째 원소부터 검색을 시작하고, 내림차순 배열은 가장 끝 원소부터 검사를 시작한다.
• 새로 생성할 배열은 첫번째 원소부터 저장할 것이기 때문에 최솟값은 1로 잡아주고, 변수 Done으로 배열 처리의 종료 여부를 판단한다.
• 배열 A와 B의 두 원소를 비교하여 작은 값을 배열 C에 저장하고 인덱스를 증가시켜 다음 원소를 비교하는 작업을 반복한다. 배열 A 또는 B의 마지막 원소까지 처리했다면 변수 Done의 값을 1로 바꿔준다.
• 한쪽 배열이 모두 처리됐을 경우, 나머지 배열을 처리한 후 배열 C를 출력하고 알고리즘을 종료한다.

 

퀵 정렬

학생 100명의 영어 성적을 오름차순으로 퀵 정렬하는 알고리즘

• 정렬할 데이터의 개수가 2개 이상일 때만 진행하고, 2개 이상이 아닐 경우 퀵 정렬을 종료한다.
• 변수 P는 축 값으로, 가장 왼쪽의 데이터가 설정된다. 변수 i는 가장 왼쪽 값으로 초기화하고, 변수 j는 오른쪽부터 왼쪽으로 검사하기 위해 R+1을 가리키도록 초기화한다.
• 왼쪽 인덱스 변수를 하나 증겨시켜 해당 데이터가 축 값보다 작을 경우 오른쪽으로 이동하는 것을 반복한다. 해당 데이터가 축 값보다 클 경우, 오른쪽 인덱스 변수를 1 감소시키고 오른쪽에서 왼쪽으로 이동하는 것을 반복한다.
• i와 j를 비교해 i가 j보다 작으면 두 데이터의 값을 교환하고 다시 왼쪽 인덱스를 증가시켜 이 작업을 반복한다.
• i와 j를 비교했을 때 i가 j보다 작지 않으면 축 값과 j번째 데이터 값을 교환하고 왼쪽 그룹과 오른쪽 그룹에 대하여 퀵 정렬을 재귀적으로 호출한다.

 

이분 검색

다음과 같은 조건에서 배열 변수 E에 대하여 데이터 K가 잇는 위치를 찾아주는 이분 검색 알고리즘

- 자연수로 이루어진 배열 E의 전체 원소들은 미리 오름차순 정렬되어 있다고 가정한다.

- 이분 검색 대상인 배열 변수 E를 일반화하기 위하여 배열 E의 인덱스(하한 인덱스 L, 상한 인덱스 H)를 알고리즘에 매개변수로 넘겨 준다.

- 검색하여 발견한 위치의 배열 인덱스 값을 결과값으로 반환한다.

- 만일 찾고자 하는 데이터가 배열 전체에 존재하지 않으면 -99를 반환한다.

• 배열의 하한 인덱스, 상한 인덱스, 검색할 데이터(K)를 매개변수로 받아 실행된다.
• 배열의 하한 인덱스가 상한 인덱스보다 크면 이분 검색을 진행할 수 없으므로 -99를 출력하고 알고리즘을 종료한다.
• 배열의 하한 인덱스가 상한 인덱스보다 작다면, 중간 인덱스 M을 계산하고 E(M)과 K를 비교한다.
• E(M)이 K보다 크면, 상한 인덱스를 M-1로 조정하고 이분 검색을 계속 진행한다.
• E(M)이 K보다 작으면, 하한 인덱스를 M+1로 조정하고 이분 검색을 계속 진행한다.
• E(M)과 K가 같으면 답을 찾았으므로 M을 출력하고 알고리즘을 종료한다.

 

최소비용 그래프

어떤 그래프 G가 N개의 정점과 서로 다른 가중치를 갖는 E개의 간선으로 구성되어 있다고 가정하자. 주어진 간선을 따라 N개의 정점을 사이클없이 모두 연결할 때 포함된 간선의 가중치 총합이 가장 작은 경우를 차장 출력해주는 최소비용 그래프 알고리즘을 다음 조건을 고려하여 제시.

- 그래프 G의 모든 간선을 대상으로 가중치 기준 오름차순 선택 정렬을 실시하였을 때 X번째로 큰 가중치의 값이 배열 변수 C(X)에 저장된다(단, 1<=X<=E).

- 함수 Cycle(X)는 현재까지 만들어진 경로에 C(X)의 가중치를 갖는 간선을 추가했을 때 경로상에 사이클이 형성되는지 여부를 판단해주는 함수이다. 사이클이 형성되면 1, 형성되지 않았으면 0을 반환해 준다.

• 선택 정령의 단계 I를 나타내는 외부 반복문에서는 전체 데이터가 E개이므로 E-1까지 반복한다. 내부 반복문은 C(i)와 비교할 C(j)에 대한 반복문이다. 따라서, 내부 반복문은 i+1번째부터 E번째까지 반복한다.
• 내부 반복문 : C(i)와 C(j)를 비교하여 작은 값이 C(i)에 위치되도록 한다.
• 외부 반복문이 전부 끝나면, 변수 L(최소비용 그래프에 참여할 간선의 순번)과 변수 K(반복용 변수)를 1로 초기화하고, 변수 T(최소비용 그래프에 참여한 간선들의 가중치 총합)을 0으로 초기화한다.
• 총 노드 수 N개인 최소비용 그래프에 참여한 간선의 개수가 N-1개를 넘는 경우, T 값을 출력하고 알고리즈믕ㄹ 종료한다.
• 간선의 개수가 N-1개를 넘지 않는 경우, 이번 간선을 최소비용 그래프에 추가했을 때 사이클이 생성되지 않으면 간선을 추가하고, K를 1 증가시켜 다음으로 큰 가중치를 갖는 간선을 반복하여 검토한다. 사이클이 생성된다면, 간선 추가 없이 바로 K를 1 증가시켜 반복하여 검토한다.

 

순차 검색

배열 변수 E에 대하여 데이터 K가 있는 위치를 찾아주는 순차 검색 알고리즘

- 자연수로 이루어진 배열 E의 전체 원소들은 전혀 정렬이 이뤄지지 않았다.

- 순차 검색 대상인 배열 변수 E를 일반화하기 위하여 배열 E의 인덱스(하한 인덱스 L, 상한 인덱스 H)를 알고리즘에 매개변수로 넘겨 준다.

- 검색하여 발견한 위치의 배열 인덱스 값을 결과값으로 반환한다.

- 만일 찾고자 하는 데이터가 배열 전체에 존재하지 않으면 -99를 반환한다.

• 변수 i는 검색할 대상인 원소를 접근하기 위한 인덱스이다. 가장 왼쪽의 데이터부터 검사해야하므로 i는 L로 초기화한다.
• 배열 E에서 변수 K와 같은 값을 가지고 있는 원소를 찾은 후, 발견한 원소의 인덱스 값을 출력하고 알고리즘을 종료한다.
• 배열 E에서 변수 K와 같은 값을 가지고 있는 원소를 찾기 위해 인덱스 i를 증가시키는 과정에서 인덱스 변수 i의 값이 배열의 상한 인덱스(H) 값을 초과하면 -99를 출력하고 알고리즘을 종료한다.