시간 복잡도/ 디버깅

1. 시간 복잡도

시간 복잡도는 어떤 작업을 수행하는 데 걸리는 시간을 어떻게 측정하는지에 대한 개념입니다. 이것은 주로 컴퓨터 과학에서 사용되며, 우리는 알고리즘(특정 작업을 수행하는 방법)의 효율성을 평가하기 위해 시간 복잡도를 분석합니다. 알고리즘에서는 주어진 문제를 해결하기 위한 연산 횟수를 의미합니다.

 

코딩 테스트에서는 시간 복잡도를 표현할 때 일반적으로 "Big O 표기법"을 사용합니다. Big O 표기법은 최악일 때의 연산 횟수를 기준으로 나타내는 표기법입니다. 

시간 복잡도의 도출 기준

1. 상수는 시간 복잡도에서 제외된다.

2. 가장 많이 '중첩'된 반복문의 횟수가 시간 복잡도의 기준이 된다.

아래 예제를 통해 설명을 풀어보겠습니다.

def once_loops(n):
    # 첫 번째 루프
    for i in range(n):
        print("첫 번째 루프:", i)

def multiple_loops(n):
    # 첫 번째 루프
    for i in range(n):
        print("첫 번째 루프:", i)
    
    # 두 번째 루프
    for j in range(n):
        print("두 번째 루프:", j)
    
    # 세 번째 루프
    for k in range(n):
        print("세 번째 루프:", k)

def find_duplicate(n):
    for i in range(n):         # 외부 반복문
        for j in range(n):     # 내부 반복문
            print("중첩루트 루프:", i, j)

첫번째 함수의 연산 횟수는 n번 입니다. 두번째 함수의 연산 횟수는 3n번 입니다. 하지만 상수는 시간 복잡도에서 제외되기 때문에 두 시간의 복잡도는 같다고 볼 수 있습니다. 

하지만 마지막 세번째는 '중첩'된 반복문을 기준으로 n x n 즉 n의 제곱이 됩니다. 자신의 시간 복잡도를 도출할 수 있어야 코딩 테스트에서 시간 초과가 발생했을 때 원인을 도출하고 더 효율적인 코드를 짤 수 있게 됩니다.

2. 디버깅

디버깅(Debugging)은 프로그램이나 소프트웨어에서 발생하는 오류나 버그를 찾아내고 수정하는 과정을 말합니다. 디버깅은 개발자가 코드를 분석하고 문제를 해결하여 소프트웨어의 정상적인 동작을 복구하는 데 중요한 작업입니다.

 

간단한 디버깅 단계
1. 오류 발견: 프로그램 실행 중에 이상한 동작이나 오류가 발생하면 어떤 부분에서 문제가 발생했는지 파악합니다.
2. 디버깅 도구 사용: 대부분의 개발 환경(IDE)은 디버깅 도구를 제공합니다. 이 도구를 사용하여 코드 실행을 중단하고 변수 값, 함수 호출 등을 확인할 수 있습니다.
3. 중단점 설정: 중단점을 코드에 설정하여 특정 지점에서 프로그램 실행을 일시 중지하고, 그 시점에서 오류를 확인합니다.
4. 변수 확인: 중단된 상태에서 변수의 값이나 상태를 확인하여 오류 원인을 찾아봅니다.
5. 단계별 실행: 코드를 한 줄씩 실행하면서 어떤 부분에서 오류가 발생하는지 확인하고, 함수 호출 스택을 따라갑니다.
6. 오류 수정: 오류를 찾으면 코드를 수정하고, 수정 후에도 다시 테스트하여 문제가 해결되었는지 확인합니다.
7. 테스트와 확인: 오류가 해결되었는지 확인하기 위해 프로그램을 다시 실행하고, 다른 부분에서 새로운 오류가 발생하지 않도록 확인합니다.

책( Do it! 알고리즘 코딩 테스트 - 파이썬 편 )에서는 코딩 테스트에서 실수하기 쉬운 4가지 오류를 아래와 같이 정리했습니다.

1. 변수 초기화 오류 찾아보기

2. 반복문에서 인덱스 지정 오류 찾아보기

3. 잘못된 변수 사용 오류 찾아보기

4. 파이썬 자동 형 변환 조심하기 

 

두가지 이론을 염두해두고 실전 문제 풀이로 들어가겠습니다.
문제는 https://www.acmicpc.net/ 백준 사이트에 로그인하면 함께 참여해서 풀어볼 수 있습니다!