<aside> 💡

알고리즘 기출은 C++로 풀이

• PS Profile 링크

</aside>

목표

1. 업무에 필요한 사고력과 기본적인 알고리즘 기본지식
2. PS 코딩 테스트를 대비

코드 작성요령

시간, 공간 복잡도

<aside> 💡

시간 및 메모리 제한

</aside>

시간제한

<aside> 💡

컴퓨터는 1초에 대략 3-5억

</aside>

int func1(int arr[], int n) {
	int cnt = 0; // cnt 대입 1번
	for(int i = 0; i < n; i++) { // i 대입, 1번 / n번 반복 ( i와 n을 비교 1번, i 증가 1번 )
		if(arr[i] % 5 == 0) cnt++; // n번 반복 ( arr[i]%5 연산 1번, 0과 비교 1번, cnt 증감 1번 )
	}
	return cnt; // 반환 1번
}

위 코드에서 필요한 연산은 1+1+n*(2+2+1)+1 = 5n + 3

⇒ n에 비례한 연산횟수, 대표항만 남겨서 나타내면 Big-O표기법 O(N)

ex)

n = 1,000,000, 대략 5,000,000만번 연산

…

n = 1,000,000,000, 대략 5억번 연산 ( 마지노선 )

내용

C++로 풀이하는 이유가 있는가?

c++은 포인터의 잘못된 사요이나, 인덱스 범위 초과, integer overflow와 같은 문제가 발생할 수 있고, 문자열 처리에 어려움이 있지만

실행속도에서의 이점과 알고리즘 학습에 대한 자료들이 대부분 C++로 제공되고 있기 때문에 구현에 기본적이 어려움이 없다면 C++이 조금 더 유리할 것이라고 생각

알고리즘 종류

배열

스택