프로그래밍 기초
-
삽입 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 5. 11:31
삽입 정렬 선택 정렬과 버블 정렬과 달리 1개짜리 배열로 시작하여 크기를 하나씩 늘려나가는 방식으로 정렬을 진행한다. 삽입 정렬 알고리즘 배열 A[1...n]에 대해 A[n] < A[i] 인 i를 찾아 A[n]과 A[i]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 삽입 정렬 알고리즘 InsertionSort(A[], n) { for i ← 2 to n { A[1...i]의 적당한 자리에 A[n]을 삽입한다 } } ※ 삽입 정렬 알고리즘의 비교 회수는 n ~ n² 사이가 되며 시간 복잡도는 최선의 경우 Ο(n), 최악의 경우 Ο(n²)이 된다. 삽입 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. InsertionSor..
-
버블 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 7. 1. 21:16
버블 정렬 선택 정렬과 비슷하게 가장 큰 원소를 가장 끝의 자리로 옮기는 정렬이다. 다만, 이동시키는 방식이 바로 오른쪽 값과 비교하여 교체해주는 것으로 선택 정렬과 차이를 갖는다. 버블 정렬 알고리즘 배열 A[1...n]에 대해 A[1] > A[2] 인 경우 A[1]과 A[2]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 버블 정렬 알고리즘 BubbleSort(A[], n) { for last ← n downto 2 { for i ← 1 to last - 1 { if (A[i] > A[i+1]) then { A[i] ↔ A[i+1] } } } } ※ 버블 정렬 알고리즘의 비교 회수는 n(n-1)/2 이며 시간 복잡도는 Ο(n²)이다. 버블 정렬..
-
선택 정렬 구현 및 테스트프로그래밍 기초/알고리즘 2021. 6. 25. 14:43
선택 정렬 여러 정렬 알고리즘 중 가장 간단한 알고리즘 중 하나이다. 선택 정렬 알고리즘 배열 A [1... n]에서 가장 큰 원소를 찾아 A [n]과 자리를 바꾼다. 이 과정을 [1... n-1]에 대해 반복한다. 이를 수도 코드로 나타내면 다음과 같다. 선택 정렬 알고리즘 SelectionSort(A[], n) { for last ← n downto 2 { A[1...last] 중 가장 큰 수 A[k]를 찾는다. A[k] ↔ A[last] } } ※ 선택 정렬 알고리즘의 비교 회수는 n(n-1)/2 이며 시간 복잡도는 Ο(n²)이다. 선택 정렬 구현 배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다. SelectionSort.hpp #pragma once #include "../Commo..
-
정렬 알고리즘 개요프로그래밍 기초/알고리즘 2021. 6. 23. 08:26
정렬 알고리즘 정렬이란? n개의 원소를 순서대로 배열하는 것으로 실생활에 다양하게 사용되는 알고리즘이다. 가령 학생을 키 순서대로 줄을 세운다거나 세무서에서 고지서를 날리기 위해 주민등록 번호순으로 정렬하는 것 등을 예로 들 수 있다. 정렬의 종류 정렬에는 여러 종류가 있으며 대표적으로 다음과 같은 정렬이 존재한다. 선택 정렬 가장 큰 원소 또는 가장 작은 원소를 찾아 첫 위치 또는 마지막 위치와 자리를 바꾸는 정렬, 평균 Ο(n²) 버블 정렬 두 개의 원소를 비교하여 정렬 방향에 따라 서로 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(n²) 병합 정렬 원소를 두 구역으로 나누는 것을 반복한 뒤 병합하며 자리를 바꾸는 연산을 반복하는 정렬, 평균 Ο(nlogn) 퀵 정렬 특정 값을 기준으로 영역을 나누..
-
알고리즘과 귀납적 사고프로그래밍 기초/알고리즘 2021. 5. 20. 08:57
알고리즘과 귀납적 사고 알고리즘이란? 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것으로 알고리즘을 설계하기 위해서는 해야 할 작업을 명확하게 명시해야 한다. ※ 알고리즘이 명확하다는 것은 모호하지 않고 이해하기 쉬운 것을 의미하며 자세한 것과는 다르다. 알고리즘은 가능하면 효율적이어야 하며 그중 작은 입력보다는 충분히 큰 입력에 대해 관심을 가져야 한다. 이렇게 큰 입력에 대한 분석을 점근적 분석(Asymptotic Analysis)라고 한다. 알고리즘을 분석하는 이유 어떠한 입력을 일정 시간 이내에 처리해야 할 때 적용할 수 있는 알고리즘의 시간 분석을 하면 각 알고리즘이 어느 정도의 시간이 소요되는지 파악하여 적절한 알고리즘을 적용할 수 있다. ※ 일반적인 상황에서..
-
인접 리스트를 통한 그래프 구현프로그래밍 기초/자료구조 2021. 5. 3. 09:37
인접 리스트 통한 그래프 구현 그래프 구현/인접 리스트 인접 리스트는 각각의 노드를 하나의 포인터로 하여 특정 노드에서 이동 가능한 노드를 표현하는 방법으로 다음과 같이 표현된다. 구현이 필요한 메서드 및 속성은 다음과 같다. 생성자 ArrayListGraph() 비어있는는 인스턴스 생성 속성 NodeCount 현재 노드의 개수 메서드 InsertNode() 노드 추가 InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가 RemoveNode(int) 지정된 인덱스의 노드 제거 RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 제거 Clear() 저장되어 있는 모든 데이터 삭제 GetDegreeIn(int) 노드의 진입 차수 반환 GetDegreeOut(i..
-
인접 행렬을 통한 그래프 구현프로그래밍 기초/자료구조 2021. 4. 22. 20:21
인접 행렬을 통한 그래프 구현 인접 행렬로 그래프를 표현하는 것은 다음과 같이 각각의 노드가 순서대로 존재하는 것으로 가정하여 표현하는 것이다. 구현이 필요한 메서드 및 속성은 다음과 같다. 생성자 ArrayGraph() 비어있고 기본 초기 용량을 가지는 인스턴스 생성 ArrayGraph(int) 비어있고 지정한 초기 용량을 가지는 인스턴스 생성 속성 NodeCapacity 노드의 최대 개수 NodeCount 현재 노드의 개수 메서드 InsertNode() 가능할 경우 노드 추가 InsertEdge(int, int) 앞의 노드에서 뒷 노드로 이동하는 에지 추가 RemoveNode(int) 지정된 인덱스의 노드 제거 후 모든 데이터 위치 조정 RemoveEdge(int, int) 앞의 노드에서 뒷 노드로 ..
-
그래프(Graph)프로그래밍 기초/자료구조 2021. 4. 8. 11:15
그래프 그래프는 연결되어 있는 원소 간의 관계를 표현하는 자료구조이다. 그래프의 구성요소 노드(또는 정점) 데이터 저장 및 표현 간선 데이터 간의 관계 표현 그래프의 종류 그래프는 방향성과 연결 정도에 따라 구분하며 추가로 간선에 가중치를 할당한 그래프가 존재한다. 무방향 그래프(Undirected Graph) 두 노드를 연결하는 간선의 방향이 없는 그래프 방향 그래프(Directed Graph) 노드를 연결할 때 간선에 방향이 있는 그래프 완전 그래프(Complete Graph) 정점이 모두 서로 연결된 그래프 부분 그래프(Subgraph) 완전 그래프에서 특정 간선이 제외된 그래프 가중 그래프(Weigh Graph) 간선마다 가중치가 할당된 그래프 그래프의 표현) 그래프는 방향성에 따라 다르게 표현된..