[Do it! 알고리즘 코딩테스트 파이썬 편] 1주차

[Do it! 알고리즘 코딩테스트 파이썬 편] 의 1주차 동안 학습한 내용을 정리하였습니다!

 

 

 

 

 

1. 코딩테스트의 핵심 : 시간복잡도를 고려한 알고리즘 선택

시간 복잡도란?

: 주어진 문제를 해결하기 위한 연산 횟수!

1초 : 2,000만 번 ~ 1억 번의 연산

(일반적인 파이썬 프로그램 기준!)

• 시간 복잡도를 정의하는 유형 3가지
  • 빅 - 오메가 : ‘최선의 경우’의 연산 횟수
  • 빅 - 세타 : ‘보통의 경우’ 의 연산 횟수 (최선 - 최악의 케이스의 절반)
  • 빅 - 오 : ‘최악의 경우’ 의 연산 횟수

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

코테에서 빅-오 표기법을 사용해야 하는 이유

→ 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 하므로, 판단시 최악의 케이스를 염두에 둬야 한다!

빅 - 오 표기법의 시간 복잡도

• 데이터 크기 (N) 의 증가에 따른 성능(수행 시간)ㅇ

효율 제일 좋음 O(logN)

:	O(N)
:	O(NlogN)
:	O(N^2)
:	O(2^n)
제일 느림	O(N!)

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

• 문제 000: 수 정렬하기
  • 버블 정렬의 시간 복잡도: O(n^2)
  • 병합 정렬의 시간 복잡도: O(nlogn)
    • 시간 제한 2초 (= 1초 2,000만 번 기준, 2초에 4,000만 번 )
    • 40,000,000
  • 입력N개의 줄에 숫자 주어짐 ( |N| ≤ 백 만 번 ) - 수는 중복되지 않음
  • 1번째 줄 부터 ~ N개의 줄에 오름차순 정렬한 결과를 1줄에 1개씩 출력한다
• N 개의 수가 주어졌을 대, 이를 오름차순 정렬하는 프로그램을 작성하시오

 

연산 횟수 계산 방법

연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출함

 

알고리즘 적합성 평가

: 데이터의 크기(N)를 단서로 사용해야하는 알고리즘 추측 가능

• 버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 (약 1조) > 40,000,00 → 부적합 알고리즘!
• 병합 정렬 = $1000000\log_{2}{1000000}$ $\approx$ 200,000,000 < 40,000,00 → 적합! 알고리즘$\log_{2}{10} \approx 3.322$
• [참고!]

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

Step1. 가장 먼저, 코드의 시간 복잡도를 도출한다

→ 그러려면 시간복잡도 도출 기준을 알아야 함!

도출 기준 고려해야한다!

1. 상수는 시간 복잡도 계산에서 제외한다코드에 반복문이 3개가 각각 있어서 연산 횟수가 3N이 되더라도,
2. 상수를 무시하고 둘 다 시간 복잡도는 O(n) 으로 같음!
3. → 반복문 하나의 연산 횟수는 N번
4. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다이중 for문 1개로 인한 N^2 이다!
5. → 일반 for문이 10개, 이중 for 문이 1개 있다고 하면, 여기에서의 시간 복잡도는

Step2. 연산이 가장 큰 부분을 찾아서 연산에 더욱 효율적인 구조로 수정!

---

2. 코드의 논리오류 잡는 법: 디버깅

2-1. 디버깅이 중요한 이유

디버깅이란

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

문법 오류는 컴파일러가 자동으로 찾아줌, 주로 논리 오류를 찾기 위함이다!

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

방법

1. 코드에서 디버깅하고자 하는 줄에 중단점(breakpoint)을 설정한다
2. IDE의 디버깅 기능을 실행하면, 코드를 1줄씩 실행하거나 , 다음 중단점까지 실행 가능!
3. (이 과정에서 추적할 변숫값도 지정 가능!), 변수의 값 변화 따라가면서 파악하기
4. 변수값 이외에도 원하는 수식을 입력해 논리 오류 파악 가능!

2-2. 디버깅 활용 사례 살피기

