[동빈나] 이코테 - 1. 코딩 테스트 출제 경향 분석 및 파이썬 문법 부수기

IT 교육 유튜브 채널 [동빈나](www.youtube.com/c/dongbinna/playlists)의

"이것이 취업을 위한 코딩 테스트다" 강의를 듣고 학습한 내용을 정리하는 글입니다.
중요한 내용 혹은 몰랐던 내용 위주로만 정리한 것이며,
코드 블럭 내 (>>>)는 실행결과를 표현하기 위한 것이니 이 점 참고해주시면 되겠습니다.

---

복잡도(Complexity)

• 복잡도는 알고리즘의 성능을 나타내는 척도

  • 시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
  • 공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

• 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘.

빅오 표기법(Big-O Notation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
• 예) 연산 횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘
  • 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3)으로 표현됨 (계수 무시)

알고리즘 설계 Tip

• 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우
  • Python을 기준으로 5 ~ 15초 가량의 시간이 소요됨
• 코딩 테스트 문제에서 시간 제한은 통상 1 ~ 5초가량. 문제에 명시되어 있지 않은 경우 대략 5초 정도.

요구사항에 따라 적절한 알고리즘 설계하기

• 문제에서 시간제한(수행시간 요구사항) 가장 먼저 확인
• 시간제한 1초인 문제의 경우, 일반적 기준
  • N의 범위 500인 경우: O(N^3)
  • N의 범위 2,000인 경우: O(N^2)
  • N의 범위 100,000인 경우: O(NlogN)
  • N의 범위 10,000,000인 경우: O(N) 

import time
start_time = time.time() # 측정 시작

# 프로그램 소스코드
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) # 수행 시간 출력

실수형

# 소수부가 0일 때 0을 생략
a = 5.
print(a)
>>> 5.0
# 정수부가 0일 때 0을 생략
b = -.7
print(b)
>>> -0.7

지수 표현 방식

• e나 E 다음에 오는 수는 10의 지수부를 의미
• Ex) 1e9 = 10의 9제곱(1,000,000,000)
• 유효숫자e^지수 = 유효숫자x10^지수
• 임의의 큰 수 표현을 위해 자주 사용
• 최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단 거리를 무한(INF)로 설정하곤 함.
• 이때 가능한 최댓값이 10억 미만이라면 무한(INF)의 값으로 1e9 이용할 수 있음

a = 1e9
print(a)
>>> 1,000,000,000.0

b = 75.25e1
print(b)
>>> 752.5

c = 3954e-3
print(c)
>>> 3.954

실수형

• IEEE754 표준에서는 실수형을 저장하기 위해 4바이트 혹은 8바이트의 고정된 크기의 메모리를 할당하므로, 컴퓨터 시스템은 실수 정보를 표현하는 정확도에 한계를 가짐
• 10진수 체계에서는 0.3 + 0.6 = 0.9로 정확히 떨어지지만, 2진수에서는 0.9를 정확히 표현할 수 없음.
• 컴퓨터는 최대한 0.9와 가깝게 표현하지만 미세한 오차가 발생

a = 0.3 + 0.6
print(a)
>>> 0.899999...

• 개발 과정에서 실수 값을 제대로 비교하지 못해서 원하는 결과를 얻지 못할 수 있음
• 이럴 때는 round() 함수 사용이 권장
• 123.456을 소수 셋째 자리에서 반올림하려면 round(123.456, 2)라고 작성 -> 결과는 123.46

a = 0.3 + 0.6
print(round(a, 4))

if round(a, 4) == 0.9:
    print(True)
else:
    print(False)

>>> 0.9
>>> True

리스트 컴프리헨션

• 리스트 초기화하는 방법 중 하나
  • 대괄호 안에 조건문, 반복문을 적용하여 리스트 초기화

# 0부터 9까지 수를 포함하는 리스트
array = [i for i in range(10)]

