| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 14 | 15 | 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 | 26 | 27 |
| 28 | 29 | 30 |
- 리액트
- 알고리즘
- merge request
- GitLab
- git remove
- 파이썬
- 엘리스 AI 트랙
- insert
- 리눅스
- PYTHON
- mongodb
- K-Digital training
- 백준 알고리즘
- join
- 트럼프 대통령 트윗 분석하기
- delete
- KDT
- 엘리스
- update
- Effect Hook
- 엘리스AI트랙
- 영어 단어 모음 분석하기
- linux
- 자료구조
- openapi
- pandas
- State Hook
- flask연동
- Git
- sql
- Today
- Total
GO WILD, SPEAK LOUD, THINK HARD
엘리스 AI 트랙 11주차 - 알고리즘의 정석 II (3/14) 🔥 본문
✔ 11주차. 자료구조와 알고리즘
<학습 목표>
- 개발 역량 강화를 위한 자료구조 및 알고리즘 문제를 수행할 수 있습니다.
- 알고리즘 문제를 만났을 때 효율적으로 접근하는 방법을 알 수 있습니다.
- 알고리즘 문제 해결 기법의 근복적인 이해를 할 수 있습니다.
[01 동적 계획법 기초]
1. 동적계획법 기초
- 피보나치 수열
- 재귀를 이용한 피보나치 수열
def fibo(n):
if n < 3:
return 1
else:
return fibo(n-1) + fibo(n-2) - 동적계획법 : 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법. (하위 문제의 답을 저장하여 중복 연산X, 하위 문제의 수만큼 저장공간 필요)
fibonacci = {1: 1, 2: 1}
def fibo(n):
if n in fibonacci:
return fibonacci[n]
else:
fibonacci[n] = fibo(n-1) + fibo(n-2)
return fibonacci[n] - 동적계획법 문제의 특성
① 중복되는 부분문제 (overlapping subproblems) : 작은 하위문제들이 중복되어 나타난다.
② 최적 부분 구조 (optimal substructure) : 최적해는 부분 문제의 최적해로부터 구할 수 있다.
- 점화식 : 복잡한 문제를 작은 하위문제로 표현한 식. Top-down / Bottom-up
예) f(n) = f(n-1) + f(n-2)
① 구하고자 하는 값이 무엇인지 정의한다
f(n): n번째 피보나치 수열
② 구하고자 하는 값을 부분문제들로 표현한다
피보나치 수열의 n번째 항은 n-1항과 n-2항의 합이다.
f(n) = f(n-1)+f(n-2)
- Top-down : 큰 문제 → 작은 문제 나누고 작은 문제를 풀어 return
- Bottom-up : 작은문제부터 차레대로 풀어서 적고, 크기를 늘려서 문제를 해결
# Top-down
fibonacci = {1: 1, 2: 1}
def fibo(n):
if n in fibonacci:
return fibonacci[n]
else:
fibonacci[n] = fibo(n-1) + fibo(n-2)
return fibonacci[n]
# Bottom-up
def fibo(n):
fibonacci = [-1, 1, 1]
if n < 3: return 1
for i in range(3, n+1):
fibonacci.append(
fibonacci[i-1] + fibonacci[i-2])
return fibonacci[n] - 동적계획법 문제풀이 방법
① 구하고자 하는 값 정의하기 : 구하고자 하는 값이 무엇인지 정의한다
② 부분문제로 표현하여 점화식 구하기 : 구하고자 하는 값을 부분문제로 구성된 식으로 표현한다
③ 코드로 옮기기 : 점화식을 재귀호출, 반복문 식으로 코드로 작성한다
2. 타일 채우기
- 문제 : 2xN짜리 액자에 2x1크기의 타일을 채워 넣으려고 한다. 해당 액자와 타일로 만들 수 있는 서로 다른 타일작품의 수는 몇 개인가?
# Top-down
def T(n):
if n == 0 or n == 1: return 1
if n in memo: return memo[n]
else:
memo[n] = T(n-1) + T(n-2)
return memo[n]
# Bottom-up
T = [1, 1]
for i in range(2, n+1):
T.append(T[i-1] + T[i-2])3. 숫자 만들기
- 문제 : 1부터 M까지의 숫자를 사용하여 합이 N이 되도록 만드는 경우의 수는? (1,000,000,007로 나눈 나머지를 반환하는 함수)
def makeNumber(n, m) :
result = [1]
for i in range(1, n + 1):
sum_temp = 0
for j in range(1, min(i, m) + 1):
sum_temp += result[i-j]
result.append(sum_temp % 1000000007)
return result[n];4. 연속 부분 최대합
- 문제 : 상훈이는 점심엔 늘 짜장, 짬뽕, 볶음밥 셋 중 하나를 먹는다. 하지만 거기엔 규칙이 하나 있는데, 전날 먹은 음식은 먹지 않는다는 것이다. 예를 들어 어제 짜장면을 먹었으면, 오늘은 짬뽕이나 볶음밥 중 하나를 먹어야 하는 것이다. 짜장, 짬뽕, 볶음밥 선호도는 그날그날 다른데, 매일 선호도가 주어질 때, 적절히 날마나 음식을 결정하여 총선호도의 최대값을 구하시오.
def eating(data) :
days = len(data)
d = [[0] * 3 for i in range(days + 1)]
for i in range(1, days + 1):
for j in range(3):
for k in range(3):
if j == k: continue
d[i][j] = max(d[i][j], d[i-1][k])
d[i][j] += data[i-1][j]
return max(d[days][i] for i in range(3))[02 동적계획법 심화]
1. 최대이익 통나무 자르기
- 길이 N짜리의 통나무를 다양한 길이로 조각 내고 싶습니다. 각 조각의 길이에 따라 판매 시 특정 가격으로 팔 수 있습니다. 길이 N의 통나무를 잘라 볼 수 있는 최대 이익을 구하세요.
def cutRod(N, myData) :
Table = [0 for i in range(N+1)]
for n in range(N+1):
for l, p in myData.items():
if n >= l:
Table[n] = max(Table[n], p + Table[n - l])
return Table[N]2. 최대길이 공통 부분 문자열 구하기
- 두개의 문자열에서 공통인 부분문자열의 최대길이를 구하시오. (예. ADGEBCD 와 TGEABDC는 공통으로 GEBD를 최대길이 부분 문자열로
가지고 있으므로 정답은 4임)
def LCS(s1, s2) :
m = len(s1)
n = len(s2)
L = [[None] * (n + 1) for i in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0 or j == 0:
L[i][j] = 0
elif s1[i-1] == s2[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]3. 최장증가수열 구하기
- 수열이 list로 주어질 때, 최장 증가 부분 수열의 길이를 반환하는 함수를 작성하세요.
def LIS(myData) :
L = [0] * len(myData)
for n in range(len(myData)):
for i in range(n):
if myData[i] < myData[n]:
L[n] = max(L[n], L[i]+1)
return max(L) + 1
4. 펠린드롬 만들기
- 문자열 data가 주어질 때, 이를 팰린드롬으로 만들기 위해 제거해야 하는 문자 개수의 최솟값을 반환하는 함수를 작성하세요.
def palindrome(data) :
n = len(data)
p = [[0] * n for i in range(n)]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if data[i] == data[j]:
p[i][j] = p[i+1][j-1]
else:
p[i][j] = min(p[i+1][j], p[i][j-1]) + 1
return p[0][len(data)-1][03 그래프 알고리즘]
1. 그래프의 개념
- 그래프 : 정점과 간선으로 이루어진 자료구조로 정점간의 관계를 조직도로 표현
- 정점 : 여러가지 특성을 가질 수 있는 객체
- 간선 : 정점들 간의 관계
- 그래프의 종류
① 무방향 그래프 : 정점간 간선에 방향이 없는 그래프
② 방향그래프 : 정점간 간선에 방향이 있는 그래프
- 그래프의 특징
① 자기 자신을 향하는 간선은 없음
② 중복된 간선 허용X
2. 그래프의 표현
① 인접행렬 - 무방향그래프
- 인접 행렬은 V x V 크기의 2차원 배열임. (V는 그래프의 정점 수)
- 0과 1 사이에 간선이 있을 경우, [0, 1] 과 [1, 0] 에 1을 표시
- 2번 방법으로 전체 행렬을 채워주면 그래프를 행렬로 표현할 수 있음
→ 인접한 정점들을 행렬로 표현한 것을 '인접행렬'이라고 부름
→ 가중치가 있을 경우, 똑같은 방식으로 채우지만 1 대신 해당 간선의 가중치를 채워줘야 함
📌 무방향 그래프를 인접행렬로 표현했을 때 특징 : 대각선을 기준으로 대칭을 이룸
② 인접행렬 - 방향그래프
- 방향 그래프는 한쪽 정점에서 다른 쪽 정점으로 방향이 존재하기 때문에 행을 시작 정점, 열을 도착 정점으로 지정
- V1 에서 V2로 연결된 간선은 [1,2] 만 적어주고 반대는 적지X
- 가중치가 있는 경우도 똑같이 표시
- 파이썬에서는 dict 자료형으로 표시 가능함
📌 참고 : ceadserv1.nku.edu/longa//classes/mat385_resources/docs/matrix.html
③ 인접리스트 - 무방향 그래프
- 각 정점마다 자신이 연결되어 있는 정점을 나타내는 연결리스트를 가지고 있음
- HEADER 는 각 시작정점의 번호를 나타냄, HEADER 정점과 연결되어 있는 정점들을 인접 리스트로 모두 연결
📌 인접리스트 방식의 특징 : HEADER에 적힌 정점과 연결되어 있는 정점들을 모두 나열
④ 인접리스트 - 방향 그래프
- 방향 그래프도 동일한 방식임. HEADER를 시작점으로 도착하는 정점들만 적어줌
- 예) 4번 정점은 다른 방향으로 가는 간선이 없으므로 연결리스트X
3. 너비우선탐색 (BFS)
- 너비우선탐색 : 부모를 공유하는 인접 노드들을 우선적으로 탐색
① 탐색을 시작할 0을 QUEUE 에 넣어 탐색을 시작
② Queue에서 0정점을 빼고 0정점과 연결되어 있는 모든 정점을 QUEUE에 넣어줌
③ Queue 에서 다시 1을 빼고 1과 연결되어 있고 방문한 적 없는 정점을 queue에 넣어줌
④ 다시 queue에서 2를 빼고 연결되어 있지만 방문한 적 없는 정점 4를 넣어줌
⑤ 3 정점 방문 후 queue에서 3을 빼고 마지막으로 4를 방문하면 탐색 완료
4. 깊이우선탐색 (DFS)
- 깊이우선탐색 : 다음 분기로 넘어가기 전에 해당 분기를 우선적으로 탐색하는 방법
① 깊이우선탐색은 stack을 사용해서 구현. 정점 0을 stack에 넣어줌 (stack에 넣는 순서가 탐색순서임)
② 0을 빼고 0과 연결된 정점인 1, 2, 3을 stack에 넣어줌
③ 처음 만나는 정점인 1를 뺌
④ 1과 연결된 2를 빼고 2와 연결된 4를 넣어줌
⑤ 4에서 더이상 탐색할 정점이 없기때문에 0으로 돌아감
⑥ 0과 연결된 3을 탐색하면 탐색완료
5. 디지털 세계 토지조사
- 네모 모양 행성에 1로 되어있는 육지와 0으로 되어있는 바다가 있다. 육지의 좌, 우, 상, 하가 모두 연결되어 있다면 섬이라고 한다. 섬의 개수를 구하시오.
isize = 0
def dfs(x, y, pMap, visited):
global isize
visited[x][y] = 1
di = [(1, 0), (0, 1), (-1, 0), (0, -1)]
n = len(pMap)
for d in di:
nx = x + d[0]
ny = y + d[1]
if nx < 0 or ny < 0 or nx > n-1 or ny > n-1 : continue
if pMap[nx][ny] == 0: continue
if not visited[nx][ny]:
isize += 1
dfs(nx, ny, pMap, visited)
def cadastralSurvey(pMap):
global isize
num_island = 0
n = len(pMap)
visited = []
for i in range(n):
visited.append ([0 for j in range(n)])
islands_size = []
for i in range(n):
for j in range(n):
if pMap[i][j] == 1 and visited[i][j] == 0:
num_island += 1
isize = 1
dfs(i, j, pMap, visited)
islands_size.append(isize)
islands_size.sort()
return num_island, islands_size6. 촌수 계산하기
- 새로운 SNS 서비스 엘리스친구는 두 명의 사용자 간의 거리를 촌수로 표시한다. 직접연결이 되어있는 친구라면 1촌, N명의 친구를 거쳐 연결되어있다면 N+1촌으로 표시한다. 두 사용자 간의 촌수를 구하시오.
import sys
from collections import deque
sys.setrecursionlimit(100000)
def SNS(n_nodes, myInput, a, b):
if a == b : return 0
graph = [[] for i in range(n_nodes)]
m_edge = len(myInput)
for line in myInput:
graph[line[0]].append(line[1])
graph[line[1]].append(line[0])
queue = deque([a])
visit = [0] * n_nodes
visit[a] = 1
while queue:
cur = queue.popleft()
for node in graph[cur]:
if visit[node] == 0:
visit[node] = visit[cur]+1
queue.append(node)
return visit[b]-1 if visit[b] > 0 else -1[04 그래프 알고리즘 심화]
1. 그래프 알고리즘
- 최단거리 알고리즘 : 그래프의 한 정점에서 다른정점으로 가는 최단거리를 계산하는 알고리즘
- 최소신장트리 : 주어진 그래프에서 최소비용으로 트리를 만드는 것. 최소신장트리는 그래프내 모든 정점을 연결하고 있는 트리로 간선의 가중치는 최소가 되어야 됨
2. 최단거리 알고리즘 - 다익스트라
- 다익스트라 (Dijkstra’s Algorithm) : 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘
- 다익스트라는 가중치가 음수인 경우에 사용할 수 X, 이 경우외에는 가장 가중치가 낮은 간선과 연결된 정점들을 먼저 방문하기 때문에 항상 정점을 처음 방문할 때의 거리가 각 정점의 최단거리임
📌 도저히 이해가 안감....... 참고1, 참고2
3. 최단거리 알고리즘 - 벨만포드
- 벨만포드 (Bellman–Ford algorithm) : 하나의 정점에서 다른 모든 정점까지의 최단경로를 구하는 알고리즘, 음수 가중치 사용 가능
- 벨만포드는 모든 간선에 대해 계산하기 때문에 중복방문 하는 경우도 있음(정점개수가 V개 일때 V번 반복함)
📌 역시 이해 못함..... 참고
4. 최소신장트리 - 크루스칼
- 크루스칼 (Kruskal's algorithm) : 짧은 간선부터 골라 그래프에 포함시키는 방법. 분리되어 있는 트리도 통합함. 우선순위큐 사용.
- 크루스칼은 간선을 정렬해 짧은 간선부터 고려하고, 트리에는 사이클이 없기 때문에 간선 포함시에는 사이클이 되는 경우라면 건너뜀
- Union Find : 임의의 노드를 포함하는 트리 A와 트리 B가 동일한 트리인지 찾고 (Find) 두 트리를 한트리로 통합하는 과정 (Union)
① 가중치 그래프에서 시작
② 가장 짧은 간선부터 골라서 그래프에 포함 (여기서는 2부터)
③ 그 다음 짧은 3을 선택
④ 3을 모두 고르면 사이클이 되기 때문에 2개만 고름 (사이클이 생기면 넘어감)
⑤ 트리 완성
📌 꼭 다시 한번 읽어보기!!!! 참고
5. 최소신장트리 - 프림
- 프림 (Prim's Algorithm) : 작은 트리에서 연결되어있는 간선들을 하나씩 확장해 트리를 만듦. 처음부터 끝까지 트리 형태 유지. 우선순위큐 사용
- 프림은 현재 만들어진 트리와 연결되어 있는 가장 작은 가중치의 간선을 찾는 것이 핵심임
① 시작점을 선택 (여기서는 C)
② 가장 작은 가중치의 간선을 선택
③ 연결되지 않은 가장 가까운 정점을 선택
④ 그다음 작은 가중치를 선택
⑤ 프림 완성
알고리즘 진짜 너무 어렵다... 솔직히 수업의 반도 이해 못한 느낌임.....
※ 수업 자료의 출처는 K-Digital Training x 엘리스 인공지능 서비스 개발 기획 1기 (elice.io/)입니다.
'개발 > 엘리스 AI 트랙' 카테고리의 다른 글
| 엘리스 AI 트랙 12주차 - 파이썬으로 시작하는 데이터 분석 II (3/18)🔥 (0) | 2021.03.27 |
|---|---|
| 엘리스 AI 트랙 12주차 - 파이썬으로 시작하는 데이터 분석 I (3/17)🔥 (0) | 2021.03.26 |
| 엘리스 AI 트랙 11주차 - 알고리즘의 정석 I (3/12) 🔥 (0) | 2021.03.15 |
| 엘리스 AI 트랙 11주차 - 알고리즘을 위한 자료구조 (3/10) 🔥 (0) | 2021.03.14 |
| 엘리스 AI 트랙 08주차 - OpenAPI 심화 (2/20)🔥 (0) | 2021.02.21 |
