세리프 따라잡기

플로이드 워셜(Floyd-Warshall)이란? -모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 -플로이드 워설 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행 →다만 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정이 필요X -플로이드 워셜은 2차원 테이블에 최단 거리 정보 저장 -다이나믹 프로그래밍 유형에 속한다. 노드의 개수가 적은 상태에서 효과적으로 사용하고, 노드의 개수와 간선이 많은 경우는 다익스트라를 더 많이 사용한다. 점화식 : 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인 → a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사 # 점화식에 따라 플로이드 워셜 알고리즘을 수..

다익스트라(Dijkstra) 알고리즘이란? 1. 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 2. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. [but, 음수일 땐 사용 불가능] 3. 다익스트라는 다이나믹 프로그래밍 or 그리디 알고리즘으로 분류되기도 한다. = 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다. [작은 문제가 큰 문제에 속해있는 다이나믹 유형] 4. 기본적으로 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용 5. 다익스트라는 정렬 사용 - 정렬 이후에 가장 적은 것을 하나씩 선택하는 게 알고리즘에 포함 [그리디 알고리즘] 다익스트라 작동 과정 1. 출발 노드를 설정 2. 출발 노드를 기준으로 각 노드의 최소 ..

DFS 기본 구현 1. 시작 노드에서 방문하지 않았으면 노드를 삽입해준다 == 방문 표시 2. 더 이상 방문이 불가능하다면, 탐색 중단하고 이전으로 돌아옴 *특징 1. 스택 or 재귀함수 사용 2. 한 방향으로 깊게 탐색 3. 깊이 제한 횟수를 늘려주자! sys.setrecursionlimit(10**8) #깊이 제한 def dfs(arr, cur, visited): visited[cur] = True for i in arr[cur]: if not visited[i]: dfs(arr, cur, visited) # 나는 dfs(arr, cur, visited) 부분을 defaultdict를 이용해 graph에 담아서 사용 def dfs(v): visited[v]=1 print(v,end=' ') for i..

최소 신장(스패닝) 트리 (minimum spanning tree) = 전체 요소들을 연결할 때 사용한다. kruskal 알고리즘, prim 알고리즘이 있다. 스패닝 트리란? - 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 조건? - 본래의 그래프의 모든 노드를 포함해야 함 - 모든 노드가 서로 연결 - 트리의 속성을 만족시킴(사이클이 존재하지 않음) ☞ 사이클이란? 그래프가 서로 연결되어 사이클을 형성하는 경우. 최소 비용 스패닝 트리에서는 사이클이 발생하면 안 된다! 애초에 모든 노드를 이어붙이기만 하면 되는데 사이클이 발생할 이유가 없다고 한다! ==> 이러면 안됩니다~ 크루스칼 kruskal 1. 간선들을 정렬 2. 간선이 잇는 두 정점의 root 찾기 3. 다르면..

알고리즘 스피드는 완료까지 걸리는 절차의 수로 결정이 된다. → 따라서 같은 작업을 수행하는데 5단계만 수행하면 되는 알고리즘이 10단계를 수행하는 알고리즘보다 좋은 알고리즘이다. 1. 상수 시간(constant time) ex. 선형 탐색 알고리즘은 1개씩 차례대로 다 검사를 해보는데, 만약 데이터가 무수히 많다면...........? 무수히 많은 단계를 거쳐야 한다~ [ n=input()이라면 n단계를 거쳐야 함 ] → 선형 탐색은 O(N)의 시간 복잡도를 가짐 빠르다/느리다 라고 표현하는 것보다 더 직관적으로 빠르게 설명할 수 있다 == BigO BigO를 이해한다면? = 알고리즘 분석을 더 빠르게 할 수 있고, 언제 무엇을 쓸지 파악이 가능하며, 자신의 코드를 평가할 수 있다. (이 코드가 미래에..

- 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다. - 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex. 어떤 물건 데이터를 자료구조에 넣었다가 가치가 높을 물건부터 꺼내서 확인해야 하는 경우, 우선순위 큐에 각각의 물건 정보를 가치 데이터와 함께 우선순위 큐에 넣었다가 꺼낼 때 자료구조 추출되는 데이터 스택 (stack) 가장 나중에 삽입된 데이터 큐 (queue) 가장 먼저 삽입된 데이터 우선순위 큐 (priority queue) 가장 우선순위가 높은 데이터 - 우선순위 큐를 구현하는 방법 1. 단순히 리스트를 이용해 구현 = 리스트에 차례대로 데이터를 연달아 넣고, 꺼낼 때는 리스트에서 각각의 데이터를 확인한 다음에 값이 가장 큰 데이터를 뽑아 추출..

'스택' 자료구조는 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출-먼저 입력되는 데이터가 나중에 출력된다)의 자료구조이다. → 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. - 대표적 예시: 박스 쌓기 = 여러 개의 박스를 쌓아야할 때(스택하고자 할 때) 아래쪽에서부터 박스를 차례대로 올려놓는다. 쌓아놓은 박스를 다시 내리고자 할 때는 가장 위쪽에 있는 박스부터 차례대로 내리게 된다. 스택 자료구조 기억은 박스 쌓기 예시로 기억하면 좋다!! 다양한 알고리즘에서 사용되기에, 스택 자료구조의 동작 방법과 사용 방법에 대해 꼭 알아야 한다! - 스택 자료구조는 삽입과 삭제 두 연산으로 구성된다. 삽입 과정이 차례대로 쌓이다, 삭제 연산을 만나면 가장 마지막에 들어왔던 7이 우선적으로 나가게 된다..