print(array)
>>> [0,1,2,3,4,5,6,7,8,9]

# 0부터 9까지 수 중에서 홀수만 포함하는 리스트
array = [i for i in range(10) if i % 2 == 1]

# 1부터 9까지의 수들의 제곱 값을 포함하는 리스트
array = [i*i for i in range(1, 10)]

• 2차원 리스트 초기화할 때 효과적
• N X M 크기 2차원 리스트 한번에 초기화 해야 할 때
  • 좋은 예시: array = [[0] * m for _ in range(n)]
  • 잘못된 예시: array = [[0] * m ] * n
  • 위 코드는 전체 리스트 안에 포함된 각 리스트가 모든 같은 객체로 인식됨.

# N X M 크기의 2차원 리스트 초기화(잘못된 방법)
n = 4
m = 3
array = [[0] * m ] * n
print(array)
>>> [[0,0,0],[0,0,0],[0,0,0],[0,0,0]]

array[1][1] = 5
print(array)
>>> [[0,5,0],[0,5,0],[0,5,0],[0,5,0]]

언더바

• 파이썬에서는 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_) 자주 사용

for _ in range(5):
  print('Hello World')

리스트 관련 기타 메서드

a = [1, 4, 3]

# 리스트에 원소 삽입
a.append(2)
print(a)
>>> [1, 4, 3, 2]

# 오름차순 정렬
a.sort()
print(a)
>>> [1, 2, 3, 4]

# 내림차순 정렬
a.sort(reverse = True)
print(a)
>>> [4, 3, 2, 1]

# 리스트 원소 뒤집기
a.reverse()
print(a)
>>> [1, 2, 3, 4]

# 특정 인덱스에 데이터 추가
a.insert(2, 3)
print(a)
>>> [1, 2, 3, 3, 4]

# 특정 값인 데이터 개수 세기
print(a.count(3))
>>> 2

# 특정 값 데이터 삭제
a.remove(1)
print(a)
>>> [2, 3, 3, 4]

리스트에서 특정 값을 가지는 원소를 모두 제거하기

a = [1, 2, 3, 4, 5, 5, 5]
remove_set = {3, 5}

# remove_set에 포함되지 않은 값만을 저장
result = [i for i in a if i not in remove_set]
print(result)

튜플 자료형(tuple)

• 튜플은 한 번 선언된 값을 변경할 수 없음
• 리스트는 []를 이용, 튜플은 ()을 이용
• 튜플은 리스트에 비해 상대적으로 공간 효율적(더 적은 양의 메모리 사용)
• 튜플을 사용하면 좋은 경우
  • 서로 다른 성질의 데이터를 묶어서 관리해야 할 때
    • 최단 경로 알고리즘에서는 (비용, 노드 번호)의 형태로 튜플 자료형 자주 사용
  • 데이터의 나열을 해싱(Hashing)의 키 값으로 사용해야 할 때
    • 튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용가능
  • 리스트보다 메모리 효율적으로 사용해야 할 때

사전 자료형(dictionary)

• 키(Key)와 값(Value)의 쌍을 데이터로 가짐
• 원하는 '변경 불가능한(Immutable) 자료형'을 키로 사용가능
• 파이썬의 사전 자료형은 해시 테이블(Hash Table)을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리 가능

data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'

print(data)

if '사과' in data:
  print("'사과'를 키로 가지는 데이터가 존재")

>>> {'사과': 'Apple', '바나나':'Banana', '코코넛':'Coconut'}
'사과'를 키로 가지는 데이터가 존재

• 키 데이터만 뽑아서 리스트로 이용할 때 keys() 함수
• 값 데이터만 뽑아서 리스트로 이용할 때 values() 함수

# 키 데이터만 담은 리스트
key_list = data.keys()
# 값 데이터만 담은 리스트
value_list = data.values()
print(key_list)
print(value_list)

