Note 2. 미리 보는 오답 노트

"Do it! 알고리즘 코딩 테스트 파이썬 편 [개정판]"을 기반으로 공부한 내용을 정리한 포스팅입니다 📚

---

1️⃣ 시간 초과 원인 찾기

‼️ 대량의 입출력 데이터를 다룰 때는 input()과 print() 대신 sys.stdin.readline()과 sys.stdout.write() 사용하기

- input() 함수는 입력을 받을 때마다 내부적으로 버퍼(Buffer)를 비우고, 사용자가 입력한 값을 가공(엔터 제거 등)하는 과정을 거칩니다. 반면 sys.stdin.readline()은 버퍼에 쌓인 데이터를 한 번에 읽어오기 때문에 오버헤드가 훨씬 적습니다.

- print() 와 달리 sys.stdout.write()는 자동으로 줄을 바꿔주지 않으며, 오직 문자열만 인자로 받습니다.

# 일반적인 입출력 방식
a = int(input())
print(a)

# 빠른 입출력 방식
import sys
b = int(sys.stdin.readline())
sys.stdout.write(str(b) + '\n')

 

2️⃣ 인덱스에 의미 부여하기

‼️ 파이썬 자료구조인 리스트를 사용할 때 인덱스로 데이터를 접근하는데, 인덱스를 단순히 '몇 번째 순서'로만 생각하지 말고, 문제 상황에 따라 다양한 의미로 변환해보자

Ex) A[1]의 의미
1. 몇 번째 데이터인지 순서를 의미하는 경우 → 첫 번째 데이터를 저장
2. 숫잣값으로 의미를 부여한 경우 → 리스트 A안에 1이라는 값이 몇 개 있는지를 저장

# 인덱스에 숫잣값으로 의미를 부여한 경우
# Q) 1,000보다 작은 자연수 10,000,000개를 1초 안에 정렬하시오

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):
    if count[i] != 0:
        for _ in range(count[i]):
            sys.stdout.write(str(i) + ' ')

 

3️⃣ 나머지 연산의 중요성

‼️ 문제에 '결과값을 00으로 나눈 나머지를 출력하시오' 문구가 있을 경우, 곱셉, 덧셈 등 중간 계산을 할 때마다 나머지 연산을 적용하는 방법 생각하자

❓나머지 연산의 분배 법칙 (나눗셈을 제외한 덧셈, 뺄셈, 곱셈의 분배 법칙 성립)
- (A+B) % C = (A%C + B%C) % C
- (A-B) % C = (A%C - B%C) % C
- (A*B) % C = (A%C * B%C) % C
- (A/B) % C != (A%C) / (B%C) % C

# Q) 1부터 100,000까지 곱한 값을 1,000,000,007로 나눈 나머지를 구하시오

# 기본 (모든 값을 곱한 뒤 마지막에 나머지 연산 수행 버전 = 시간 초과)
import time

answer = 1
start = time.time()

for i in range(1,100001):
 answer *= i
 
result = answer % 1000000007
end = time.time()	# 수행 시간 : 2.8초

# 수정 (곱셉의 나머지 분배법칙을 이용해 곱셉을 수행할 때마다 나머지 연산을 적용)
import time

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

for i in range(1,100001):
 answer = (answer * i) % MOD
 
end = time.time()	# 수행 시간 : 0.008초

 

4️⃣ 정렬 기초

‼️ 이진 탐색과 같은 특정 알고리즘은 정렬된 데이터에만 적용할 수 있고, 그리디 알고리즘과 투 포인터, 우선순위 큐 문제에서도 정렬은 전처리할 때 반드시 등장하므로 기본법을 정확히 익혀보자

❓ 오름차순 정렬
- 데이터를 가장 작은 값부터 시작하여 점차 큰 값으로 나열하는 과정
- list.sort() : 리스트 객체 자체를 정렬하며 반환값은 None
- sorted(list) : 원본을 유지하고 정렬된 복사본을 반환

❓ 내림차순 정렬
- 데이터를 가장 큰 값부터 시작하여 점차 작은 값으로 나열하는 과정
- reverse=True 옵션 사용
- list.sort(reverse=True)
- sorted(list, reverse=True)
- 정렬 함수를 직접 제어할 수 없는 경우 → 부호를 일시적으로 반전 

A = [5,3,7,8,1]

# 부호를 반전시키고 오름차순으로 정렬한 후, 다시 부호 되돌리기
A = [-x for x in A]		# [-5,-3,-7,-8,-1]
A.sort()			# [-8,-7,-5,-3,-1]
A = [-x for x in A]		# [8,7,5,3,1]

 

5️⃣ 다중 조건 정렬

‼️ 만약 성적을 정렬할 때, 먼저 영어 점수를 기준으로 하되, 영어 점수가 같을 경우에는 수학 점수를 기준으로 하고 싶을 때 대표적으로 사용하는 방법들을 알아보자

❓ 튜플 기반 정렬
- 데이터를 (기준1, 기준2, ..) 형태의 튜플로 구성한 뒤, sort() 또는 sorted() 함수의 key 인자에 lambda를 사용해 정렬 기준 지정

❓ 딕셔너리 기반 정렬
- 데이터를 {기준1, 기준2, ..} 형태의 딕셔너리로 구성한 뒤, sort() 또는 sorted() 함수의 key 인자에 lambda를 사용해 정렬 기준 지정

# 튜플 기반 정렬
scores = [
    (80,100),
    (100,50),
    (70,100),
    (80,90)
]
scores.sort(key=lambda x: (-x[0],-x[1]))

# 딕셔너리 기반 정렬
scores = [
	{'english':80, 'math':100},
    	{'english':100, 'math':50},
    	{'english':70, 'math':100},
    	{'english':80, 'math':90},
]
scores.sort(key=lambda x: (-x['math'],-x['english']))

 

6️⃣ 이차원 리스트

‼️ 그래프 관련 알고리즘에 자주 등장하며 특히 인접 리스트 방식으로 그래프를 표현하니 이차원 리스트의 선언과 데이터 저장, 활용 방법을 익혀보자

# 1) 이차원 리스트 선언과 초기화

# 보통 노드 번호는 1부터 시작하므로, 인덱스 0은 사용하지 않고 N+1 크기로 리스트를 초기화

N = 3
graph = [[] for _ in range(N+1)]

# 2) 그래프 데이터 저장

# 보통 코테에서는 입력값이 다음과 같이 주어짐
# 3 4 (노드 3개, 엣지 4개)
# 1 2 4 (1번 노드에서 2번 노드로 가는 가중치 4의 엣지가 있음)
# 2 1 10
# 1 3 7
# 3 2 6

N, E = map(int, input().split())
for _ in range(E):
   s,e,w = map(int,input().split())
   graph[s].append((e,w))
   
# 3) 그래프 데이터 가져오기
for nextNode,weight in graph[1]:
   print(f"next Node {nextNode}, weight = {weight}")

---

‼️ 끝