오류 점검방안

1. 변수 초기화 오류를 범하지 않았는지 체크

→ 모든 변수가 정상적으로 초기화 되고 있는지, 디버깅을 이용해 확인해보기

2. 반복문 인덱스 범위 넘어가지 않았는지 체크

→ 반복문에서 반복 범위를 잘못 지정하거나,

비교 연산자를 잘못 사용하는 경우

배열 인덱스가 0부터 시작하는 사실을 간과하거나,

반복문을 N까지 반복하도록 설정해야 하는데, 비교 연산자를 잘못 입력하여 N-1 까지 반복하도록 설정하는 때도 있다

 

반복문을 사용할 때 마다, 범위와 시작 인덱스를 꼼꼼하게 확인하고,

혹시 모를 입력 실수를 대비해 디버깅하는 습관을 들일 것!

 

3. 잘못된 변수 사용 체크

4. 파이썬 자동 형 변환 체크

파이썬에서의 나누기는 / 연산자와, // 연산자 두 가지 이다!

• / 연산: 나눗셈의 결과값을 float 형으로 출력 → 소수점의 결과까지 보여준다!
• // 연산: 나눗셈을 한 결괏값을 int 형으로 출력 → 몫의 결과만 보여준다!
• % 연산: 나눗셈을 한 후 나눈 나머지 값을 보여준다! 

 

 

 

 

 

 

 

• Chapter 2 목표: 다양한 알고리즘에 관련된 핵심 이론과, 이를 바탕으로 실전 문제를 해결하는 방법 알아보기

미리 보는 코딩 테스트 오답 노트

• 목표: 문제 풀이에서 자주 실수하는 유형, 팁 으로 미리 익혀두기!

1. 시간 초과의 원인을 찾아 해결하기

해결 방법 1. 풀이 로직의 시간 복잡도 허용 범위 다시 점검하기

문제 풀이를 설계 할 때,

해당 방식이 시간 복잡도를 고려하여 제한 시간 범위 내에 들어가는지를 먼저 체크하고 들어가야함!

→ 시간 복잡도가 너무 높다면 풀이 알고리즘 자체를 수정해야할 필요가 있다

해결 방법 2. 입/출력 최적화!

• 입출력 최적화 방법:sys.stdin.readline() 과 sys.stdout.write()를 활용하면 처리 속도를 크게 향상시킬 수 있다!
• input() , print() 대신,
• 이걸 쓰면 얼만큼 시간을 단축시킬 수 있는지?
  • 1,000,000개의 정수 입출력 시간 차이 비교 표방식 입력 속도(초) 출력 속도(초) 총 소요 시간(초)

    input()과 print()	1.8	1.2	3
    sys.stdin.readline()과 sys.stdout.write()	0.3	0.3	0.6

  • → 총 소요시간에서 큰 차이가 생긴다! (실제 환경에 따라 달라질 순 있음)
• 각각의 작동 원리 차이[비교]
  • input() 은 호출될 때 마다 한 줄을 읽어 → 끝의 개행 문자를 제거한 문자열을 반환
  • (숫자 변환 등 추가 파싱은 직접 처리해야함!)
  • print()는 기본적으로 출력 내용을 버퍼에 모았다가 상황에 따라 비운다
  • → 반복 호출이 많으면 작은 단위의 잦은 쓰기로 인해 성능이 저하될 수 있음!
• 입출력 데이터의 양이 많아지면, 큰 성능 차이가 발생할 수 있기 때문에!

 

• sys.stdin.readline() 은 입력 버퍼에서 한 줄 전체를 그대로 읽음
• → 대량 입력에서 더 빠른 성능을 낼 수 있다!
• sys.stdout.write() : 개행 문자를 자동으로 붙이지 않음!(문자열만 출력할 수 있으므로, 정수는 str() 로 변환하여 출력!)
• → 여러 출력을 모아 한 번에 출력하면 큰 속도향상 가능!

 

2. 인덱스에 의미 부여하여 풀어 보기

인덱스의 역할

