lgvv98

크루스칼 알고리즘과 위상정렬 백준 알고리즘: 최소 스패닝 트리에서 연습할 수 있습니다. ✅ 서로소 집합 6개의 노드가 주어지는데 각 연결 관계는 6 4 1 4 2 3 2 4 5 6 으로 주어집니다. 여기서 각 노드를 비교하고, 노드 번호의 부모를 업데이트 하면서 결국은 사이클이 형성되는지 찾을 수 있습니다. 하지만 이 경우 시간 복잡도에 큰 손해가 발생하는데, 이를 단축시키고자 경로 압축 기법을 사용하곤 합니다. * 경로 압축 기법이란? - find 함수를 재귀적으로 호출하여 부모 테이블 값을 갱신하는 방법입니다. 오늘 주로 알아 볼 내용은 크루스칼 알고리즘이므로 서로소 집합에 대한 내용은 아래 포스팅을 참고해주세요! https://velog.io/@syc1013/%EC%95%8C%EA%B3%A0%EB%..

플로이드 워셜 알고리즘 ✅ 플로이드 워셜 알고리즘 이번 알고리즘 코드는 나동빈 책을 기반으로 공부하고, swift로 제 이해를 바탕으로 직접 코드를 작성하였습니다. 따라서 성능 및 코드 검증이 완벽하지 않아서 오류가 있을 수도 있습니다. 오류가 있다면 댓글로 제보해주세요! 다익스트라 : 한 지점에서 다른 특정 지점까지 - 그리디에 속함 플로이드 워셜 : 모든 지점에서 다른 모든 지점까지 - dp에 속함 시간복잡도는 O(N^3)이다. ✅ 코드 import Foundation /// 정점간의 연결관계, 가중값, 정점의 개수 func FloydWarshall(graph: [[Int]], weight: [Int], n: Int) -> [[Int]] { var node = [[Int]](repeating: [In..

Dijkstra 알고리즘 ✅ Dijkstra 알고리즘을 구현해보자. 이번 포스팅에서는 스위프트 데이터 구조와 알고리즘 책과 나동빈 파이썬 알고리즘 책 그리고 다른 분의 포스팅을 참고하여 작성하였음. 이거 예전에 손을 풀때는 참 이해도 쉽고 그랬는데, 알고리즘 공부 놓고 다시 시작하려니까 어려웠음. 근데 그냥 상당히 집중이 안되는 시기인 것 같다. 아래의 그래프를 다익스트라 알고리즘을 손으로 분석해보자. 나동빈 책에 따르면 다익스트라 알고리즘과 플로이드 워셜 알고리즘을 소개해주는데 둘의 차이를 분석해보자. 다익스트라 알고리즘 : 한 지점에서 각각의 특정 지점까지의 최단 경로 - 그리디에 속함 플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지의 최단 경로 - dp에 속함 간선의 개수 : E 노드의..

chapter 5. DFS/BFS ✅ DFS/BFS에 대해서 알아보자! DFS/BFS는 인공지능 수업시간에 공부했어서 그 개념은 알고 있었지만, 코드로 작성해 본 경험은 예전에 급하게 문제를 풀 때를 제외하곤 없었다. 알고리즘을 풀면서 DFS/BFS는 음.. 뭐랄까, 재귀나 완전탐색 등 다른 방법으로도 풀리는 문제들도 있었는데 가끔은 DFS/BFS가 아니면 풀 수 없겠는 문제(아니면 매우 복잡한)가 많더라. 그래서 공부해봄 ✅ DFS DFS는 깊이 우선 탐색 알고리즘이다. 이 알고리즘은 특정한 경로로 탐색하다가 특정 상황에서는 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가서 다른 경로로 탐색하는 경로로 탐색하는 알고리즘이다. import Foundation func DFS (graph: [T: ..

chapter 8. DP ✅ 다이나믹 프로그래밍(DP)에 대해서 알아보자! DP는 학교 수업시간에 피보나치를 공부하면서 계산한 부분을 계산하지 않는 것으로 배웠는데, 그 당시에는 그게 DP인지 몰랐음 알고리즘을 풀면서 DP와 같은 문제들을 잘 못푸는데, 이번에 공부해 보니까 그 사고를 얻어서 조금 자신감도 생김 수능때도 점화식 문제에 유독 너무나도 약했는데, DP는 점화식이 거의 베이스네..? 아무튼 열심히 해보자. ✅ 1로 만들기 점화식을 이용하던데, 특정한 작은 값을 정해서 직접 그러보면 문제를 만드는데 도움이 많이 된다. 또한, 보텀업 방식으로 계산하는게 조금 더 이득이 있다고 하고, 엄청 어렵지도 않으니까 한번 해보자. 비슷한 문제를 백준에서 찾아 풀어보자. 🟠 백준문제 알고리즘을 점화식을 만들어..

✅ 이번 시간에는 드디어 코딩 테스트를 제대로 준비하기 위해서 Swift 자료구조와 알고리즘 책을 구입하고 공부한 것에 대해서 기록해 보려고 해. 우선 내가 C언어(C++ 아님;;) 로 코딩 테스트를 준비했기 때문에, 시간 내에 빨리 풀기가 너무나도 힘들었음. 그래서 내가 python으로 준비 했었으나, 토스 코딩 테스트를 보는데 Swift로 제한해 둔 것을 보고 아예 다시 맘을 잡고 공부해보기로 함. 근데 단점은 Swift로 풀어도, 반환 방법, 배열의 index 참조 법, String을 다루는 법 등 Swift를 다루기가 어려웠어. 또한 Dictionary를 Python에서도 상당히 힘들어 했었는데, Swift로도 여전히 힘들어서, 아예 하나하나 정독하기 위해서 책을 구입했다. ✅ 공부 계획 챕터를 ..