📅 오늘 한 일
1. 자료 구조 / 알고리즘 개념 공부
2. 프로그래머스 문제 풀이
✏️ 무엇을 배웠나
데이터 구조 aka 자료 구조란?
데이터 구조(자료 구조)는 데이터를 어떻게 구성하고 저장하는지 그리고 개별적인 데이터를 어떻게 식별하고 데이터 사이의 관계는 어떤지 보여주는 개념이다. 데이터 구조는 메모리 같은 자원을 효과적으로 관리하기 위해 존재한다.
알고리즘이란?
알고리즘은 어떤 문제를 해결하기 위해 밟아야 하는 논리적인 절차를 말한다.
EX) 라면 끓이는 알고리즘
1. 냄비에 물을 받는다
2. 냄비를 가지고 인덕션 앞으로 이동한다
3. 냄비를 인덕션 위에 올리고 인덕션 전원을 켠다
4. 봉지에서 라면을 꺼낸다
5. 건면을 냄비에 넣는다
6. 스프를 넣는다
7. 3분 30초 후에 인덕션 전원 끈다
재귀와 반복
1) 재귀는 한자를 풀이하면 '다시 돌아옴'을 뜻한다. 재귀함수는 실행 도중 자신을 또 호출하는 함수를 말한다. 재귀함수가 자신을 계속 호출하게 되면 결국 메모리가 부족해지고 한계치인 최대 재귀 깊이를 넘어가면 그 유명한 스택 오버 플로우 에러가 발생한다.
2) 반복은 어떤 조건을 만족시킬 때까지 코드가 실행되는 것을 말한다. 재귀도 어찌 보면 반복적이지만 다른 개념이다. 재귀는 자기 자신을 호출하는 것이고 반복은 자기 자신을 호출하는 게 아니라 조건에 의해 반복되는 것이다.
알고리즘은 보통 재귀나 반복을 사용하기 때문에 재귀와 반복의 개념을 인지해야 함
알고리즘의 유형
- 분할 정복 알고리즘
큰 문제를 여러 개의 작은 단위의 문제로 나눠 해결하는 방법 - 탐욕 알고리즘
알고리즘이 실행될 때마다 맥락에 따라 그 안에서 가장 적당한 결정을 하는 방법. 전체적인 상황에서 그게 최선인가의 문제는 장담 못 함. - 동적 프로그래밍 알고리즘
탐욕 알고리즘과 달리 문제를 해결하는 여러 방법을 찾아 저장한 다음 추후에 재사용함.
알고리즘을 분석하는 방법
문제를 해결하기 위한 절차가 적을 수록 효율적인 알고리즘이다. 알고리즘의 효율성은 시간복잡도와 공간복잡도를 사용한다.
1) 시간복잡도
주어진 입력에 따라 문제를 해결하는 데 걸리는 시간을 측정하는 방법임. 알고리즘을 분석하는 데 쓰이는 가장 일반적인 방법
2) 공간복잡도
문제를 해결할 때 필요한 메모리를 측정하는 방법임. 메모리가 작았던 옛날에는 중요했지만, 요즘은 일반적인 상황에서는 거의 사용되지 않음.
빅 오 표기법
알고리즘의 효율성을 수학적으로 표현하는 방법임. 크게 최악의 경우, 최선의 경우, 보통의 경우를 측정할 수 있음. 빅 오메가 표기법은 최소 시간을 측정하고 빅 세타 표기법은 최소 + 최대 시간을 측정하는데, 빅 오 표기법은 실행 시간이 가장 느린 최악의 경우를 나타낸다.
빅 오 표기법 분류
- O(1) : 상수형 알고리즘. 입력값과 무관하게 시간이 일정함을 나타냄.
- O(n) : 선형 알고리즘. 입력값이 커질수록 시간이 늘어남을 나타냄.
- O(logn) : 로그형 알고리즘. 입력값이 커질수록 시간이 줄어듬을 나타냄.
- O(nlogn) : 선형-로그형 알고리즘. 입력값이 n배 늘어나면 시간이 n배보다 조금 넘게 늘어남을 나타냄.
- O(n의 2승) : 입력값이 커지면 시간이 그 제곱으로 늘어남을 나타냄.
- O(2의 n승) : 입력값이 커지면 시간이 2배로 늘어남을 나타냄.
- O(n!) : 입력값이 커질 때마다 시간이 n배로 늘어남을 나타냄.
성능이 좋은 순으로 정렬하면
- O(1) > O(logn) > O(n) > O(n의 2승) > O(2의 n승) > O(n!)
