섹션0. 코딩테스트 준비하기

안녕하세요 슐리반입니다.

강의 들은 내용 정리하겠습니다.

 

1. 시간복잡도

핵심 1) 시간복잡도

시간복잡도 : 연산 함수 (1억번 연산이 1초) -> c++이 제일 빠르다

 

< 시간복잡도 유형 >

   º  빅 오메가 : best case

   º  빅세타 : 평균
   º  빅오 : worst case

코딩테스트에서는 빅오를 기준으로 수행시간을 계산하는게 좋다.

 

< 시간복잡도 활용 기준>

1. 알고리즘 선택 기준으로 사용하기

   º   버블정렬 시간복잡도 : n^2
   º   병합정렬 시간복잡도 : nlogn

예시)
코딩테스트 문제 -> 시간 제한 : 2초
   º    여기서 도출할 수 있는 점!
   º    c++의 경우 1초에 1억번 연산을 함, 2초가 제한이라면 2억번 이하의 연산을 수행하는 알고리즘을 짜야함.
따라서, 문제에서 주어진 시간제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야할 것인지 판단이 가능함.

 

 

2. 시간 복잡도를 바탕으로 코드 로직 개선하기

   º   코드의 시간 복잡도를 도출할 수 있어야 한다. 
         1) 상수는 시간 복잡도 계산에서 제외
         2) 가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도의 기준이 된다
주의) for문만 반복문이 아니라 while문도 있다. 그렇기에 코드 상에서 전체 또는 절반의 데이터를 스캔하는 부분을 위주로 확인!
         시간복잡도는 가장 많이 중첩된 반복문을 기준으로 도출한다.

 

 

 

정리)
1. 시간복잡도는 최악의 케이스(빅오)
2. 시간복잡도 도출시 상수는 무시하고 가장 많이 중첩된 반복문 기준
3. 시간복잡도 활용 기준은 선택한 알고리즘을 기준
-> 시간 초과시 비효율적인 코드가 어떤 곳인지 판단 하기

 

 

2. 디버깅

코딩테스트에서 떨어진 주요 이유 중 하나는?

-> 코드에서 논리 오류를 찾아 내지 못함

 

해결책은 "디버깅 사용하기"

 

디버깅이란?

프로그램에서 발생하는 문법 오류 또는 논리 오류를 찾아 바로 잡는 과정
    º 문법오류 -> 컴파일러가 자동으로 찾아줌
    º 논리 오류 -> 코드가 사용자의 의도와 다르게 동작하는 것
*디버깅은 코딩테스트에 필요한 기술이고 문제를 풀면서 반드시 해야됨.

 

Q,.특정 코딩테스트에서는 디버깅 못하는데 공부하야하나요?
A. 네 해야합니다

 

<디버깅 중요성>

1. 디버깅을 많이 하다보면 컴퓨터의 프로세스대로 어떻게 동작이 되는지 이해할 수 있다.
2. 알고리즘의 동작원리를 이해할 수 있다.(재귀함수, dfs 등이 동작하는법을 자세히 이해할 수 있음.)

현업에서도 디버깅은 필수적이다.

 

<디버깅 하는법>

1. 코드에서 디버깅하고자 하는 중에 중단점을 생성한다. (중단점은 여러개 생성 가능)
2. IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며, 이 과정에서 추적할 변수도 지정할 수 있다. 이 방법으로 변수의 값이 자신이 의도한대로 바뀌는지 파악한다
3. 변수의 값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있다

    º 비쥬얼스튜디오에서는 로컬(local), 자동(auto), 조사식(watch)창을 활용하면 된다.(디버그 -> 창)

 

<코딩테스트 중 실수를 많이 하는 4가지 오류>

 º 오류1) 변수 초기화 오류
 º 오류2) 반복문에서 인덱스 범위 지정 오류

              반복문에서 반복 범위를 잘못 지정하거나 비교 연산자 <,<=를 잘못 사용하는 경우
 º 오류3) 잘못된 변수 사용 오류
              반복문에서 반복 변수가 아닌 기준 변수 사용하는경우. 즉, 변수 이름 자체가 비슷해서 잘못 사용하는 경우
 º 오류4) 자료형 범위 오류
              Tip. 음수가 나올 수 없는 구조인데 음수가 나왔을 경우 -> 자료형 범위확인

 

 

//예제
#include <iostream>
#include <cstdlib>
#include <climits>
using namespace std;

int main()
{
	int testcase;
	cin >> testcase;

	long long answer = 0;
	int A[100001] = { 0 };

	for (int i = 1; i < 10001; i++)
	{
		A[i] = rand() * 100;
	
	}

	for (int t = 1; t < testcase + 1; t++)
	{
		int start, end;
		cin >> start >> end;
		for (int i = start; i <= end; i++)
		{
			answer += A[i];
		}
		cout << testcase << " " << answer;
	
	}
}

 

 

 

<출처>

https://inf.run/aoFs

[무료] Do it! 알고리즘 코딩테스트 with C++ - 인프런 | 강의