오늘은 식목일~ 나무가 잘 자라라고 봄비가 내리나 보다 🌳🌧️
기술 면접 스터디
✅ 알고리즘에서 '시간복잡도' 와 '공간복잡도' 란 무엇인가? 그리고 이것들은 왜 중요한가?
🌳 시간 복잡도
특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미.
알고리즘이 진행되는데 걸리는 실행시간이 아니라, 연산 횟수라는 것에 유의해야함.
시간과 공간은 반비례적 경향이 있고, 최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선 시 되며 알고리즘은 시간 복잡도가 중심이다. 제한 시간내에 빠른 속도로 처리해주어야하기 때문이다.
💡 계산 방법
- Big-O(빅-오)
- Big-Ω(빅-오메가)
- Bid-θ(빅-세타)
세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대해 나타내는 방법다.
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.
💡 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법
faster
O(1) (Constant)
입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘.
데이터가 얼마나 증가하든 성능에 영향을 거의 미치지 않는다.
O(log₂ n) (Logarithmic)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log: 지수 함수의 역함수) 만큼 짧아지는 알고리즘.
예를 들어 데이터가 10배가 되면, 처리 시간은 2배가 된다. 이진 탐색이 대표적이며, 재귀가 순기능으로 이루어지는 경우도 해당된다.
O(n) (Linear)
입력 데이터의 크기에 비례해 처리 시간이 증가하는 알고리즘.
예를 들어 데이터가 10배가 되면, 처리 시간도 10배가 됩니다. 1차원 for문이 있다.
O(n log₂ n) (Linear-Logarithmic)
데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어나는 알고리즘.
예를 들어 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합 정렬, 퀵 정렬이 대표적이다.
O(n²) (quadratic)
데이터가 많아질수록 처리시간이 급수적으로 늘어나는 알고리즘.
예를 들어 데이터가 10배가 되면, 처리 시간은 최대 100배가 된다. 이중 루프(n² matrix)가 대표적이며 단, m이 n보다 작을 때는 반드시 O(nm)로 표시하는 것이 바람직하다.
O(2ⁿ) (Exponential)
데이터량이 많아질수록 처리시간이 기하급수적으로 늘어나는 알고리즘.
대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다.
slower
💡 시간복잡도 줄이는 법
- 반복문이 가장 시간 소모에 가장 큰 영향을 미치므로 반복문을 줄여야 한다..
- 조건문을 줄이는 것이다.
너무 많은 조건문이 있다면 거기서 한번씩 멈추기 때문에 시간이 n * 조건문 숫자 만큼 된다. - 자료구조를 적절하게 이용해야 한다.
가장 효율적인 자료구조들을 적절히 사용한다면 시간 복잡도를 최대한 줄일 수 있다. - 알고리즘을 적절하게 이용하는 것이다.
대표적으로 이진 탐색, 그리디 알고리즘, 정렬 알고리즘 등이 있을다. 효율적인 알고리즘을 공부해뒀다가 적절할 때 사용한다면 큰 효과를 볼 수 있다.
🌳 공간 복잡도
작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법이다.
💡 공간복잡도 계산법 (빅-오)
int a = 10;일반적으로 공간이 하나씩 생성되는것을 1이라고 표현한다. 위의 공간복잡도는 O(1) 이다.
int get_factorial(int n)
{
int i = 0;
int result = 1;
for(i = 1; i <= n; i++)
{
result = result * i;
}
return result;
}반복문이 N번만큼 반복하여도 for문 안에서의 지역변수이므로 위의 공간복잡도는 O(1) 이다.
n의 값에 상관없이 함수를 호출하고 i와 result의 변수만 사용된다. 다른 것은 전혀 영향을 주지 못한다.
int get_factorial(int n)
{
if(n > 1) return n * factorial(n - 1);
else return 1;
}🚨 재귀함수일 경우에는 이야기가 달라진다.
함수 내부에서 n이 1이하 일 때까지 팩토리얼을 구하는 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이며 위의 공간 복잡도는 O(n) 이다.
여기서 이러한 생각을 가지신 분이 계실 수 있다. 함수 밖으로 나오면 저것은 사라지니까 O(1)이 아닌가?
알고리즘은 한 번 실행하여 종료 될 때까지가 공간 복잡도 이다. 재귀의 경우 뒤에서 부터 하나씩 변수를 가지고 있기 때문에 n부터 1까지 모두 쌓이므로 공간 복잡도는 O(n) 이라고 한다.
🌧️ 참고 블로그
✅ 오버로딩과 오버라이딩의 차이점
🌳 오버로딩 : 메서드 명이 같지만 파라미터가 다른 메서드
- 메서드명이 같아야 한다.
- 매개변수의 갯수 또는 타입이 달라야 한다.
- 리턴 타입만 다르면 오버로딩이 성립되지 않는다.
대표적인 예로는 println() 메서드가 있다.
🌳 오버라이딩 : 부모 클래스에서 정의한 메서드를 자식 클래스에서 재정의
- 부모 클래스의 메서드와 메서드 구성 요소 모두가 동일해야 한다.
- 메서드명, 매개변수, 리턴 타입이 모두 같아야 한다.
자바에서 자식 클래스는 부모 클래스의 private 멤버를 제외한 모든 메서드를 상속 받는다. 이렇게 상속받은 메서드는 그대로 사용해도 되고, 필요한 동작을 위해 재정의하여 사용할 수도 있다.
즉, 메서드 오버라이딩이란 상속받은 부모 클래스의 메서드를 재정의하여 사용하는 것을 의미한다.
🌠 정리
오버로딩과 오버라이딩은 둘 다 '다형성'을 가졌지만
오버로딩 - 기존에 없는 새로운 메소드를 추가하는 것
오버라이딩 - 상속받은 메소드를 재정의 하는 것
이라는 큰 차이점이 있다.
이 외에도 표와 같은 차이점들이 있다.
| 구분 | Overriding | Overloading |
| 접근 제어자 | 부모 클래스의 메소드의 접근 제어자보다 더 넓은 범위의 접근 제어자를 자식 클래스의 메소드에서 설정할 수 있다. |
모든 접근 제어자를 사용할 수 있다. |
| 리턴형 | 동일해야 한다. | 달라도 된다. |
| 메소드명 | 동일해야 한다. | 동일해야 한다. |
| 매개변수 | 동일해야 한다. | 달라야만 한다. |
| 적용 범위 | 상속관계에서 적용된다. | 같은 클래스 내에서 적용된다. |
🌧️ 참고 블로그