동빈나 알고리즘 정리

송병훈·2022년 8월 10일
알고리즘코테

언어

Python, C++, Java

유형

  1. 그리디, 구현, DFS/BFS를 이용한 탐색
  2. 최단경로, 다이나믹프로그래밍, 정렬
  3. 그래프 이론, 이진 탐색

복잡도

낮을수록 좋음
빅오표기법 - 가장 영향이 큰 항만 고려한다

(좋음)	O(1)	O(logN)	O(N)	O(NlogN)	O(N²)	O(N³)	O(2ⁿ)	(나쁨)
		상수		로그		선형		로그선형		이차		삼차		지수

Tip

  • 코테에서 파이썬이 1초에 2천만번의 연산만 처리할 수 있다고 가정하고 접근하는 것이 좋다.
  • 문제에 시간제한이 없으면 5초라고 생각해라.
  • 시간제한이 1초인 문제를 만났을 때 일반적인 기준
	N < 500		: O(N³)
	N < 2,000	: O(N²)
	N < 100,000	: O(NlogN)
	N < 10,000,000	: O(N)

인 알고리즘을 설계하면 문제를 풀 수 있다

문제해결과정

  1. 지문 읽기 및 컴퓨터적 사고 (문제를 잘게 나누기)
  2. 요구사항(복잡도) 분석
  3. 문제해결을 위한 아이디어 찾기
  4. 소스코드 설계 및 코딩

수행 시간 측정 코드

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

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

실수값 보정

반올림 함수인 round() 이용
round(123.456, 2) -> 123.46

리스트

  • [] 안에 원소를 넣어 초기화한다. 쉼표로 구분한다.
  • 비어있는 리스트를 선언하고자 할 때는 list() 혹은 [] 를 이용할 수 있다.
  • 리스트의 원소에 접근할 때는 index 값을 괄호에 넣는다.
  • index는 0부터 앞에서 시작하고, -1부터 뒤에서 시작한다.
  • 리스트에서 연속적인 원소를 가져올 때는 '슬라이싱'을 이용한다.
    arr[ n : m+1 ]
  • 리스트 컴프리핸션: 리스트를 초기화 하는 방법. if, for을 사용할 수 있다. 
	arr = [ i for i in range(10) ] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	arr = [ i for i in range(20) if i%2 == 1 ] = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
	arr = [ i*i for i in range(1,10) ] = [1, 4, 9, 16, 25, 36, 49, 64, 81]
  	
    # 2차원 리스트를 초기화 할 때 효과적이다.
	arr = [ [0]*m for _ in range(n) ] (n행, m열의 리스트 생성)
	( 잘못된 예시: arr = [[0]*m] * n )
  • arr.append(): 리스트 끝에 원소 삽입
  • arr.sort(): 오름차순 정렬
    (reverse = True): 내림차순 정렬
  • arr.reverse(): 원소 순서 뒤집기
  • arr.insert(): 특정한 위치에 삽입
  • arr.count(): 특정한 값의 개수를 센다.
  • arr.remove(): 특정한 값을 갖는 원소를 제거하는데, 하나만 제거한다.
a = [1, 2, 3, 4, 5, 5, 5]
remove_set = {3, 5}
result = [ i for i in a if i not in remove_set ]	# remove_set에 들어있지 않은 것들만 새로 저장한다. == 3, 5 제거
print(result)

문자열

  • 덧셈을 이용하면 문자열이 연결된다.
  • 곱셈을 이용하면 그 값만큼 더해진다.
  • 인덱싱과 슬라이싱을 이용할 수 있다.
  • 특정 인덱스의 값을 변경할 수는 없다.

튜플

  • 소괄호()를 이용한다.
  • 리스트와 유사하지만, 값을 변경할 수 없다.
  • 인덱싱과 슬라이싱을 이용할 수 있다.
  • 리스트에 비해 공간 효율적이다.
  • 서로 다른 성질의 데이터를 묶어서 관리해야 할 때 사용한다.
    최단 경로 알고리즘에서 (비용, 노드번호)의 형태로 자주 사용함.
  • 데이터의 나열을 Hashing의 Key 값으로 사용해야 할 때 좋다.
    튜플은 데이터 변경이 불가능하므로 Key 값으로 사용될 수 있다.

사전 자료형

  • Key와 Value의 쌍을 데이터로 가지는 자료형이다.
    순차적으로 저장하는 것과 다르다.
  • 원하는 '변경 불가능한 자료형'을 Key로 사용할 수 있다.
  • 파이썬의 사전 자료형은 Hash Table을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다.
data = dict()
data['사과'] = 'Apple'
data['바나나'] = 'Banana'
data['코코넛'] = 'Coconut'

