본문 바로가기

programming study/Algorithm

 (275)
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (31)(2021.2.24) 본 내용은 해당 강의 토대로 작성 1. 플로이드 워샬 알고리즘 문제 해설 각 정점에서 각 정점으로의 최소 비용 2차원 리스트 다이나믹 프로그래밍 냅색 알고리즘 dis[ i ] [ j ]: i노드에서 j노드로 가는데 드는 최소 비용 i: 출발점 j: 도착점 i에서 j로 갈 때의 경우의 수 이 중에서 최소비용을 찾기 최솟값을 찾기 dis[ i ] [ j ] dis[ i ] [ k ] + dis[ k ] [ j ] k: 중간 경유지 , for문으로 접근할 것 비용이 제일 최소가 되는 순열로 이루어지게 된다. 문제 답안 if __name__ == "__main__": n, m = map(int, input().split()); # 정점, 간선 개수 dis =[[5000] * (n + 1) for _ in ran..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (30)(2021.2.23) 본 내용은 해당 강의 토대로 작성 1. 가방문제 (냅색 알고리즘) 문제 해설 다이나믹 프로그래밍 dy: 0으로 초기화한 배열 만들기 dy[ j ]: 가방에 j라는 무게까지 담을 수 있을 때 가방에 담을 수 있는 보석들의 최대 가치 보석이 한 종류만 있다는 가정하에 dy 테이블 기록하기 w: 보석의 무게, v: 보석의 가치 dy[ j ] = dy[j - w] + v dy[ j ] 에 값이 있으면 넣을 값과 비교하여 그 중 최댓값을 넣는다. 문제 풀이 n, L = map(int, input().split()); # 보석의 종류, 가방 무게 한도 dy = [0] * (L + 1); # 각 인덱스 기준 보석의 최대 가치 for _ in range(n): w, v = map(int, input().split())..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (29)(2021.2.22) 본 내용은 해당 강의 토대로 작성 1. 알리바바와 40인의 도둑(Bottom-Up) 문제 해설 최단거리로 가기위해서는 오른쪽, 아래로 움직인다. 별도의 dy 2차원 리스트 만들기 출발지에서 각 지점까지 가는데 드는 최소 비용 0행과 0열의 dy 값은 누적되어 가는 값이다. 문제 풀이 n = int(input()); a = [list(map(int, input().split())) for _ in range(n)]; dy = [[0]*n for _ in range(n)]; # 각 지점에서의 최소 비용 dy[0][0] = a[0][0]; # 시작점 for i in range(1 , n): # dy의 0행, 0열 초기화 dy[0][i] = a[0][i] + dy[0][i - 1]; dy[i][0] = a[i]..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (28)(2021.2.21) https://www.inflearn.com/course/파이썬-알고리즘-문제풀이-코딩테스트/dashboard 파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 파이썬을 이용한 코딩테스트 문제풀이를 합니다. 초급 프로그래밍 언어 알고리즘 자료구조 Python 코딩 테스트 온라인 강의 코딩테스트 문제풀이 강의, 자료구조와 알고리즘,기업 코딩테스트, 파 www.inflearn.com 동적계획법 Dynamic Programming 크고 복잡한 문제를 다룰 때 문제를 직관적인 작은 단위로 바꾸어 해를 구한다. 그 후, 조금 더 큰 문제로 확장하여 구한 해를 이용하여 조금 더 큰 문제의 해를 구한다. 이 구한 작은 단위들의 해들은 따로 기록한다(메모이제이션) 이를 반복하여 주어진 문제의 점화식을 도출해서 답..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (27)(2021.2.20) 본 내용은 해당 강의 토대로 작성 정렬 1. 병합 정렬 분할 정복 배열의 중간지점을 나누어 더이상 영역을 나눌 수 없을 때까지 재귀함수 호출 두 원소의 대소를 비교 후 임시의 공간에 원소를 넣으며 진행 후회순회 병합 정렬 알고리즘 def Dsort(lt, rt): # 왼쪽부터 오른쪽 if lt < rt: mid = (lt + rt) // 2; # 중간 Dsort(lt, mid); # 왼쪽 Dsort(mid + 1, rt); # 오른쪽 p1 = lt; # 정렬 시작 p2 = mid + 1; tmp = []; while p1
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (26)(2021.2.19) 본 내용은 해당 강의 토대로 작성 1. 토마토 (BFS) 문제 해설 토마토의 정보가 있는 2차원 배열(board), 익는데에 며칠 걸리는지 정보를 적는 2차원 배열(dis)을 만든다. dis는 0으로 초기화 board를 탐색하며 익은 토마토 정보를 큐에 넣기 상하좌우 탐색 익게된 토마토의 날짜를 기록 익게된 토마토를 큐에 넣기 문제 답안 from collections import deque dx = [-1, 0, 1, 0]; dy = [0, 1, 0, -1]; n, m = map(int, input().split()); board = [list(map(int, input().split())) for _ in range(m)]; # 토마토 Q = deque(); # 큐 자료구조 dis = [[0]*n fo..
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (25)(2021.2.18) 본 내용은 해당 강의 토대로 작성 1. 미로탐색(DFS) 문제 해설 방법의 수를 구하는 것에 유의 -> DFS 지나온 길은 재방문하지 않는다. 경로를 탐색 후 지나온 길의 체크를 풀 것 문제 답안 dx = [-1, 0, 1, 0]; # 방향 dy = [0, 1, 0, -1]; def DFS(x, y): global cnt; if x == 6 and y == 6: # 도착지점 cnt += 1; else: for i in range(4): xx = x + dx[i]; # 갈 곳 yy = y + dy[i]; if 0
[인프런 - 김태원] 파이썬 알고리즘 문제풀이 (코딩테스트 대비) (24)(2021.2.17) 본 내용은 해당 강의 토대로 작성 1. 동전 분배하기(DFS) 문제 해설 상태 트리 각 동전을 누구에게 주는지 정하기 각 사람의 동전 금액을 기록하는 리스트 만들기 문제 답안 def DFS(L): global res; if L == n: # 종료 지점 cha = max(money) - min(money); # 최댓값과 최솟값의 차 if cha < res: tmp = set() # set 자료구조 for x in money: tmp.add(x); if len(tmp) == 3: # 서로 다 다른 금액 res = cha; else: for i in range(3): money[i] += coin[L]; # 더하기 DFS(L + 1); money[i] -= coin[L]; # 빠져왔을 때 다시 빼기 if __..

티스토리툴바