복잡도는 알고리즘의 성능을 나타내는 척도
- 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
- 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘
빅오표기법
가장 빠르게 증가하는 항만을 고려하는 표기법
- 함수의 상한만을 나타내게 된다
예를 들어 연산횟수가 3N³+5N²+1,000,000인 알고리즘이 있을때
빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N³)으로 표현
알고리즘 설계 tip
- 코딩 테스트 문제에서 시간제한은 통상 1-5초 가량이다
- 문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항) 이다
- 시간 제한이 1초인 문제를 만났을때, 일반적인 기준은 다음과 같다
N의 범위가 500인 경우 : 시간 복잡도가 O(N³)인 알고리즘을 설계
N의 범위가 2000인 경우 : 시간 복잡도가 O(N²)인 알고리즘을 설계
N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계
N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)인 알고리즘을 설계 - 일반적인 알고리즘 문제 해결 과정은 다음과 같다
- 지문 읽기 및 컴퓨터적 사고
- 요구사항(복잡도) 분석
- 문제 해결을 위한 아이디어 찾기
- 소스코드 설계 및 코딩
일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면 간결하게 소스코드를 작성할 수 있는 형태로 문제를 출제한다.
파이썬 문법
자료형
- 파이썬의 자료형으로는 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전 등이 있다.
<수 자료형> - 정수형(Integer)은 정수를 다루는 자료형이다
양의 정수, 음의 정수, 0이 포함된다 - 실수형은 소수점 아래의 데이터를 포함하는 수 자료형이다
파이썬에서는 변수에 소수점을 붙인 수를 대입하면 실수형 변수로 처리됨
소수부가 0이거나, 정수부가 0인 소수는 0을 생략하고 작성할 수 있다
# 소수부가 0일때 0을 생략
a = .5
print(a) // 5.0
# 정수부가 0일때 0을 생략
a = -.7
print(a) // -0.7- 지수 표현 방식
e나 E를 이용한 지수 표현 방식을 이용 할 수 있다.
e나 E 다음에 오는 수는 10의 지수부를 의미한다
예를 들이 1e9라고 입력하게 되면, 10의 9제곱(1,000,000,000)이 된다
유효숫자e^지수 = 유효숫자 X 10^지수
지수 표현 방식은 임의의 큰 수를 표현하기 위해 자주 사용된다
최단 경로 알고리즘에서는 도달할 수 없는 노드에 대하여 최단 거리를 무한(INF)로 설정한다
이때 가능한 최댓값이 10억 미만이라면 무현(INF)의 값으로 1e9를 이용할 수 있다
# 1,000,000의 지수 표현 방식
a = 1e9
print(a) // 1000000000.0
# 752.5
a = 75.25e1
print(a) // 752.5
# 3.954
a = 3954e-3
print(a) / 3.954예를 들어 10진수 체계에서는 0.3과 0.6을 더한 값이 0.9로 정확히 떨어지지만
2진수에서는 0.9를 정확히 표현할 수 있는 방법이 없다
컴퓨터는 최대한 0.9와 가깝게 표현하지만, 미세한 오차가 발생하게 된다
a = 0.3+0.6
print(a) // 0.89999999999
if a == 0.9;
print(True)
else :
print(False) // False이럴 때는 round()함수를 이용할 수 있으며, 이러한 방법이 권장된다
예를 들어 123.456을 소수 셋째 자리에서 반올림하려면 round(123.456.2)라고 작성하면
결과는 123.46이 된다
a = 0.3+0.6
print(round(a,4)) // 0.9
if round(a, 4) == 0.9;
print(True)
else :
print(False) // True수 자료형에 대하여 사칙연산과 나머지 연산자가 많이 사용된다
단 나누기 연산자(/)를 주의해서 사용해야 한다
파이썬에서 나누기 연산자(/)는 나눠진 결과를 실수형으로 반환한다
다양한 로직을 설계할 때 나머지 연산자(%)를 이용해야 할 때가 많다
ex) a가 홀수인지 체크해야 하는 경우
파이썬에서는 몫을 얻기 위해 몫 연산자(//)를 사용한다
이외에도 거듭 제곱 연산자(**)를 비롯해 다양한 연산자들이
a=7
b=3
# 나누기
print(a/b) // 2.33333333333335
# 나머지
print(a%b) // 1
# 몫
print(a//b) // 2
a=5
b=3
# 거듭 제곱
print(a ** b) // 125
# 제곱근
print( a** 0.5 ) // 2.2360679......9<리스트 자료형>
여러개의 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료혐
사용저 입장에서 C나 자바에서의 배열(Array)의 기능 및 연결 리스트와 유사한 기능을 지원한다
C++ 의 STL vector와 기능적으로 유사하다
리스트 대신에 배열 혹은 테이블이라고 부르기도한다
- 리스트 초기화
리스트는 대괄호([])안에 원소를 넣어 초기화하며, 쉼표(,)로 원수를 구분한다
비어 있는 리스트를 선언하고자 할때는 list() 혹은 간단히 [] 를 이용할 수 있다
리스트의 원소에 접근할 때는 인덱스(index)값을 괄호에 넣는다
인덱스는 0 부터 시작한다 - 리스트의 인덱싱과 슬라이싱
인덱스 값을 입력하여 리스트의 특정한 원소에 접근하는 것을 인덱싱이라고 한다
파이썬의 인덱스값은 양수와 음수 모두 사용할 수 있다
음수를 넣으면 원소를 거꾸로 탐색하게 된다
리스트에서 연속적인 위치를 갖는 원소들을 가져와야 할 때는 슬라이싱을 이용한다
대괄호 안에 콜론(:)을 넣어서 시작 인덱스와 끝 인덱스를 설정할 수 있다
끝 인덱스는 실제 인덴스보다 1을 더 크게 설정한다 - 리스트 컴프리헨션
리스트를 초기화하는 방법 중 하나
대괄호 안에 조건문과 반복문을 적용하여 리스트를 초기화 할 수 있다
# 0부터 9까지의 수를 포함하는 리스트
array = [i for i in range(10)]
print(array) // [0,1,...,8,9]# 리스트 컴프리헨션과 일반적인 코드 비교
# 코드 1:리스트 컴프리헨션
# 0부터 19까지의 수 중에서 홀수만 포함하는 리스느
array = [i for i in range(20) if i%2 ==1]
# 코드 2:일반적인 코드
array = []
for i in range(20) :
if i % 2 == 1:
array.append(i)
# 두 코드모두 실행 결과는 동일하다
# [1,3,5,7,...,17,19]리스트 컴프리헨션은 2차원 리스트를 초기화할 때 효과적으로 사용될 수 있다
특히 N X M 크기의 2차원 리스트를 한 번에 초기화 해야 할 때 매우 유용하다
ex) 좋은 예시 : array = [[0]m for_in range(n)]
만약 2차원 리스트를 초기화할 때 다음과 같이 작성하면 예기치 않은 결과가 나올 수 있다
ex) 잘못된 예시 : array = [[0]m]*n
위 코드는 전체 리스트 안에 포함된 각 리스트가 모두 같은 객체로 인식된다
파이썬에서는 반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바(_)를 자주 사용한다
<문자열 자료형>
문자열 변수를 초기화할 때는 큰 따옴표(")나 작은 따옴표(')를 이용한다
문자열 안에 큰 따옴표나 작은따옴표가 포함되어야 하는 경우가 있다
- 전체 문자열을 큰따옴표로 구성하는 경우, 내부적으로 작은따옴표를 포함할 수 있다
- 전체 문자열을 작음따옴표로 구성하는 경우, 내부적으로 큰따옴표를 포함할 수 있다
- 혹은 백슬래시()를 사용하면, 큰따옴표나 작은따옴표를 원하는 만큼 포함시킬 수 있다
<문자열 연산>
문자열 변수에 덧셈(+)를 이용하면 문자열이 더해져서 연결된다
문자열 변수를 특정한 양의 정수와 곱하는 경우, 문자열이 그 값만큼 여러 번 더해진다
문자열에 대해서도 마찬가지로 인덱싱과 슬라이싱을 이용할 수 있다
다만 문자열은 특정 인덱스의 값을 변경할 수는 없다
<튜플 자료형>
튜플 자료형은 리스트와 유사하지만 다음과 같은 문법적 차이가 있다
튜플은 한 번 선언된 값을 변결할 수 없다
리스트는 대괄호([])를 이용하지마만, 튜플은 소괄호(())를 이용한다
튜플은 리스트에 비해 상대적으로 공간 효율적이다
튜플을 사용하면 좋은 경우
서로 다른 성질의 데이터를 묶어서 관리해야 할때
최단 경로 알고리즘에서는 (비용, 노드 번호)의 형태로 튜플 자료형을 자주 사용한다
데이터의 나열을 해싱의 키 값으로 사용해야 할 때
튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있다
리스트보다 메모리를 효율적으로 사용해야 할 때
<사전 자료형>
사전자료형은 키(key)와 값(value)의 쌍을 데이터로 가지는 자료형이다
리스트나 튜플이 값을 순차적으로 저장하는 것과는 대비된다
사전 자료형은 키와 값의 쌍을 데이터로 가지며, 원하는 '변경 불가능한 자료형'을 키로 사용할 수 있다
파이썬의 사전 자료형은 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다
dict() 함수 이용
사전자료형에서는 키와 값을 별도로 뽑아내기 위한 메서드를 지원한다
키 데이터만 뽑아서 리스트로 이용할 때는 keys() 함수를 이용
값 데이터만 뽑아서 리스트로 이용할 때는 values() 함수를 이용
<집합 자료형>
집합은 다음과 같은 특징이 있다
-중복을 허용하지 않는다
-순서가 없다
집합은 리스트 혹은 문자열을 이용해서 초기화할 수 있다
-이때 set()함수를 이용한다
혹은 중괄호({}) 안에 각 원소를 콤마(,)를 기준으로 구분하여 삽입함으로써 초기화 할 수 있다
데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다
합집합 : 집합 A에 속하거나 B에 속하는 원소로 이루어진 집합(A∪B) #(A|B)
교집합 : 집합 A에도 속하고 B에도 속하는 원소로 이루어진 집합(A∩B) #(A&B)
차집합 : 집합 A의 원소 중에서 B에 속하지 않는 원소들로 이루어진 집합(A-B) #(A-B)
사전 자료형과 집합 자료형의 특징
리스트나 튜플은 순서가 있기 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있다
사전 자료형과 집합 자료형은 순서가 없기 때문에 인덱싱으로 값을 얻을 수 없다
사전의 키(key)혹은 집합의 원소(element)를 이용해 O(1)의 시간 복잡도로 조회한다
자주 사용되는 표준 입력 방법
input() 함수는 한 줄의 문자열을 입력 받는 함수이다
map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용
ex) 공백을 기준으로 구분된 데이터를 입력 받을 때는 다음과 같이 사용한다
list(map(int, input().split()))
ex) 공백을 기준으로 구분된 데이터의 개수가 많지 않다면, 단순히 다음과 같이 사용한다
a,b,c = map(int, input().split())
사용자로부터 입력을 최대한 빠르게 받아야 하는 경우
sys 라이브러리에 정의되어있는 sys.stdin.readLine() 메서드를 이용한다
단, 입력 후 엔터가 줄 바꿈 기호로 입력되므로 rstrip() 메서드를 함께 사용한다
자주 사용되는 표준 출력 방법
파이썬에서 기본 출력은 print() 함수를 이용한다
각 변수를 콤마(,)를 이용하여 띄어쓰기로 구분하여 출력할 수 있다
print()는 기본적으로 출력 이후에 줄 바꿈을 수행한다
줄 바꿈을 원치 않는 경우 'end'속성을 이용할 수 있다
f-string 예제
파이썬 3.6부터 사용 가능, 문자열 앞에 접두사 'f'를 붙여 사용
중괄호 안에 변수명을 기입하여 간단히 문자열과 정수를 함께 넣을 수 있다
answer = 7
print(f"정답은 {answer}입니다.") // 정답은 7입니다.<조건문>
조건문은 프로그램의 흐름을 제어하는 문법
조건문을 이용해 조건에 따라서 프로그램의 로직을 설정할 수 있다
x = 15
if x>=10:
print("x>=10")
if x>=0:
print("x>=0")
if x>=30:
print("x>=30")
// x>=10
// x>=0<들여쓰기>
파이썬에서는 코드의 블록을 들여쓰기로 지정한다
탭을 사용하는 쪽과 공백 문자(space)를 여러 번 사용하는 쪽으로 두 진영이 있다
파이썬 스타일 가이드라인에서 4개의 공백문자를 사용하는 것을 표준으로 설정하고 있다
조건문의 기본적인 형태는 if ~ elif ~ else 이다
조건문을 사용할 때 elif 또는 else 부분은 경우에 따라서 사용하지 않아도 된다
if 조건문 1 :
조건문 1이 True일 때 실행되는 코드
elif 조건문 2:
조건문 1에 해당하지 않고, 조건문 2가 True일 때 실행되는 코드
else :
위의 모든 조건문이 모두 True 값이 아닐 때 실행되는 코드
<비교 연산자>
비교 연산자는 특정한 두 값을 비교할 때 이용
대입연산자(=)와 같음 연산자(==) 차이점에 유의
비교 연산자 설명
X==Y X와 Y가 서로 같을 때 참(true)
X!=Y X와 Y가 서로 다를때 참(true)
X>Y X가 Y보다 클 때 참
X<Y X가 Y보다 작을 때 참
X>=Y X가 Y보다 크거나 같을 때 참
X<=Y X가 Y보다 작거나 같을 때 참
<논리 연산자>
논리값(True/False)사이의 연산을 수행할 때 사용
논리 연산자 설명
X and Y X와 Y가 모두 참일때 참
X or Y X와 Y중에 하나만 참이어도 참
not X X가 거짓일때 참
<파이썬의 기타 연산자>
다수의 데이터를 담는 자료형을 위해 in 연산자와 not in연산자가 재공된다
리스트, 튜플, 문자열, 딕셔너리 모두에서 사용이 가능
x in 리스트 리스트 안에 x가 들어가 있을 때 참
x not in 리스트 문자열 안에 x가 들어가 있지 않을때 참
<파이썬의 pass키워드>
아무것도 처리하고 싶지 않을 때 pass키워드를 사용한다
예시) 디버깅 과정에서 일단 조건문의 형태만 만들어 놓고 조건문을 처리하는 부분은 비워놓고 싶은 경우
score = 85
if score>=80 :
pass # 나중에 작성할 소스코드
else:
print('성적이 80점 미만입니다.')
print('프로그램을 종료합니다')
// 프로그램을 종료합니다조건문에서 실행될 소스코드가 한 줄인 경우,굳이 줄 바꿈을 하지 않고도 간략하게 표현할 수 있다
score = 85
if score>=80:result = "Success"
else : result = "Fail"
// Success조건부 표현식은 if ~ else문을 한 줄에 작성할 수 있도록 해준다
score=85
result = "Success" if score >=80 else "Fail"
print(result)
// Success파이썬 조건문 내에서의 부등식
다른 프로그래밍 언어와 다르게 파이썬은 조건문 안에서 수학의 부등식을 그대로 사용할 수 있다
예를 들어 x>0 and x<20과 0<x<20은 같은 결과를 반환한다
<반복문>
특정한 소스코드를 반복적으로 실행하고자 할 때 사용하는 문법
파이썬에서는 while문과 for문이 있는데, 어떤 것을 사용해도 상관없다
다만 코딩 테스트에서의 실제 사용 예시를 확인해보면, for문이 더 간결한 경우가 많다
무한루프란 끊임없이 반복되는 반복 구문을 의미한다
코테에서 무한 루프를 구현할 일은 거의 없다
반복문을 작성한 뒤에는 항상 반복문을 탈출할 수 있는지 확인한다
반복문 : for문
for문의 구조는 특정한 변수를 이용하여 'in'뒤에 오는 데이터(리스트, 튜플 등)에 포함 되어 있는 원소를 첫번째 인덱스부터 차례대로 하나씩 방문한다
for 변수 in 리스트 :
실행할 소스코드
for문에서 연속적인 값을 차례대로 순회할 때는 range()를 주로 사용한다
이때 range(시작 값, 끝 값 +1) 형태로 사용한다
인자를 하나만 넣으면 자동으로 시작 값은 0이 된다
result = 0
# i는 1부터 9까지의 모든 값을 순회
for i in range(1,10) :
result += i
print(result) // 45반복문에서 남은 코드의 실행을 건너뛰고, 다음 반복을 진행하고자 할 때 continue를 사용한다
1부터 9까지의 홀수의 합을 구할 때
result = 0
for i in range(1,10) :
if i % 2 == 0:
continue
result += i
print(result) // 25반복문을 즉시 탈출하고자 할 때 break를 사용한다
1부터 5까지의 정수를 차례대로 출력하고자 할 때
i = 1
while True:
print("i : ", i)
if i == 5:
break
i += 1
// i : 1 ... i : 5함수와 람다 표현식
함수란 특정한 작업을 하나의 단위로 묶어 놓은 것을 의미
함수를 사용하면 불필요한 소스코드의 반복을 줄일 수 있다
내장 함수 : 파이썬이 기본적으로 제공하는 함수
사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수
매개변수 : 함수 내부에서 사용할 변수
반환 값 : 함수에서 처리된 결과를 반환
def 함수명(매개변수):
실행할 소스코드
return 반환 값# 더하기 함수 예시
def add(a,b):
return a+b
print(add(3,7)) // 10파라미터의 변수를 직접 지정할 수 있다
이 경우 매개변수의 순서가 달라고 상관없다
<global 키워드>
global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고, 함수 바깥에 선언된 변수를 바로 참조하게 된다
a=0
def func():
global a
a+=1
for i in range(10):
func()
print(a) // 10함수 안에 지역변수로써 전역변수와 동일한 이름을 가지면
함수 안에서는 지역변수가 우선적으로 참조가 된다
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]전역 변수에 있는 값 참조
array = [1,2,3,4,5]
def func() :
global array
array = [3,4,5]
array.append(6)
func()
print(array)
// [3,4,5,6]파이썬에서 함수는 여러개의 반환 값을 가질 수 있다
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)<람다 표현식>
특정한 기능을 수행하는 함수를 한 줄에 작성할 수 있다는 점이 특징
def add(a,b):
return a+b
# 일반적인 add() 메서도 사용
print(add(3,7))
# 람다 표현식으로 구현한 add() 메서드
print((lamda a,b:a+b)(3,7))
// 10 10# 내장 함수에서 자주 사용되는 람다 함수
array = [('홍길동',50),('이순신',32),('아무개',74)]
def my_key(x):
return x[1]
print(sorted(array, key=my_key))
print(sorted(array, key=landa x:x[1]))
// [('이순신'),32), ('홍길동',50), ('아무개',74)]
// [('이순신'),32), ('홍길동',50), ('아무개',74)]# 여러 개의 리스트에 적용
list1 = [1,2,3,4,5]
list2 = [6,7,8,9,10]
result = map(lamda a,b : a+b, list1, list2)
print(list(result)) // [7,9,11,13,15]실전에서 유용한 표준 라이브러리
내장 함수 : 기본 입출력 함수부터 정렬 함수 까지 기본적인 함수들을 제공
- 파이썬 프로그램을 작성할 때 없어서는 안되는 필수적인 기능 포함
itertools : 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들을 제공 - 특히 순열과 조합 라이브러리는 코딩 테스트에서 자주 사용된다
heapq : 힙(Heap) 자료구조 제공 - 일반적으로 우선순위 큐 기능을 구현하기 위해 사용
bisect : 이진 탐색(바이너리 서치) 기능을 제공
collections : 덱(deque), 카운터(Counter)등의 유용한 자료구조를 포함
math : 필수적인 수학적 기능을 제공 - 팩토리얼, 제곱근, 최대공약수(GCD),삼각함수 관련 함수부터 파이(pi)와 같은 상수 포함
# 자주 사용되는 내장 함수
# sum()
result = sum([1,2,3,4,5])
print(result) // 15
# min(),max()
min_result = min(7,3,5,2)
max_result = max(7,3,5,2)
print(min_result,max_result) // 2 7
# eval()
result = eval("(3+5)*7")
print(result) // 56
# sorted()
result = sorted([9,1,8,5,4])
reverse_result = sorted([9,1,8,5,4], reverse=True)
print(result)
print(reverse_result)
// [1,4,5,8,8]
// [9,8,5,4,1]
# sorted() with key
array=[('홍길동', 35),('이순신',75),('아무개',50)]
result = sorted(array, key=lamda x:x[1], reverse=True)
print(result)
// [('이순신',75), ('아무개',50),('홍길동',35)]<순열과 조합>
모든 경우의 수를 고려해야 할 때 효과적인 라이브러리 사용
순열 : 서로 다른 n개에서 서로 다른 r개를 선택하여 일렬로 나열하는 것
{'A','B','C'}에서 세 개를 선택하여 나열하는 경우 : 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'
from itertools import permutations
data = ['A','B','C'] # 데이터 준비
result = list(permutations(data,3)) # 모든 순열 구하기
print(result)조합 : 서로 다른 n개에서 순서에 상관 없이 서로 다른 r개를 선택하는 것
{'A','B','C'}에서 순서를 고려하지 않고 두 개를 뽑는 경우 : 'AB','AC','BC
from itertools import combinations
data = ['A','B','C'] # 데이터 준비
result = list(combinations(data,2)) # 2개를 뽑는 모든 조합 구하기
print(result)
# 중복 순열과 중복 조합
from itertools import product
data = ['A','B','C']
result = list(product(data, repeat=2)) # 2개를 뽑는 모든 순열 구히기(중복허용)
from itertools import combinations_with_replacement
data = ['A','B','C']
result = list(combinations_with_replacement(data,2)) # 2개를 뽑는 모든 조합 구하기(중복허용)< Counter >
파이썬 collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공
리스트와 같은 반복 가능한(iterable) 객체가 주어졌을 때 내부의 원소가 몇 번씩 등장했는지를 알려준다
from collections import Counter
counter = Counter(['red','blue','red','green','blue','blue'])
print(counter['blue'])
print(counter['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(21,14)) # 최대 공약수(GCD)계산
print(lcm(21,14)) # 최소 공배수(LCM) 계산
// 7
// 42