1. 몇 번째 데이터인지 나타내는 역할
2. 인덱스를 순서가 아니라, 해당 숫잣값 자체에 의미를 부여하여 사용하는 방식!
3. → 해싱 개념을 적용하자!

인덱스에 해싱 개념 적용

• 적용 예시A[1] : A라는 배열의 1번 인덱스의 값을 나타낼 수도 있지만,1이라는 값이 몇 개 있는지를 저장한다고도 사용가능
  • A[1] = 2, 1이라는 값이 2개 있다는 뜻으로 사용 가능0 1 2 3 4 

    5

    2

    1

    6

    9

• 인덱스를 순서가 아니라, 해당 숫잣값 자체에 의미를 부여하는 상황을 가장 자주 사용한다
• → 숫자값으로 의미를 부여한 경우,
• 언제 적용하면 좋은가?→ 1초 안에 정렬이 어렵다
• 인덱스를 값 자체로 활용하면, 계수 정렬과 같은 방식으로 제한 시간 내에 정렬할 수 있다!
• 예) 1000보다 작은 자연수 10,000,000개를 1초 안에 정렬해야 하는 상황,
• 인덱스에 의미를 부여한 대표 사례 - [계수 정렬]→ 여기서 count 리스트의값은 해당 숫자의 등장 횟수!
• 인덱스는 숫자 자체
• import sys N = int(sys.stdin.readline()) count = [0]* 1001 numbers = list(map(int, sys.stdin.readline().split())) for number in numbers: **count[number] += 1 #인덱스에 숫자값으로 의미를 부여하여 데이터를 저장!** for i in range(1001): #0~1000 중에 if count[i] != 0: #i값이 0개인 수면 for _ in range(count[i]): #0부터 count[i]의 개수-1까지 sys.stdout.write(str(i)+ ' ')

비교 연산을 따로 하지 않아도 10,000,000개의 숫자를 1초 안에 빠르게 정렬할 수 있다!

 

실제 코테 상황에서는, 요구 사항에 따라 인덱스에 적절한 의미를 직접 부여해야 하는 문제도 자주 출제되므로,

⇒ 인덱스를 단순히 ‘몇 번째 순서’ 로만 생각하지 말고

문제 상황에 따라 다양한 의미로 변환해 보는 연습이 중요하다!!

 

3. 나머지 연산의 중요성 알아보기

• 나머지 연산이 왜 중요한가?

정답을 OO으로 나눈 나머지를 출력해라 → 나머지 연산을 언제 하느냐가 속도 차이를 만든다!

• 분배 법칙 활용의 중요성!분배 법칙을 통해 값을 중간중간씩 연산하는 것이 연산 속도를 줄인다!
• 또한 매우 큰 값을 한 번에 연산하기 보다,

나머지 연산이 자주 활용되는 분배 법칙

• 주의! 나눗셈은 분배 법칙이 성립하지 않는다

1. 덧셈의 분배 법칙 : (A+B) % C = (A%C + B%C)%C
2. 뺄셈의 분배 법칙 : (A-B) % C = (A%C - B%C)%C
3. 곱셈의 분배 법칙 : (A*B)%C = (A%C * B%C) %C

→ 나눗셈은 나머지 연산의 분배 법칙이 성립하지 않는다. 나머지(덧셈, 뺄셈, 곱셈은 성립)

큰 값을 한 번에 나머지 연산 하면 시간 초과의 위험이 있다! → 분배 법칙을 잘 활용하자

파이썬에서는 int형이 자동으로 확장되므로, 정수 오버플로는 발생하지 않는다.

하지만 숫자가 매우 커지면, 계산 속도가 급격히 느려지고, 시간 초과에 걸릴 수 있다!

마지막에만 %연산을 적용해도 정답 계산이 가능하지만,

채점 서버에서는 시간 초과로 처리되어 오답이 될 수 있다!

• 활용 예시 : [1부터 100,000까지 곱한 값을 1,000,000,007로 나눈 나머지를 구하시오]

import time

MOD = 1000000007
answer = 1
start = time.time()

"""
for i in range(1,100001):
	answer *= i 

result = answer % 1000000007 #곱한 결과를 한 번에 나머지 연산 하기보다는,
"""
**for i in range(1,100001):
	answer = (answer *i)%MOD**