# 각 키에 따른 값을 하나씩 출력
for key in key_list:
  print(data[key])

집합 자료형(set)

• 중복 허용 하지 않음
• 순서 없음
• 집합은 리스트 혹은 문자열을 이용해서 초기화할 수 있음
  • 이때 set() 함수 이용
• 혹은 중괄호 ({}) 안에 각 원소를 콤마(,)를 기준으로 구분하여 삽입함으로써 초기화할 수 있음.
• 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리 가능

# 집합 자료형 초기화 방법 1
data = set([1, 1, 2, 3, 4, 4, 5])
print(data)
>>> {1, 2, 3, 4, 5}

# 집합 자료형 초기화 방법 2
data = {1, 1, 2, 3, 4, 4, 5}
print(data)
>>> {1, 2, 3, 4, 5}

집합 자료형의 연산

• 합집합, 교집합, 차집합

a = set([1, 2, 3, 4, 5])
b = set([3, 4, 5, 6, 7])

print(a | b) # 합집합
print(a & b) # 교집합
print(a - b) # 차집합

>>> {1, 2, 3, 4, 5, 6, 7}
{3, 4, 5}
{1, 2}

집합 자료형 관련 함수

data = set([1, 2, 3])

# 새로운 원소 추가
data.add(4)
print(data)
>>> {1, 2, 3, 4}

# 새로운 원소 여러 개 추가
data.update([5, 6])
print(data)
>>> {1, 2, 3, 4, 5, 6}

# 특정한 값을 갖는 원소 삭제
data.remove(3)
print(data)
>>> {1, 2, 4, 5, 6}

사전 자료형과 집합 자료형의 특징

• 리스트 / 튜플은 순서가 있기 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있음
• 사전 자료형과 집합 자료형은 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없음
  • 사전의 키(key) 혹은 집합의 원소(element)를 이용해 O(1)의 시간 복잡도로 조회

기본 입출력

자주 사용되는 표준 입력 방법

• map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용
  • 예시) 공백을 기준으로 구분된 데이터 입력 받을 때
    • list(map(int, input().split()))

빠르게 입력 받기

• 사용자로부터 입력을 최대한 빠르게 받아야 하는 경우
• 파이썬의 경우 sys 라이브러리에 정의되어 있는 sys.stdin.readline() 메서드를 이용한다.
  • 단, 입력 후 엔터(Enter)가 줄 바꿈 기호로 입력되므로 rstrip() 메서드를 함께 사용한다.

import sys

# 문자열 입력 받기
data = sys.stdin.readline().rstrip()
print(data)

자주 사용되는 표준 출력 방법

• print() 줄 바꿈을 원치 않는 경우 'end' 속성 이용할 수 있음.

f-string 예제

• 파이썬 3.6부터 사용 가능, 문자열 앞에 접두사 'f'를 붙여 사용
• 중괄호 안에 변수명을 기입하여 간단히 문자열과 정수를 함께 넣을 수 있음

answer = 7

print(f"정답은 {answer}입니다.")
>>> 정답은 7입니다.

조건문 간소화

• 조건부 표현식(Conditional Expression)은 if ~ else문을 한 줄에 작성할 수 있도록 해줌

score = 85
result = "Success" if score >= 80 else "Fail"

print(result)
>>> Success

함수

• 내장 함수 : 파이썬이 기본적으로 제공하는 함수
• 사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수

파라미터 지정하기

• 파라미터의 변수를 직접 지정할 수 있음
  • 이 경우 매개변수의 순서가 달라도 상관없음

def add(a, b):
  print('함수의 결과:', a + b)

add(b = 7, a = 3)
>>> 함수의 결과: 10

global 키워드

• global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조하게 됨.

a = 0

def func():
  global a
  a += 1

for i in range(10):
  func()

print(a)

array = [1, 2, 3, 4, 5]

def func():
  array = [3, 4, 5]
  array.append(6)
  print(array) # 함수 내의 지역변수를 참조