분할정복법 (Divide & Conquer): 큰 문제를 작은 문제로 분할해 재귀적으로 해결 ☞ 간단히, 큰 문제 보다는 작은 문제를 해결하기 쉬우니까~ base case: 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않아도 바로 답을 알 수 있는 경우 recursive case: 문제가 커서 바로 답을 알 수 없어서, 같은 형태의 부분 문제들로 쪼개서 풀어야 하는 경우 간단 예제(맛보기) ex. Q. 1~8까지의 합을 구하라 [recursive case라고 생각하며 풀어보기] → 과정 1. 1-4 와 5-8로 쪼개서 구해보자. //그래도 너무 크다? 2. 1-4범위를 1-2와 3-4로 또 쪼개서 구해봄 //근데도 아직 큰거야.. 3. 1-2범위를 1과 2로 쪼개서 구해본다! // 1에서 1..

순차 탐색: 리스트 안에 있는 특정한 데이터 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 [별다른 말이 없다면 기본적으로 이 방법으로 탐색] 이진 탐색: 정렬되어 있는 리스트에서 (만족한다면) 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 -> 탐색 범위를 정해줘야함. 시작점, 끝점, 중간점. ex. step1 중간점 선정은 중간점index값에서 소수점 이하는 제거다. 우리가 찾는 값이 4일 때, 중간점 보다 왼쪽에 있으므로, 중간점~끝점까지는 볼 필요가 X 따라서 끝점을 중간점보다 한 칸 왼쪽으로 다시 재지정해준다. step2 끝점의 위치 조정으로 인한 중간점 재지정에 들어감. 이번에도 찾고자 한 값이 중간점보다 오른쪽에 있으므로 시작점~중간점은 볼 필요X 따라서 시작점을 중간점보다 한 칸..

과거에 대한 성찰 월요일부터 입소했으니, 오늘로 정글러가 된 지 6일 차다. 일단 지금까지도 한편으로 꾸준히 드는 생각은 '나 여기 어떻게 왔지?'가 떨쳐지질 않는다. 다들 기본적으로 할 줄 아는 사람들이 왔기 때문이다. 이제와 보니 나는 몰입을 전혀 안 했던 것 같다. 그렇지 않고서야.. 이렇게까지 모든 게 새롭고 내 마음대로 술술 풀리는 게 정말 쉬운 것 밖에 없지 않을 테니😣 처음에 입소할 때만 해도 후기에서 본 이전 기수분들처럼 글도 열심히 쓰면서 해보자! 이랬는데, 막상 한 치 앞도 모를 숲 속에 들어와 보니 바깥일은 다 모르겠고 당장 하루 식량(?) 구하기 바쁘다. 그마저도 강의실에 새벽까지 남아서 매달려야 겨우겨우 끝내고 있다. 왜 전 기수분들이 '알고리즘 공부는 하고 오라.'라고 했는지, ..