[코딩테스트 합격자 되기 스터디] 1주차 - 시간복잡도

우연한 기회로 인프런에서 코딩테스트 합격자 되기 스터디원 모집 공고를 보고 신청하게 되었다.

열심히 공부해서 스터디가 끝난 후에는 코딩테스트에 자신감이 붙을 수 있도록 노력해야지..

그리고 올해 안에 이직도 성공할 수 있기를! 🍀

---

[알고리즘]

📝 알고리즘 : 어떠한 문제를 해결하기 위한 일련의 규칙이나 절차

다음 조건을 충족해야 한다.

- 정밀성 : 변하지 않는 명확한 작업 단계를 거쳐야 함

- 유일성 : 각 단계마다 명확한 다음 단계를 거쳐야 함

- 타당성 : 구현할 수 있고 실용적이어야 함

- 입력, 출력

- 유한성 : 일정한 시간 내에 결과를 도출해야 함 (무한루프 X)

- 일반성 : 모든 입력들에 대해 적용할 수 있어야 함 (특정한 경우에만 적용된다면 일반성을 만족시키지 않음)

 

📝 알고리즘의 성능 측정 방법

• 연산 횟수 측정 - 코드가 동일하면 연산횟수가 모두 동일하므로 객관적 지표로 사용 가능함. 연산횟수는 환경에 영향을 받지 않으나 입력값에 따라 달라질 수 있음
  
  • 예시) 입력값에 따른 연산 횟수가 일정하지 않은 경우

#include <iostream>

using namespace std;

void solution(int n) {
	if(n%2 == 0) {
    	for (int i = 0; i < n*n; ++i) {
        	cout << i << endl; 
        }
    } else {
    	for (int i = 0; i <= n; ++i) {
        	cout << i <<endl;
        }
    }
}

위 코드에서 연산횟수를 구하면 N이 짝수인 경우 N^2, N이 홀수인 경우 N 이 되므로 연산횟수가 일정하지 않다.

코딩테스트에서는 최악의 경우를 기준으로 연산횟수를 정한다.

 

입력값에 따른 연산횟수를 측정해서 알고리즘의 성능을 지표로 나타내는 것을 시간복잡도 라고 한다.

 

[점근적 표기법]

• 정확한 연산횟수가 아닌, 연산횟수의 추이를 활용해 시간복잡도 표기
• 최악의 경우를 고려해서 점근적 표기법으로 나타내는 것을 빅오표기법이라고 한다.
  
  • 방법
    1. 다항식에서 가장 많이 영항을 미치는 항을 남기고 제거
    2. 마지막 남은 항의 계수를 제거

📝 예시) 3x^2 + 5x + 6  을 빅오 표기법으로 표기하면  O(x^2)    -> 다항함수로 구성되어 있으므로 최고차항 x^2만 남음 x + logx 을 빅오 표기법으로 표기하면 O(x)    -> 다항함수와 로그함수로 구성되어 있음. 증가폭이 더 낮은 로그함수는 사라지고 다항함수만 남음

 

[점근적 표기법의 코딩테스트 활용 방법]

• 주어진 입력값의 크기를 통해 어느 정도 시간복잡도 까지 허용되는지 추측 가능
• 구현 시 어떤 자료구조/알고리즘을 선택할 지 명확히 할 수 있음
• 구현한 코드가 시간초과 발생할 것인지 미리 파악 가능

---

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]