# Key: '사과', Value: 'Apple'
  • 키 데이터만 뽑아서 리스트로 이용할 때는 keys() 함수를 이용한다.
  • 값 데이터만 뽑아서 리스트로 이용할 때는 values() 함수를 이용한다.
b = {
	'홍길동': 97,
	'이순신': 98
}

print(b)		# {'홍길동': 97, '이순신': 98}
print(b['이순신'])	# 98

key_list = list(b.keys())
print(key_list)	# ['홍길동','이순신']

집합 자료형

  • 중복이 없고, 순서가 없다.
  • 집합은 리스트 혹은 문자열을 이용해서 초기화할 수 있다.
    이 때 set() 함수를 이용한다.
  • {} 안에 ,로 원소를 구분하여 삽입함으로써 초기화 할 수 있다.
  • 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다.
# list를 set으로 하여 초기화
data = set([1,1,2,3,4,4,5])
print(data)	# {1, 2, 3, 4, 5}

# 바로 초기화
data = {1,1,2,3,4,4,5}
print(data)	# {1, 2, 3, 4, 5}
  • 합집합( | ), 교집합( & ), 차집합( - ) 연산 등이 있다.
  • data.add( 4 ): 새로운 원소 추가
  • data.update( [5, 6] ): 새로운 원소 여러 개 추가
  • data.remove( 3 ): 특정한 값을 갖는 원소 삭제

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

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

