코딩테스트 - 패스트캠퍼스 챌린지 08일차

수강한 강의
Chapter 12 기본 정렬 알고리즘
- 참고: 공간복잡도

학습 후기
 저번 강의까지 자료구조에 대한 강의를 끝내고, 이번 강의부터 알고리즘 관련 강의가 시작되었다. 저번 강의 중에 복잡도 관련하여 시간 복잡도와 공간 복잡도가 있다고 했고 저번 강의에서 시간 복잡도에 대해 자세히 이야기 해주었다면 이번 강의에서는 공간 복잡도에 대한 설명을 더해주는 강의였다.
 좋은 알고리즘이란 실행 시간도 짧고, 공간도 적게 차지하는게 좋은 알고리즘인데 요즘에는 대용량 시스템이나 하드웨어의 발전으로 공간복잡도의 영향이 덜 해 공간복잡도 보다는 시간복잡도에 조금 더 가중치를 두는 편이다. 하지만 코딩테스트에서는 공간복잡도에 대한 제약 사항이 있는 경우가 있기 때문에 공간 복잡도까지 신경써서 구현해야 한다.
 공간복잡도에 대한 예시로 팩토리얼 함수를 말씀해 주셨는데 같은 팩토리얼을 구하는 함수라도 함수를 구현하는 방식에 따라 공간복잡도가 달라짐을 알려주셨다.

public int forFactorial(int n) {
    int total = 1;
    for(int i = 1; i <= n; i++) {
    	total = total * i;
    } 
    return total;
}

public int recursiveFactorial(int n) {
    if (n < 2) {
    	return 1;
    }
    return n * recursiveFactorial(n - 1);
}

 그냥 for문으로 팩토리얼을 구현할 때(1)와 재귀 함수로 팩토리얼을 구현할 때(2)의 공간 복잡도는 다르다. (1)번의 경우 공간 복잡도는 함수 안의 변수들 갯수만 관여하여 O(1)이지만 (2)의 경우는 재귀 함수를 호출할 때 마다 스택에 쌓이게 되므로 공간복잡도는 O(N)이다. 공간 복잡도에 대해 공부하다보니 예전에 한 게임에서 어떤 성향치의 최대값이 32767인 걸 보았는데 아마 c언어의 short값을 사용하여 수치를 표현했던 것 같다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.