'22.08.02 Today I Learned

<학습내용>

- 알고리즘

 

 

---

 

1. 알고리즘

 

오늘도 역시 알고리즘과 자료구조에 대해서 공부했다. 여전히 알고리즘과 자료구조는 굉장히 어렵고 머리가 지끈거린다. 그럼에도 피할 수 없다면 내가 여기에 적응하는 수밖에 없다. 

 

 

> 이진탐색

 

이진탐색은 특정 데이터를 찾는 방법 중 하나이다. 가령 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이라는 배열에서 8이라는 데이터를 찾아야 한다면 방법이 여러개가 있을 것이다.

 

이진탐색은 절반씩 나눠서 데이터를 찾는 것이다. 우선 절반인 5보다 큰지 작은지 확인을 하고, 만약 크다면 그 이후부터는 6, 7, 8, 9, 10 에서 찾을 수 있다. 그럼 여기서 또 절반이 되는 8을 기준으로 큰지 작은지 확인을 하면 된다. (이 경우엔 8이 이미 나왔기 때문에 탐색을 멈추게 된다)

 

이런 식으로 범위를 좁혀가면서 탐색을 하기 때문에 시간복잡도 측면에서 유리하다는 장점이 있다. 다만 이진탐색을 사용하기 위해서는 탐색하고자 하는 자료가 정렬이 되어 있어야 한다.

 

> 재귀

 

재귀란 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 의미한다. 재귀 알고리즘의 대표적인 예는 팩토리얼, 회문 검사 등이 있다. 재귀 알고리즘을 짤 때 중요한 것은 늘 탈출조건을 명시해야된다는 것이다. 그렇지 않으면 무한루프에 빠질 수 있다.

 

 

> 정렬

 

정렬은 말 그래도 자료들을 일정한 규칙을 가지게끔 재배치하는 것이다. 대표적으로 오름차순, 내림차순 등이 있겠다.

 

정렬의 종류에는 버블정렬, 선택정렬, 삽입정렬, 병합정렬 등이 있다. 

 

• 버블정렬: 바로 옆에 있는 자료들을 비교하면서 크기를 비교해서 정렬 규칙에 맞게 재배치하는 것을 의미한다.

• 선택정렬: 특정 데이터를 선택한 다음 그것을 정렬하는 것이다. 

• 삽입정렬: 각 자료를 알맞은 위치에 삽입함으로써 자료를 규칙에 맞게 재배치하는 것이다.

• 병합정렬: 분할정복의 개념을 사용해서 자료를 재배치하는 것이다. 가령 [1,4,3,2,5,7,6,8] 이라는 자료를 병합정렬로 재배치한다고 하면 절반을 나눠서 [1,4,3,2] 와 [5,7,6,8] 이렇게 나누고 이것을 1,4 / 3,2 와 5,7 / 6,8 이렇게 반으로 나누고 이걸 또 반으로 나눠서 각각에 대해서 정렬을 하는 것이다. 조금 더 쉽게 이해하자면 정렬이 되지 않은 배열을 작은 단위로 쪼개서 각 단위를 우선 정렬하고 그 정렬된 것을 합치는 식으로 자료들을 정렬하는 것이다.