1) 알고리즘이란?
- 알고리즘이란, 입력값을 출력값으로 바꾸기 위한 그 일련의 과정을 이야기한다. 어떤 명령이 수행되어야하는지 규칙적인 순서적 나열이라고 이야기할 수 있다.
- 알고리즘에서 중요한 것은 '정확성' 과 '효율성' 이다.
2) 알고리즘을 잘짜기 위해서는?
- 제대로된 출력값을 컴퓨터가 출력하게끔 하게 위해서는 프로그래밍 언어를 활용해야한다. 즉, 알고리즘을 표현하기 위한 언어는 자연어, 의사코드, 순서도 등이 있다.
- 프로그래밍 언어같은 경우는, 컴퓨터가 알아들을 수 있게 이미 정해진 코드를 짜야하지만 의사 코드(pseudocode)는 정해진 방법이 없으며 보다 명확하게 의미를 나타낼 수 있기 때문에 알고리즘을 이해하기 쉽다. 의사코드는 사람이 이해할 수 있는 말로 내가 해결해야하는 문제, 방법을 적어 표현하고 이를 프로그래밍 언어로 바꿔 적기만 하면 알고리즘을 적기 쉬워진다.
3) 선형탐색
- 알고리즘을 짤 때, 하나씩 확인하는 방식인 선형탐색을 활용한다면 아주 정확하지만 효율적이지는 못한 방식이다. 예를들어 확인해야하는 데이터가 100개라면, 100개를 모두 확인해야하기 때문에 100번을 실행해야한다. 선형탐색은 데이터가 정렬되어있지 않을때 활용하는게 맞다.
4) 버블정렬
- 정렬된 알고리즘 중 하나는 버블정렬이다. 정렬되지 않은 자료 값들을 인접한 값들과 비교하여 교환하는 방식으로 정렬하는 방법. 하지만 교환을 너무 많이 하는 경우가 있기 때문에, 가장 효율적인 방법은 아니다.
-의사코드(peusudo code)
for every element in the array
check if element to the right is smaller
if so swap the two elements
even move on to the next element in the list
5) 선택정렬
- 가장 큰 값, 가장 작은 값 하나를 찾아서 맨 왼쪽에 있는 값과 바꿔주고, 그다음 작은 값을 찾아 기억해 두번째 값과 바꿔주는 식으로 계속 다음 작은 값을 찾아 선택적으로 위치를 바꿔 정렬해주는 것. 순서가 마구잡이로 섞여있을 때, 버블정렬보다는 더 효율적인 방식이다.
-의사코드(peusudo code)
repeat for the amount of elements in the array
find the smallest unsorted value
swap that value with the first unsorted value
6) 삽입정렬
- 삽입 정렬은 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어있는 경우 효율적이다. 삽입정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮다.
- 의사코드(peusudo code)
for each unsorted element, n, in the array
determine where in the sorted portion of the array to insert n
shift sorted element rightwards as necessary to make room for n
insert n into sorted portion of the list
7)합병정렬
- 실행의 시간이 n log n의 값을 가진 정렬이고, 8개의 데이터가 있다면 반을 나눠 정렬하고, 또다른 반을 정렬한다. 그다음 큰 두개의 데이터를 합치는 방식이다.
-의사코드(peusudo code)
on input of n elements
if n < 2
return
else
sort left half of elements
sort right half of elements
merge sorted halves