# 반복문 한 숫자 마다 곱셉, 나머지 연산을 하는 것이 훨씬 속도 향상된다

즉, 정답을 OO으로 나눈 나머지를 출력해라 에서 정답을 구한 후 마지막에 나머지 연산을 구하는 경우 , 시간 초과의 위험이 있다!

⇒ 분배 법칙을 통해, 곱셈, 덧셈 등 중간 계산을 할 때 마다 나머지 연산을 적용하는 습관이 필수이다!

4. 정렬 기초 다지기

• 정렬 기초를 다져야 하는 이유?
  1. 이진 탐색 과 같은 특정 알고리즘은 정렬된 데이터에만 적용될 수 있기 때문!
  2. 또한, 정렬은 그리디 알고리즘, 투 포인터, 우선순위 큐 문제에서도 전처리 시 반드시 해야함!

오름차순 정렬 : 작은 값 to 큰 값

데이터의 원본이 유지되어야 하는지의 여부에 따라 다른 방식 사용!

• 방식1: 파이썬 .sort() 이용한 정렬!

  #원본 리스트 선언
  A = [5,3,2,4,1]
  
  # 방식1 : list.sort() : 리스트 자체를 정렬 (in-place)
  A.sort()
  

• = 리스트(원본) 자체를 정렬! (in-place 정렬) : 반환값 None
• 방식2 : 파이썬 sorted() 이용한 정렬!

  #원본 리스트 선언
  A = [5,3,2,4,1]
  
  # 방식2 : sorted(list) : 리스트의 정렬된 복사본을 반환 (원본은 유지)
  B = sorted(A)
  

• = 정렬된 복사본을 반환!

내림차순 정렬 : 큰 값 to 작은 값

reverse=True 옵션 추가해서 내림차순 정렬 구현!

#원본 리스트 선언
A = [5,3,2,4,1]

# 방식1에 내림차순 옵션 추가
A.sort**(reverse=True)**
print("내림차순 결과:",A)

# 정렬된 복사본 반환(원본 유지)
B = sorted**(A, reverse=True)**
print("내림차순 복사본:",B)

추가) 정렬 함수를 직접 제어할 수 없는 경우 : 부호를 일시적으로 반전!

#원본 리스트 선언
A = [5,3,2,4,1]

**#부호를 반전시키고, 오름차순으로 정렬한 후, 다시 부호 되돌리기!**
A = [-x for x in A] #부호 반전 : [-5,-3,-2,-4,-1]
A.sort() # 이때의 A는 [-5,-4,-3,-2,-1]

A = [-x for x in A] # 부호 반전 : [5,4,3,2,1] -> 내림차순!이 됨

5. 다중 조건 정렬 익히기

• 다중 조건 정렬이란? : 여러개의 조건에 따라 정렬하는 것
• 대표적으로 튜플 기반 정렬과, 딕셔너리 기반 정렬이 있다

튜플 기반 정렬

• 튜플 기반 방식 : 데이터를 튜플로 구성 후→ .sort() 나 sorted() 의 key인자에 lambda를 사용해 정렬 기준을 지정
• 튜플 형태로 하는 이유?
• 정렬 기준을 튜플로 묶으면, 앞에 있는 조건부터 차례로 여러 조건을 적용할 수 있음!
• 예시 - 영어 점수 내림차순 정렬, 동점인게 있으면 수학점수 내림차수도 고려하는 정렬
  • socres.sort(key=lambda x: (-x[0], -x[1]))
    • key=lambda x:튜플의 각 요소를 x 라고 부르고,
    • 그 x를 어떻게 변형한 값을 기준으로 정렬할지 정해준다!
    • → 정렬 기준을 커스텀(사용자 정의) 하겠다는 의미!
    • (-x[0], -x[1])-x[0] : 첫 번째 요소에 마이너스 붙여서 정렬<aside>
      • 영어는 내림차순(높은 순) → 수학은 오름차순(낮은 순) 으로 정렬하고 싶다면?
      • scores.sort(key=lambda x: (-x[0], x[1]))
      </aside>
    • -x[1] : 두 번째 요소에 마이너스 붙여서 정렬!
    • 기본 정렬은 오름차순인데, 마이너스를 붙여서 순서를 뒤집음!