func()
print(array) # 전역변수를 참조

>>> [3, 4, 5, 6]
[1, 2, 3, 4, 5]

람다 표현식

• 특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있음

print((lambda a, b: a + b)(3, 7))

>>> 10

array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]

def my_key(x):
  return x[1]

print(sorted(array, key = my_key))
print(sorted(array, key = lambda x: x[1]))

>>> [('이순신', 32), ('홍길동', 50), ('아무개', 74)]
[('이순신', 32), ('홍길동', 50), ('아무개', 74)]

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

result = map(lambda a, b: a + b, list1, list2)

print(list(result))

실전에서 유용한 표준 라이브러리

• 내장 함수: 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공
• itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공
  • 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용
• heaps: 힙(Heap) 자료구조 제공
  • 일반적으로 우선순위 큐 기능을 구현하기 위해 사용
• bisect: 이진 탐색(Binary Search) 기능을 제공
• collections: 덱(deque), 카운터(Counter) 등의 유용한 자료구조 포함
• math: 필수적인 수학적 기능 제공
  • 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 함수부터 파이(pi)와 같은 상수 포함

자주 사용되는 내장 함수

# eval()
result = eval("(3+5)*7")
print(result)
>>> 56

# sorted() with key
array = [('홍길동', 35), ('이순신', 75), ('아무개', 50)]
result = sorted(array, key = lambda x: x[1], reverse = True)
print(result)
>>> [('이순신', 75), ('아무개', 50), ('홍길동', 35)]

순열과 조합

• 모든 경우의 수를 고려해야 할 때 어떤 라이브러리를 효과적으로 사용할 수 있을까?

• 순열: 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열

  • {'A', 'B', 'C'}에서 세 개를 선택하여 나열하는 경우: 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'

• 조합: 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택

  • {'A', 'B', 'C'}에서 순서를 고려하지 않고 두 개를 뽑는 경우: 'AB', 'AC', 'BC'

• 순열의 수: nPr = n * (n-1) * ... * (n-r+1)

• 조합의 수: nCr = n * (n-1) * ... * (n-r+1) / r!

# 순열
from itertools import permutations

data = ['A', 'B', 'C'] # 데이터 준비

result = list(permutations(data, 3)) # 모든 순열 구하기
print(result)

>>> [('A','B','C'), ('A','C','B'), ... ]


# 조합
from itertools import combinations

data = ['A', 'B', 'C']

result = list(combinations(data, 2)) # 2개를 뽑는 모든 조합 구하기
print(result)

>>> [('A','B'), ('A','C'), ('B','C')]


# 중복 순열
from itertools import product

data = ['A', 'B', 'C'] # 데이터 준비

result = list(product(data, repeat = 2)) # 2개를 뽑는 모든 순열 구하기 (중복 허용)
print(result)


# 중복 조합
from itertools import combinations_with_replacement

data = ['A', 'B', 'C'] # 데이터 준비

result = list(combinations_with_replacement(data, 2)) # 2개를 뽑는 모든 조합 구하기 (중복 허용)
print(result)

Counter

• 파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공
• 리스트와 같은 반복 가능한(iterable) 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 알려줌.

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])

print(counter['blue']) # 'blue'가 등장한 횟수 출력
print(counter['green']) # 'green'이 등장한 횟수 출력
print(dict(counter)) # 사전 자료형으로 변환

>>> 3
1
{'red': 2, 'blue': 3, 'green': 1}

최대 공약수와 최소 공배수

• math 라이브러리의 gcd() 함수를 이용

import math

# 최소 공배수(LCM)를 구하는 함수
def lcm(a, b):
  return a * b // math.gcd(a, b)

a = 21
b = 14

print(math.gcd(12, 14)) # 최대 공약수(GCD) 계산
print(lcd(12, 14)) # 최소 공배수(LCM) 계산

>>> 7
42