알고리즘 정리 낙서장(나중에 글 정리해서 알고리즘 카테고리에 옮길 것!)
스티커 메모 개수가 너무 늘어나서 여기에 옮겨 적음
최단 경로 알고리즘
가장 짧은 경로를 찾는 알고리즘
한 지점에서 다른 한 지점까지의 최단 경로
한 지점에서 다른 모든 지점까지의 최단 경로
모든 지점에서 다른 모든 지점까지의 최단 경로
각 지점은 그래프에서 노드로 표현
지점 간 연결된 도로는 그래프에서 간선으로 표현
다익스트라 최단 경로 알고리즘
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산
음의 간선이 없을 때 정상적으로 동작 (현실 세계의 도로는 음의 간선으로 표현 X)
다익스트라 알고리즘은 그리드 알고리즘으로 분류
매 상황에서 가장 비용이 적은 노드를 선택해 반복
1 출발 노드를 설정
2 최단 거리 테이블 초기화
3 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5 3번 4번 반복
다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않는다
다이나믹 프로그래밍 구형은 탑다운 보텀업 두 가지 방식으로 구성
1 최적 부분 구조
큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제 해결
2. 중복되는 부분 문제
동일한 작은 문제를 반복적으로 해결해야함
피보나치 수열
재귀함수
def fibo(x):
if x==1 or x==2:
return 1
return fibo(x-1) + fibo(x - 2)
print (fibo(4))
단순 재귀 함수로 피보나치 수열을 해결하면 지수 시간 복잡도를 가지게 됨으로 N이 조금만 커져도 매우 많은 시간이 걸림
효율적인 해법
다이나믹 프로그래밍 사용 조건을 만족하는지 확인
1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.
2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결
메모이제이션 (탑다운 방식(하향식)에서 사용)
한 번 계산한 결과를 메모리 공간에 메모하는 기법
같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다
값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
다이나믹 프로그래밍의 전형적인 형태는 보텀업 (상향식) 방식
결과 저장용 리스트는 DP 테이블이라고 부른다.
메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미
(탑 다운) - 복잡도 O(N) 으로 감소
# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0] * 100
def fibo(x):
if x==1 or x==2:
return 1
#이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
#아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과반환
d[x] = fibo(x-1) + fibo(x-2)
returnd[x]
(보텀업)
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n+1):
d[i] = d[i-1] + d[i -2]
다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.
다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.
다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.
분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
분할 정복의 대표적인 예시인 퀵 정렬
한 번 기준 pivot이 자리를 변경해서 자리를 잡으면 pivot 위치는 바뀌지 않는다. 분할 이후에 해당 피벗을 다시 처리하는 부분 문제는 호출하지 않는다.
다이나믹 프로그래밍 유형임을 파악하는 것이 중요
가장 먼저 그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
다른 알고리즘으로 풀이 방법이 떠오르지 않으면 다이나믹 프로그래밍을 고려해 본다.
일단 재귀 함수로 비효율적인 완전 탐색 프로그램으로 작성한 뒤 코드를 개선하는 방법을 사용 가능
코딩 테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다.
개미 전사
식량을 선택할 수 있는 경우의 수 구한 후 최적의 해
ai = i 번째 식량창고까지의 최적의 해 (얻을 수 있는 식량의 최댓값)
ki = i 번째 식량창고에 있는 식량의 양
ai = max(ai-1,ai-2 +ki)
한 칸 이상 떨어진 식량찬고는 항상 털 수 있으므로 i-3번째 이하는 고려할 필요가 없다.
n = int(input())
array = list(map(int, input().split()))
#앞서 계산된 결과를 저장하기 위한 DP테이블 초기화
d = [0]*100
#다이나믹 프로그래밍 진행 (보텀업)
d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, n):
d[i] = max(d[i-1],d[i-2]+array[i])
#계산된 결과 출력
print(d[n-1])
1로 만들기
정수 X가 주어졌을 때 연산 4가지
X가 5로 나누어 떨어지면 5로 나눈다.
X가 3으로 나누어 떨어지면 3으로 나눈다.
X가 2로 나누어 떨어지면 2로나눈다.
X에서 1을 뺀다.
연산 사용횟수의 최솟값 구하기
최적 부분 구조와 중복되는 부분 문제를 만족한다.
ai = i를 1로 만들기 위한 최소 연산횟수
ai = min(ai-1,ai/2, ai/3, ai/5) + 1
1을 빼는 연산을 제외하고 해당 수로 나누어 떨어질 때에 한해 점화식을 적용 할 수 있다.
x = int(input())
#앞서 계산된 결과를 저장하기 위한 DP테이블 초기화
d= [0]*30001
#다이나믹 프로그래밍 진행 (보텀업)
for i in range(2, x+1):
d[i] = d[i-1] + 1
if i % 2 == 0:
d[i] = min(d[i], d[i//2]+1)
if i % 3 == 0 :
d[i] = min(d[i],d[i//3]+1)
if i % 5 == 0:
d[i] = min(d[i], d[i//5]+1)
print(d[x])
효율적인 화폐 구성
N가지 종류의 화폐가 있다. 화폐들의 개수를 최소한 이용해서
그 가치의 합이 M원
ex) 2,3원 15원 = 3원 5개
각 화폐 단위인 K를 하나씩 확인하며
a i-k 를 만드는 방법이 존재하는 경우 ai = min(ai,ai-k +1)
ai-k를 만드는 방법이 존재하지 않는 경우 ai = INF
각 인덱스에 해당하는 값으로 INF 값 설정 (ex 10001)
첫 번째 화폐 단위인 2를 확인
0 2 4 6 -> 0 1 2 3 갱신
두 번째 화폐 단위인 3을 확인
0 2 3 4 5 6 7 -> 0 1 1 2 2 2 3 갱신
세 번째 화폐 단위인 5를 확인
0 2 3 4 5 6 7 -> 0 1 1 2 1 2 2 갱신
n, m = map(int, input().split())
array=[]
for i in range(n):
array.append(int(input()))
#한번 계산된 결과를 저장하기 위한 DP테이블 초기화
d = [10001]*(m+1)
#다이나믹 프로그래밍 진행(보텀 업)
d[0] = 0
for i in range(n):
for j in range(array[i], m+1):
if d[j - array[i]] != 10001: #(i-k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j-array[i]]+1)
#계산된 결과 출력
if d[m] == 10001: #최종적으로 M 원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])
금광
채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작하며, m-1번에 걸쳐서 매번 위, 오른쪽 오른쪽 아래 3가지 중 하나의 위치로 이동, 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력
dp[i][j] = array[i][j] + max(dp[i-1][j-1], dp[i][j-1], dp[i+1][j -1])
for tc in range(int(input())):
n, m = map(int, input().split())
array = list(map(int, input().split()))
#다이나믹 프로그램을 위한 2차원 DP테이블 초기화
dp = []
index = 0
for i in range(n):
dp.append(array[index:index + m])
index += m
#다이나믹 프로그래밍 진행
for j in range(1, m):
for i in range(n):
#왼쪽 위
if i == 0: left_ up = 0
else: left_up = dp[i-1][j-1]
#왼쪽 아래
if i == n - 1: left_down = 0
else: left_down = dp[i+1][j-1]
#왼쪽
left =dp[i][j-1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in renge(n):
result = max(result, dp[i][m-1])
print(result)
병사 배치하기
전투력이 높은 병사가 앞쪽에 오도록 내림차순
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 최장 증가 부분 수열 문제로 변환
array.reverse()
#다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
#열외 해야하는 병사의 최소 수를 출력
print(n - max(dp))
함수형 프로그래밍 VS 객체지향 프로그래밍
AI, IoT, bitcoin, big data 등 방대한 데이터를 빠르게 병렬, 안정적으로 계산하기 위해서 주목
특징
1. 순수함수
동일한 인자를 넣었을 때 동일한 인자값 반환, 외부에 영향을 받지 않도록 작성을 해야 함 ( 함수 안에서 값 변한다면 절차지향)
2. 비상태 불변성 Stateless, Immutability
전달된 데이터 변경 X 외부의 상태나 함수에 인자로 전달된 데이터의 상태를 변경하지 않음으로서 sideeffect(부작용)을 만들지 않음으로 불변성 유지 멀티스레드 환경에서 정상적으로 작동
3. Expressions Only
if, switch,for 사용 X
4. First-class and higher - order functions
함수를 변수에 할당, 함수에 인자로 전달하거나 리턴일들을 할 수 있어야하며 함수자체를 인자로 전달하거나 함수에서 또 다른 함수를 호출하거나 하는 두가지 속성을 가져야함
*Monad
목적지나 목표에 따라 적절한 방식으로 개발
API?
라이브러리나 프레임워크에서 우리가 이용할 수 있는 함수를 API 라고 부름 (내부의 구현 사항을 숨겨 두고 외부에서 사용하는 사람이 필요한 것만 노출해 해두는 것 을 인터페이스. API. 라 한다)
GIPHY 개발툴에서 제공하는 SDK, OPEN API 이용, Spotify 에서 제공하는 API, 카카오 API
https://github.com/public-apis/public-apis
이진 탐색 알고리즘
순차 탐색: 리스트 안에 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인
이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색
시작점, 끝점, 중간점을 이용(인덱스 의미)
시작점 0 끝점 9 중간점 4 (소수점 이하 제거)
시작점 0 끝점 3 중간점 1 (소수점 이하 제거)
시작점 2 끝점 3 중간점 2
이진 탐색의 시간 복잡도
단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 log2N 에 비례
이진탐색은 O(log N) 보장
#재귀함수
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
#찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
#중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
#중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else:
return binary_search(array, target, mid + 1, end)
#원소의 개수와 찾고자 하는 값 입력 받기
n,target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n - 1)
result 가 None 이 아니면 result + 1 해서 위치 출력
while start <= end:
mid = (start+end) // 2
if 같으면 mid
elif 중간점이 찾고자하는값보다 크면 end = mid - 1
else 중간점이 찾고자하는 값보다 작으면 start = mid + 1
bisect_left(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스 반환
bisect_right(a,x): '' 가장 오른쪽 인덱스 반환
값이 특정 범위에 속하는 데이터 개수 구하기
from bisect import bisect_left, bisect_right
#값이 left val, right val 인 데이터 개수를 반환하는 함수
def count_by_range(a, left_val, right_val):
right_index = bisect_right(a, right_val)
left_index = bisect_left(a, left_val)
return right_index - left_index
#배열
a = list ~
#값이 4인 데이터 개수
count_by_range(a, 4, 4)
#값이 [-1, 3] 범위에 있는 데이터 개수
count_by_range(a,-1,3)
파라메트릭 서치(일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.)
최적화 문제를 결정 문제 Y/N 로 바꾸어 해결하는 기법
ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
문제 - 손님이 요청한 총 길이가 M 일때 M만큼 떡을 얻기 위해 절단기의 높이의 최댓값을 구하는 프로그램
적절한 높이를 찾을 때 까지 이진 탐색을 수행하여 높이 H를 반복하여 조정
현재 이 높이로 자르면 조건을 만족할 수 있는가? 를 확인한 뒤에 조건의 만족 여부 Y/N 에 따라 탐색 범위를 좁혀서 해결할 수 있다.
정수 0~ 10억
큰 탐색 범위를 보면 가장 먼저 이진 탐색을 떠올려라
시작점 0 끝점 19 중간점 9 (중간점 == 높이)
시작점 10 끝점 19 중간점 14
시작점 15 끝점 19 중간점 17
시작점 15 끝점 16 중간점 15
중간점의 값은 시간이 지날수록 최적화된 값이 되기 때문에 떡의 길이의 합이 떡의 길이보다 크거나 같을 때 마다 중간점의 값을 기록하면 된다.
#떡의 개수 와 요청한 떡의 길이
n, m = list(map(int,input().spilt(' ')))
#각 떡의 개별 높이 정보를 입력
array = list(map(int, input().split()))
#이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)
#이진 탐색 수행 (반복)
result = 0
while(start <= end):
total = 0
mid = (start+end) // 2
for x in array:
#잘랐을 때 떡의 양 계산
if x > mid:
total += x - end
#떡의 양이 부족한 경우 더 많이 자르기 (왼쪽 탐색)
if total < m:
end = mid - 1
#떡의 양이 충분한 경우 덜 자르기 (오른쪽 탐색)
else:
result = mid # 최대한 덜 잘랐을 때가 정답이므로 여기서 result 기록
start = mid + 1
print(result)
정렬된 배열에서 특정 수의 개수 구하기
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있다.
이때 이 수열에서 x 가 등장하는 횟수 계산
O logN 으로 알고리즘 설계하지 않으면 시간 초과
일반적인 선형 탐색으로는 시간 초과
데이터가 정렬되어 있기 때문에 이진 탐색을 수행
from bisect import bisect_left, bisect_right
#값이 left val, right val 인 데이터 개수를 반환하는 함수
def count_by_range(a, left_val, right_val):
right_index = bisect_right(a, right_val)
left_index = bisect_left(a, left_val)
return right_index - left_index
#데이터의 개수 N 찾고자 하는 값 x
n, x = map(int, input().split())
#배열
a = list ~
#값이 2인 데이터 개수
count_by_range(a, 2, 2)
정렬 알고리즘
데이터를 특정한 기준에 따라 순서대로 나열
선택정렬
- 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복
if array[min_index] > array[j] # j = i+1~len(array)
min_index = j
array[i], array[min_index] = array[min_index], array[j]
삽입정렬 - 최선의 경우 O N 의 시간 복잡도
- 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
for i in range(1, len~) # 2번째 부터
for j in range(i, 0, -1): #인덱스 i 부터 1까지 1씩 감소하여 반복
if array[j] < array[j-1] #한 칸씩 왼쪽으로 이동
array[j], array[j-1] = array[j -1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 자리에서 멈춤
break
퀵 정렬
기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
첫 번째 데이터를 pivot
왼쪽에서부터 pivot 보다 큰값과 오른쪽에서 pivot보다 작은값 서로 스위칭
왼쪽과 오른쪽 위치가 엇갈리는 경우 pivot 과 작은 데이터의 위치를 서로 변경
이상적인 경우 분할이 절반씩 일어난다면 연산횟수로 O NlogN 을 기대
-표준 라이브러리 이용할 때 NlogN 기대
최악의 경우 O N^2
- 이미 정렬된 배열에 대해서 퀵 정렬을 수행하게 될 때
def quick_sort(array, start, end):
if start >= end: #원소가 1개인 경우 종료
return
pivot = start
left = start + 1
reight = end
while(left <= right):
#피벗보다 큰 데이터를 찾을 떄 까지 반복
while(left <= end and array[left] <= array[pivot])
left += 1
#피벗보다 작은 데이터를 찾을 때 까지 반복
while(right > start and array[right] >= array[pivot]):
right -=1
if(left > right): #엇갈렸다면 작은 데이터와 피벗을 교체
array[right], array[pivot] = array [pivot], array[right]
else: #엇갈리지 않았으면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
#분할 이후 왼쪽과 오른쪽 각각 정렬 수행
quick_sort(array, start, right - 1)
quick_sort(array, right +1 , end)
quick_sort(array, 0 , len(array) - 1)
파이썬의 장점을 살린 방식
def quick_sort(array):
#리스트가 하나 이하의 원소만을 담고 있다면 종료
if len(array) <= 1:
return array
pivot = array[0] # 피벗은 첫 번째 원소
tail = array[1:] # 피벗은 제외한 리스트
left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
right_side = [x for x in tail if x> pivot]# 분할된 오른쪽 부분
return quick_sort(left_side) + [pivot] + quick_sort(rifgt_side)
print(quick_sort(array))
계수 정렬
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
데이터 개수가 N 데이터 중 최대값 K일 때 최악의 경우에도 O(N+K)를 보장
#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 #각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): #리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end = ' ') #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
시간 + 공간 복잡도 O(N+K)
동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적
평균 시간 복잡도 공간 복잡도 특징
선택 정렬 ON^2 O N 아이디어 매우 간단
삽입 정렬 ON^2 O N 데이터가 거의 정렬되어 있을 때 가장 빠름
퀵 정렬 O NlogN ON 대부분의 경우 가장 적합, 충분히 빠름
계수 정렬 O N+K O N+K 데이터의 크기가 한정되어 있는 경우에만 사용 가능하지만 매우 빠름
문제 두 배열의 원소 교체:
매번 배열 A 에서 가장 작은 원소를 골라 배열 B에서 가장 큰 원소와 교체
A오름차순 B 내림차순
A의 원소가 B 원소보다 작을 때만 교체 수행
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list ``
#첫번째 인덱스 부터 확인하며 두 배열의 원소를 최대 K번 비교
for i in range(k):
#A의 원소가 B원소보다 작은 경우
if a[i] < b[i]
#두 원소 교체
a[i], b[i] = b[i], a[i]
else: #A의 원소가 B 원소보다 크거나 같을 때 반복문 탈출
break
print(sum(a)) #배열 A의 모든 원소의 합
복잡도
시간복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
복잡도가 낮을 수록 좋은 알고리즘
N의 범위가 500인 경우 O N^3
2000인 경우 O N^2
100,000인 경우 O NlogN
10,000,000인 경우 O N 인 알고리즘을 설계하면 문제를 풀 수 있다.
지문 읽기 및 컴퓨터적 사고
요구사항 복잡도 분석
문제 해결을 위한 아이디어 찾기
소스코드 설계 및 코딩
import time
start_time = time.time() # 측정 시작
end_time = time.time() # 측정 종료
print("time:", end_time - start_time) #수행 시간 출력
자료형
정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전
1e9 = 1 x 10^9
소수 셋째 자리 반올림 round(a, 2)
파이썬에서 / 나눠진 결과를 실수형으로 반환
몫 연산자(//) 거듭 제곱 연산자(**)
# 크기가 N 이고 모든 값이 0인 1차원 리스트
n = 10
a = [0]*n
#뒤에서 n번째 a[-n]
#0부터 9까지 수 포함 리스트
array = [i for i in range(10)]
#0부터 19까지의 수 중에서 홀수만 포함
array = [i for i in range(20) if i % 2 == 1]
좋은 예시
# N X M 크기의 2차원 리스트 초기화
array = [[0]*m for _ in range(n)]
_ 반복을 수행하되 반복을 위한 변수의 값을 무시
append() 리스트에 원소 하나 삽입 O(1)
sort()기본 정렬 기능으로 오름차순 정렬
sort(reverse = True) 내림차순 정렬 O (NlogN)
reverse() 리스트의 원소를 모두 뒤집어 놓는다.O(N)
insert(삽입할 위치 인덱스, 삽입할 값) 특정한 인덱스 위치에 원소 삽입 O(N)
count(특정 값) 특정한 값을 가지는 데이터의 개수를 셀 때 사용 O(N)
remove(특정 값) 특정한 값을 갖는 원소를 제거하는데 값을 가진 원소가 여러 개면 하나만 제거한다.O(N)
튜플은 한 번 선언된 값을 변경할 수 없습니다.
() 이용 리스트에 비해 상대적으로 공간 효율적입니다. (적은양의 메모리 사용)
사용하면 좋은 경우
서로 다른 성질의 데이터를 묶어서 관리해야 할 때
-최단 경로 알고리즘에서는 (비용, 노드 번호)의 형태
데이터 나열을 해싱의 키 값으로 사용해야 할 때
-튜플은 변경이 불가능하므로 리스트와 다르게 키 값으로 사용될 수 있다.
리스트보다 메모리를 효율적으로 사용해야 할 때
사전 자료형은 키와 값의 쌍을 데이터로 가지는 자료형
변경 불가능한 자료형을 키로 사용할 수 있다.
파이썬의 사전 자료형은 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리 가능
키 데이터만 뽑아서 리스트 keys()
값 데이터만 뽑아서 리스트 values()
집합 자료형
중복 허용X 순서 X
리스트 혹은 문자열을 이용해서 초기화 가능
데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리 가능
data = set([1,1,2,3 ....])
data = {1,1,2,3,....}
| 합집합
& 교집합
- 차집합
새로운 원소 추가
add(4)
여러 개 추가
update([5,6])
특정한 값을 갖는 원소 삭제
remove(3)
리스트나 튜플은 순서가 있기 때문에 인덱싱을 통해 자료형의 값을 얻을 수 있지만 사전 자료형과 집합 자료형은 순서가 없기 대문에 인덱싱으로 값을 얻을 수 없습니다.
사전은 Key 혹은 집합의 Element 를 이용해 O(1) 의 시간 복잡도로 조회
input() 함수는 한 줄의 문자열을 입력 받는 함수
map() 함수는 리스트의 모든 원소에 각각 특정한 함수를 적용할 때 사용
n = int (input())
data = list(map(int, input().split()))
빠르게 입력 받기
sys.stdin.readline().rstrip()
print() 는 기본적으로 출력 이후 줄 바꿈 수행
줄 바꿈 원치 않는 경우 print(a, end=" ")
f-string
print(f"정답은~~{answer}") # str로 변경X 상관 없음
if ~ elif ~ else
pass #디버깅 과정에서 아무것도 처리하고 싶지 않을 때 사용
for 변수 in 리스트 :
range(시작, 끝 값 +1) # 인자를 1개만 넣으면 자동으로 시작 값은 0
다음 반복을 진행하고자 할 때 continue를 사용
def 함수명(매개변수):
소스코드
return 반환 값
파이썬에서 함수는 여러 개의 반환 값을 가질 수 있음
람다 표현식
어떠한 함수 자체를 입력으로 받는 또다른 함수가 존재할 때 유용,
단순히 한번 사용하고 마는 경우
print(sorted(array, key=lambda x:x[1]))
resule = map(lambda a, b: a+b, list1, list2)
itertools: 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능 제공 (순열과 조합 라이브러리)
heapq: 힙 자료구조를 제공
일반적으로 우선순위 큐 기능을 구현하기 위해 사용
bisect 이진 탐색 기능을 제공
collections: 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함
math: 필수적인 수학적 기능을 제공
팩토리얼, 제곱근, 최대공약수, 삼각함수 파이와 같은 상수 포함
sum,max,min,eval,sorted
itertools
permutations(data,3) #모든 순열 구하기
combinations(data,2)# 2개를 뽑는 모든 조합 구하기
product(data, repeat=2) #2개를 뽑는 모든 순열 구하기 (중복 허용)
combinations_with_replacement(data,2)# 2개를 뽑는 모든 조합 구하기(중복 허용)
collections
등장 횟수를 세는 기능 제공
counter = Counter(['', '' ,'' ...])
math
최소 공배수 lcm 최대공약수 gcd
counter['']
그리디 알고리즘
현재 상황에서 당장 좋은 것만 고르는 방법
알고리즘 문제를 풀기 위해 최소한의 아이디어를 떠올릴 수 있는 능력 요구
단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토
거스름 돈
가장 큰 화폐 단위부터 돈을 거슬러 주면 됨
N이 1이 될 때 까지
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
N에 대하여 최대한 많이 나누기
n, k = map(int, input().split())
result = 0
while True:
#N이 K로 나누어 떨어지는 수가 될 때 까지 빼기
target = (n // k) *k
result += (n - target)
#N이 K보다 작을 때 나눌 수 없을 때 반복문 탈출
if n < k:
break
#K로 나누기
result += 1
n //= k
#마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
곱하기 혹은 더하기
두 수중에 하나라도 0 혹은 1인 경우 곱하기 보다 더하기
data = input()
# 첫 번째 문자를 숫자로 변경하여 대입
result = int (data[0])
for i in range(1, len(data)):
#두 수 중에서 하나라도 0 1인 경우 더하기 수행
num = int(data[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)
모험가 길드
공포도 X인 모험가는 X명 이상 모험가 그룹에 참여
오름차순 정렬 후 현재 그룹 포함된 모험가의 수가 공포도 보다 크거나 같다면 그룹으로 설정
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0 # 총 그룹의 수
count = 0 #현재 그룹에 포함된 모험가의 수
for i in data: #공포도 낮은 것 부터 확인 그룹에 해당 모험가 포함
count += 1
if count >= i : # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면 그룹
result += 1 #총 그룹의 수 증가
count = 0 #현재 그룹 포함된 모험가 수 초기화
구현 문제
풀이를 떠올리는건 쉽지만 소스코드로 옮기기 어려운 문제
알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
실수 연산을 다루고 특정 소수점 자리까지 출력
문자열을 특정한 기중에 따라 끊어 처리해야 하는 문제
적절한 라이브러리 찾아서 사용
상하좌우
n = int(input())
x, y = 1, 1
plans = input().split()
dx = [0, 0, -1, 1]
dx = [-1, 1, 0 , 0]
move_types = ['L', 'R', 'U', 'D']
#이동 계획 하나씩 확인
for plan in plans:
#이동 후 좌표 구하기
for i in range(len(move_types)):
if plan == move_types[i]:
nx = x + dx[i]
ny = y + dy[i]
#공간을 벗어나는 경우 무시
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
#이동 수행
x, y = nx, ny
print(x, y)
완전 탐색 Brute Forcing
가능한 경우의 수를 모두 검사
h = int(input())
count = 0
for i in range(h+1):
for j in range(60):
for k in range(60):
#매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)
왕실의 나이트
#현재 나이트 위치 입력
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) -1
#나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
#8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
#이동하고자 하는 위치 확인
next_row = row + step[0]
next_column = column + step[1]
#해당 위치로 이동이 가능하다면 카운트 증가
if next_row >=1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)
문자열 재정렬
숫자(0 ~ 9), 수 100, 1000, 700 과 같은 정수
data = input()
result = []
value = 0
#문자를 하나씩 확인
for x in data:
if x.isalpha():
result.append(x)
else:
value += int(x)
#알파벳 오름차순 정렬
result.sort()
#숫자가 하나라도 존재하면 가장 뒤에 삽입
if value != 0:
result.append(str(value))
print('',join(result))
DFS/BFS 코딩 테스트에서 매우 자주 등장
python 에서 Queue를 사용할 때 deque 라이브러리 사용 (시간적으로 유리)
queue = deque()
queue.append(5) #삽입
queue.popleft() #삭제
재귀 함수 (Stack과 비슷 1 -> 100 100번째 재귀 종료 -> 1번쨰)
자기 자신을 다시 호출하는 함수 DFS를 실질적으로 구현할 때 사용
python에서 최대 재귀 깊이 제한이 있어서 오류 메시지가 출력
n! 구현 (0! == 1! = 1)
유클리드 호제법 최대공약수 계산
A, B (A> B) A를 B로 나눈 나머지 R
A와 B의 최대공약수는 B와 R의 최대공약수와 같다
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a%b)
재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
함수를 연속적으로 호출하면 메모리 내부의 스택 프레임에 쌓이기 때문에 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
DFS 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더 이상 2번의 과정을 수행할 수 없을 때 까지 반복
1 2 7 6 -> 인접 노드 없음 pop(6)
1 2 7 6 8 3 4 5
def dfs(graph, v, visited):
#현재 노드를 방문 처리
visited[v] = True
print(v, end=' ')
#현재 노드와 연결된 다른 노드를 재귀적으로 방문
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
# 각 노드가 방문된 정보를 표현 (1차원 리스트)
visited = [False]*9
#정의된 dfs 함수 호출
dfs(graph, 1, visited)
BFS 너비 우선 탐색 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐 자료구조를 이용
1.탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리
3. 더이상 2번의 과정을 수행할 수 없을 때 까지 반복
큐에 1 삽입 -> 1을 꺼내 방문하지 않은 노드 인접 2 3 8 큐에 넣고 방문 처리 -> 2를 꺼내 7 삽입 -> 3을 꺼내 4 5 방문 처리 -> 8 꺼냄 인접노드가 없으면 무시 ->
1 2 3 8 7 4 5 6
from collections import deque
def bfs(graph, start, visited):
#큐 구현을 위해 deque 라이브러리 사용
queue = deque([start])
#현재 노드를 방문 처리
visited[start] = True
#큐가 빌 때 까지 반복
while queue:
#큐에서 하나의 원소를 뽑아 출력
v = queue.popleft()
print(v, end=' ')
#아직 방문하지 않은 인접한 원소들을 큐에 삽입
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
음료수 얼려 먹기
구멍이 뚫려 있는 부분은 0, 간막이 존재하는 부분은 1
구멍이 뚫려 있는 부분끼리 연결되어 있는 것으로 간주
4 5
00110
00011
11111
00000
DFS, BFS로 해결할 수 있음
연결되어 있다 = 인접한 노드로 표현
DFS 활용
1 특정 지점의 상하좌우 살펴본 뒤 주변 지점 중 값이 0 이면서 아직 방문하지 않은 지점이 있으면 방문
2. 방문한 지점에서 연결된 모든 지점을 방문
3. 1~2번 과정을 반복하여 방문하지 않은 지점의 수 카운트
#DFS로 특정 노드를 방문하고 연결된 모든 노드들도 방문
def dfs(x, y):
# 주어진 범위를 벗어나는 경우에는 즉시 종료
if x<= -1 or x>=n or y<=-1 or y >=m:
return False
#현재 노드를 아직 방문처리 않았다면
if graph[x][y] == 0:
#해당 노드를 방문 처리
graph[x][y] = 1
#상 하 좌 우 위치들 재귀적으로 호출
dfs(x-1, y)
dfs(x, y-1)
dfs(x+1, y)
dfs(x, y+1)
return True
returnFalse
#N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
#2차원 리스트의 맵 정보 입력 받기
graph = []
for i in range(n):
graph.append(list(map(int, input())))
#모든 노드(위치)에 대하여 음료수 채우기
result = 0
for i in range(n):
for j in range(m):
#현재 위치에서 DFS 수행
if dfs(i,j) == True:
result +=1
print(result)
미로탈출
BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색
-따라서 1,1 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.
최단 경로의 값들이 1씩 증가하는 형태
#BFS 소스코드 구현
def bfs(x, y):
queue = deque()
queue.append((x, y))
#큐가 빌 때 까지 반복
while queue:
x, y = queue.popleft()
#현재 위치에서 4가지 방향으로의 위치 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
#미로 찾기 공간을 벗어난 경우 무시
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
#벽인 경우 무시
if graph[nx][ny] == 0:
continue
#해당 노드를 처음 방문하는 경우에만 최단 거리 기록
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
#가장 오른쪽 아래까지의 최단 거리 반환
return graph[n-1][m -1]
#이동할 네 가지 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
#BFS를 수행한 결과 출력
print(bfs(0, 0))