기본 입출력

  • input(): 한 줄의 문자열을 입력 받음
  • map(): 리스트의 모든 원소에 각각 특정한 함수를 적용함
    ex) 공백을 기준으로 구분된 데이터를 입력 받을 때
    list( map( int, input().split() ) )
    ex) 공백을 기준으로 구분된 데이터의 개수가 많지 않다면
    a, b, c = map( int, input().split() )
  • 빠르게 입력받기: sys.stdin.readline() 메서드 사용.
    단, 입력 후 엔터가 줄바꿈 기호로 입력되므로 rstrip() 메서드를 함께 사용.
    ( rstrip()이 줄바꿈 기호(\n)를 제거해준다. )
    이진탐색, 그래프, 정렬에서 자주 사용된다.
  • 출력: print()
    각 변수를 콤마(,)를 이용하여 띄어쓰기로 구분하여 출력한다.
    print()는 출력 이후에 줄바꿈을 수행한다. end 속성을 이용하면 줄바꿈 안 할 수 있다.
    문자와 숫자를 동시에 출력할 때, 콤마(,)를 사용하면 출력이 가능하지만,
    덧셈(+)을 사용하면 오류가 난다.
    곱셈(*)과 정수를 사용하면 정수만큼 곱해진다.
    나머지 연산자(**, %, //, /, -)는 오류가 난다.
  • 파이썬 3.6부터 f-string을 사용할 수 있다.
    문자열 앞에 접두사 'f'를 붙여 사용한다.
    중괄호 안에 변수명을 기입하여 간단히 문자열과 다른 자료형을 함께 넣을 수 있다.
answer = 7
print(f"정답은 {answer}입니다.")

조건문

if ~ elif ~ else 형태가 기본.

  • 조건문의 간소화
score = 85
if score >= 80: result = "Success"	# 줄바꿈을 하지 않아도 됨
else: result = "Fail"
score = 85
result = "Success" if score >= 80 else "Fail"	# 한 줄에 작성할 때, if문이 중간에 들어감에 주의

print(result)	# Success

(이외 설명은 잘 알고 있어서 생략.)

파이썬의 기타 연산자

  • 다수의 데이터를 담는 자료형을 위해 in 연산자와 not in 연산자가 제공된다.
    리스트, 튜플, 문자열, 딕셔너리 모두에서 사용 가능하다.
  • 아무것도 처리하고 싶지 않을 때 pass 키워드를 사용한다.
    디버깅 과정에서 일단 조건문의 형태만 만들어 놓고 조건문을 처리하는 부분은 비워놓고 싶은 경우.
  • 파이썬에서는 0 < x < 20 같은 수학의 부등식을 그대로 사용할 수 있다.

반복문

  • while문 보다 for문을 사용하는 게 더 간결하다.
  • for는 특정한 변수를 이용하여 in 뒤에 오는
    데이터(리스트, 튜플)에 포함되어 있는 원소를
    첫번째 인덱스부터 차례대로 하나씩 방문합니다.
  • for문에서 연속적인 값을 차례대로 순회할 때는 range()를 이용한다. range(시작값, 끝값+1)
  • continue 키워드: 반복문에서 남은 코드의 실행을 건너뛰고, 다음 반복을 진행하고자 할 때 사용함.
  • break 키워드: 반복문을 즉시 탈출하고자 할 때 break를 사용함.

함수

특정한 작업을 하나의 단위로 묶어 놓은 것 -> 중복을 줄일 수 있다.

  • 내장함수: 파이썬이 기본으로 제공하는 함수
  • 사용자 정의 함수: 개발자가 직접 정의하여 사용할 수 있는 함수
def 함수명(매개변수):	# 매개변수: 함수 내부에서 사용할 변수
    실행할 소스코드
    return 반환값		# 반환값: 함수에서 처리된 결과를 반환
def add(a,b):
    return a+b
print(add(3,7))
def add(a,b):
    print('함수의 결과:', a+b)
add(3,7)
  • 매개변수를 직접 지정할 수 있다. 매개변수의 순서가 달라도 상관없다.
def add(a,b):
    print('함수의 결과:', a+b)
add(b=3, a=7)

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

    배열은 global 키워드 없이 바로 참조가 가능하다.
    그러나 전역변수의 값을 변경하고자 한다면
    global 키워드를 사용하여 값을 변경할 수 있다.

    함수 내부와 외부에 같은 이름의 변수가 선언된다면,
    함수 내부의 지역변수를 우선한다.

  • 파이썬에서 함수는 여러 개의 반환값을 가질 수 있다.

def operator(a,b):
    add_var = a+b
    subtract_var = a-b
    multiply_var = a*b
    divide_var = a/b
    return add_var, subtract_var, multiply_var, divide_var	# 패킹: 여러 개의 변수가 한 번에 반환되는 것

a,b,c,d = operator(7,3)	# 언패킹: 반환된 값들을 차례대로 특정 변수에 저장하는 것
print(a,b,c,d)

람다 표현식

함수를 간단하게 작성할 수 있다.
특정한 기능을 수행하는 함수를 한 줄에 작성활 수 있다는 점이 특징이다.

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

함수의 기능이 간단하거나, 한 번 사용하고 말 경우에 유용하게 쓸 수 있다.

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

def my_key(x):
    return x[1]	# index가 1이므로 두번째 원소를 기준으로 정렬하도록 함

print(sorted(arr, key=my_key))	# sorted함수는 key=에 함수를 넣어서, 정렬 기준을 명시해 줄 수 있다.
print(sorted(arr, key=lambda x: x[1]))	# 정렬은 한 번 사용하고 말기에 lambda 함수로 간편히 표현할 수 있다.
list1 = [1,2,3,4,5]
list2 = [6,7,8,9,10]

result = map(lambda a,b: a+b, list1, list2)	# list1, list2의 원소들이 하나씩 순서대로 더해진다.

print(list(result))	# [7,9,11,13,15]

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

  • 내장함수: 기본 입출력 함수부터 정렬 함수까지 기본적인 함수들을 제공한다.
    • 파이썬 프로그램을 작성할 때 필수 기능을 포함
    • sum(), min(), max(), eval(), sorted()
  • itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공한다.
    • 특히 순열과 조합 라이브러리는 코테에서 자주 사용된다.
    • permutations(), combinations(), product(), combinations_with_replacement()
from itertools import permutations

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

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

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

result = list(combinations(data, 2))	# 2개를 뽑는 모든 조합 구하기
print(result)
  • heapq: 힙(heap) 자료구조를 제공한다.
    • 일반적으로 우선순위 큐 기능을 구현하기 위해 사용된다.
  • bisect: 이진탐색 기능을 제공한다.
  • collections: 덱, 카운터 등의 유용한 자료구조를 포함한다.
  • math: 필수적인 수학적 기능을 제공한다.
    • 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련 함수부터 파이와 같은 상수를 포함한다.
    • 최대공약수를 구해야 할 때는 math 라이브러리의 gcd() 함수를 이용할 수 있다.
import math

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

a, b = 21, 14

print(math.gcd(21, 14))	# 최대 공약수(GCD) 계산 7
print(lcm(21, 14))		# 최소 공배수(LCM) 계산 42
  • Counter: 등장 횟수를 세는 함수
    리스트와 같은 반복 가능한 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 알려준다.
from collections import Counter

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

print(counter['blue'])	# 'blue'가 등장한 횟수 출력	# 3
print(counter['green'])	# 'green'이 등장한 횟수 출력	# 1
print(dict(counter))		# 사전 자료형으로 반환	#{'red': 2, 'blue': 3, 'green': 1}
profile
송병훈
성실하고 꼼꼼하게
이전 포스트

백준 5635: 생일

다음 포스트

동빈나 알고리즘 정리2

0개의 댓글