• # 영어, 수학 순서로 튜플 데이터 저장 scores = [ (80,100), (100,50), (70,100), (80,90), ] #1순위: 영어 내림차순 -> 동점인게 있으면 2순위: 수학 내림차순 **scores.sort(key=lambda x: (-x[0],-x[1]))** for s in scores: print(f"english={s[0]}, math={s[1]}")
• 추가) 람다 함수 lambda 이해하기! : 람다 함수는 정렬시 참고하기 위한 기준만 보기 위함임!sort(key=...) 함수에서 key에 전달하는 람다 함수는정렬할 때만 참고하는 '임시 기준값'을 만드는 역할을 합니다.
  1. 기준표 작성: 파이썬이 정렬하기 전에 각 요소 옆에 포스트잇을 하나씩 붙인다고 상상해 보세요.
     • (80, 100) 옆에는 (-80, -100)이라는 포스트잇을 붙입니다.
     • (100, 50) 옆에는 (-100, -50)이라는 포스트잇을 붙입니다.
  2. 순서 정하기: 파이썬은 실제 데이터가 아니라, 이 포스트잇에 적힌 숫자들을 비교해서 오름차순으로 순서를 정합니다.
     • 100이 80보다 작으므로, 100 포스트잇이 붙은 데이터가 가장 앞으로 갑니다.
  3. 결과 출력: 순서가 다 정해지면 포스트잇은 떼어버리고, 원래 있던 실제 데이터(100, 50 등)만 남겨서 리스트를 재배치합니다.

  ---

  파이썬 내부에서 sort가 돌아갈 때의 논리 구조는 다음과 같습니다:결국 lambda 함수는 "어떤 기준으로 줄 세울까?"라는 질문에 답하기 위해 잠깐 계산해 보는 식일 뿐, 원본 데이터를 수정(Modify)하는 명령이 아닙니다!
• </aside>
• # 내부적인 가상의 동작 과정 temp_keys = [] for x in scores: temp_keys.append((-x[0], -x[1])) # 정렬을 위한 "임시 키" 생성 # 이 temp_keys를 기준으로 전체 데이터의 순서를 결정 (실제 데이터는 변하지 않음) # 순서 결정 완료 후 리스트 재배치`
• 작동 원리를 비유로 설명하면 이렇습니다:
• 실제 리스트의 값을 바꾸는 것이 아니라,
• <aside>

딕셔너리 기반 정렬

• 딕셔너리 기반 방식 : 데이터를 딕셔너리로 구성 후→ .sort() 나 sorted() 의 key인자에 lambda를 사용해 정렬 기준을 지정
• 딕셔너리 형태로 하는 이유?
• 정렬 기준을 딕셔너리 형태로 묶으면, 키(key)의 이름으로 값을 찾기 때문에, 데이터에 새로운 항목이 추가되거나 순서가 바뀌어도 정렬 코드를 고칠 필요가 없다!
• 예시 - 수학 점수 내림차순 정렬, 동점인게 있으면 영어 점수 내림차수도 고려하는 정렬
  • socres.sort(key=lambda x: (-x[0], -x[1]))
    • key=lambda x:튜플의 각 요소를 x 라고 부르고,
    • 그 x를 어떻게 변형한 값을 기준으로 정렬할지 정해준다!
    • → 정렬 기준을 커스텀(사용자 정의) 하겠다는 의미!
    • (-x[0], -x[1])-x[0] : 첫 번째 요소에 마이너스 붙여서 정렬<aside>
      • 영어는 내림차순(높은 순) → 수학은 오름차순(낮은 순) 으로 정렬하고 싶다면?
      • scores.sort(key=lambda x: (-x[0], x[1]))
      </aside>
    • -x[1] : 두 번째 요소에 마이너스 붙여서 정렬!
    • 기본 정렬은 오름차순인데, 마이너스를 붙여서 순서를 뒤집음!
