알고리즘

[Do It] 첫째 마당 : 코딩 테스트 준비하기

Ynghan 2023. 3. 15. 15:49

01 어떤 알고리즘으로 풀어야 할까?

01-1 시간 복잡도 표기법 알아보기

시간 복잡도 유형

  • 빅-오메가 : best case의 연산 횟수
  • 빅-세타 : average case의 연산 횟수
  • 빅-오 : worst case의 연산 횟수

시간 복잡도 예제 코드

다음은 0~99 사이의 무작윗값을 찾아 출력하는 코드입니다.

public class timeComplexityExample1 {
	public static void main(String[] args) {
    	// 1~100 사이 값 랜덤 선택
        int findMember = (int)(Math.random() * 100);
        for(int i = 0; i < 100; i++) {
        	if(i == findNumber) {
            	System.out.println(i);
                break;
            }
       	}
    }
}

빅-오메가 표기법의 시간 복잡도는 1번
빅-세타 표기법의 시간 복잡도는 N/2번
빅-오 표기법의 시간 복잡도는 N번

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용해야 할까?

빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋다.
시간 복잡도를 판단할 때는 최악일 때를 염두에 둬야 한다.

 

01-2 시간 복잡도 활용하기

시간 복잡도의 개념을 코딩 테스트에 어떻게 활용해야 할까?

가정 : 버블 정렬과 병합 정렬의 시간 복잡도가 각각 O($n^2$), O(($n\log n$)이다.

문제 0. 수 정렬하기

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

연산 횟수 계산 방법
연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기

알고리즘 적합성 평가
 - 버블 정렬 = (1,000,000)$^2$ = 1,000,000,000,000 > 200,000,000 → 부적합 알고리즘
 - 병합 정렬 = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 → 적합 알고리즘

이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있다. 즉, 데이터의 크기(N)를 단서로 사용해야하는 알고리즘을 추측할 수 있다.

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

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다.
이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.

시간 복잡도 도출 기준

  1. 상수는 시간 복잡도 계산에서 제외한다.
  2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

연산 횟수가 N$^2$인 경우

public class 시간복잡도_판별원리3 {
	public static void main(String[] args) {
    	int N = 100000;
        int cnt = 0;
        for(int i = 0; i < N; i++) {
        	for(int j = 0; j < N; j++) {
            	System.out.println("연산 횟수:" + cnt++);
            }
        }
    }
}

시간 복잡도는 가장 많이 중첩된 반복문을 기준으로 도출하므로 이 코드에서는 이중 for문이 전체 코드의 시간 복잡도 기준이 된다. 만약 일반 for문이 10개 더 있다 하더라도 도출 원리의 기준 2에 따라 시간 복잡도의 변화 없이 N$^2$으로 유지된다.

02 코드의 논리 오류를 어떻게 잡을까?

02-1 디버깅은 왜 중요할까?

디버깅 : 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정

문법 오류는 컴파일러가 자동으로 찾아 주므로 테스트할 때 문제가 되지 않습니다.
논리 오류는 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생합니다.

디버깅의 중요성

디버깅은 코딩 테스트에 필요한 기술이고, 그냥 알아 두기만 하면 되는것이 아니라 문제를 풀면서 반드시 해야 하는 과정입니다.
반드시 디버깅을 익힌 후에 코딩 테스트에 응시하기 바랍니다.

디버깅하는 법

디버깅을 하는 방법은 코드에서 디버깅하고자 하는 줄에 중단점을 설정하고, IDE의 디버깅 기능을 실행해 진행하면 됩니다.

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testcase = sc.nextInt();
        int answer = 0;
        int A[] = new int[100001];
        int S[] = new int[100001];
        for(int t = 1; t < testcase; t++) {
            int query = sc.nextInt();
            for(int i = 0; i < query; i++) {
                int start = sc.nextInt();
                int end = sc.nextInt();
                answer += S[end] - S[start - 1];
                System.out.println(testcase + " " + answer);
            }
        }
    }
}

디버깅으로 논리 오류를 찾아보겠습니다.

오류 1. 변수 초기화 오류 찾아보기
: 1번째 오류는 변수 초기화 로직에서 초기화를 제대로 하지 않은 경우입니다. 다음 화면에서 변숫값 기능을 보여 주는 Variables 탭을 봅시다.

 

저작자표시 (새창열림)