• # 영어, 수학 순서로 튜플 데이터 저장 scores = [ {'english':80, 'math':100 }, {'english':100 , 'math': 50}, {'english':70, 'math': 100}, {'english':80, 'math': 90}, ] #1순위: 영어 내림차순 -> 동점인게 있으면 2순위: 수학 내림차순 **scores.sort(key=lambda x: (-x['math'],-x['english']))** for s in scores: print(s)

두 정렬 방식의 차이

• 어떤 상황에 활용하는가?짧고 간단해서 더 빠르다딕서너리 기반 정렬: 데이터에 새로운 항목이 추가되거나 순서가 바뀌어도 정렬 코드를 고칠 필요가 없다!
• 구조화되어 가독성이 좋다
• → 조건이 많아지면, 딕셔너리로 해야 가독성이 더 좋음!
• 튜플 기반 정렬: 적은 조건일 때!, (단순 계산용), 단순 입력처리 일 때!

6. 이차원 리스트 제대로 다루기

• 이차원 리스트는 어디에 사용하는가? : 그래프의 구조 표현특히 인접 리스트 방식으로 그래프를 표현할 때,
• 이차원 리스트의 선언,데이터 저장, 활용 방법을 정확히 이해하고 있어야 시험장에서 당황하지 않고 문제를 풀 수 있다!
• → 코테 문제에서는 그래프 관련 알고리즘이 많이 등장하는데, 이 때 그래프의 구조를 표현하는데 많이 사용하는 것이 이차원 리스트이다!

이차원 리스트를 이용한 그래프 구현 방법

[Step 1. 이차원 리스트 선언과 초기화]

파이썬 리스트 안에 또 다른 리스트를 넣는 방식으로 이차원 리스트를 구성한다!

• 보통 노드 번호는 1번부터 시작 하므로, 인덱스 0 사용x, N+1 크기로 리스트 초기화 한다
• # 정점이 3개 있다고 가정 (1~3번 사용!) N =3 **graph = [[] for _ in range(N+1)]**

→ 이렇게 만든 graph[1], graph[2], graph[3] 각각이 각 정점의 인접 리스트 역할을 한다!

[Step 2. 그래프 데이터 저장하기]

• 문제 예시) 아래의 간단한 그래프에 입력값 저장하기<aside>
  • 왼쪽 그래프를 표현하기 위한 입력값
  3 4 (→ 노드가 3개, 에지가 4개인 그래프)2 1 103 2 6
  • 그래프 데이터를 이차원 리스트 자료구조를 이용하여 저장하기

    # 정점 수와 간선 수 입력
    N,E = map(int, input().split()) #정점=3, E 간선(edge)=4
    
    # 간선 정보를 입력받아 저장
    for _ in range(E): #저장할 에지의 개수만큼 반복 (1~4까지)
    	s,e,w = map(int,input().split())
    	**graph[s].append((e,w)) #이차원 리스트에 그래프 데이터 저장!	
    			# (e,w) 는 (도착 노드, 가중치) 임!**
    

  • 연결 정보는 (도착 노드, 가중치) 형태의 튜플로 저장한다
  • 실제 이차원 리스트에 데이터 저장 형태[1] → [2,4] [3,7][3] → [2,6]
  • [2] → [1,10]
  • [시작노드] → [도착노드, 가중치] 형태!
• </aside>
• 1 3 7
• 1 2 4 ( 1번 노드에서 2번 노드로 가는 가중치 4의 에지가 있음 )
• flowchart LR 1 -- 7 --> 3 3 -- 6 --> 2 1 -- 4 --> 2 2 -- 10 --> 1

[Step 3. 그래프 데이터 가져오기]

• 1번 노드에서 시작되는 에지 데이터를 가져오기!이 코드를 사용하면
• [2,4] 랑 [3,7] 의 2개의 에지 데이터를 가져올 수 있다
• for nextNode, weight in graph[1]: print(f"next Node {nextNode}, weight= {weight}")

→ 그래프 문제에서 이차원 리스트가 필요할 때 적절하게 활용하여 문제를 해결하자!