다익스트라 알고리즘을 공부하다보면 나오게 되는 플로이드-워셜 알고리즘! 정말 이 알고리즘을 볼 때마다 감탄이 나오는 것 같다. [Algorithm] 다익스트라 알고리즘🕸️ 다익스트라 알고리즘그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.각 정점을 방문하면서 그 정점에 도달하는 최소값을 갱신해주는 방식이다. 다음 정점을 선swift-library.tistory.com🌐 Floyd-Warshall 플로이드-워셜 알고리즘그래프에서 가능한 모든 정점 쌍에 대해 최단 거리를 구하는 알고리즘이다. 시간복잡도는 O(V^3)이지만 모든 노드 쌍에 대해 최단 거리를 구할 수 있다. 특히 다익스트라 알고리즘은 음의 가중치를 가지는 그래프에서 쓸 수 없는데, 플로이드-워셜은 쓸 수 있다.🔥 Swi..
전체 글
🕸️ 다익스트라 알고리즘그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.각 정점을 방문하면서 그 정점에 도달하는 최소값을 갱신해주는 방식이다. 다음 정점을 선택할 때 시작정점으로부터 가장 짧은 거리의 정점을 방문해야 한다.🔥 Swift 구현실제 구현은 아래와 같다. 다익스트라의 시간 복잡도는 O(V^2 + E)인데, 그것을 표현하고 싶어 아래와 같이 표현했다.struct Edge { var d: Int var w: Int}func dijkstra(graph: [[Edge]], start: Int) -> [Int] { var distances = Array(repeating: Int.max, count: graph.count) var visited = Array..
🥸 지난 글이전 글에서 0-1 배낭문제를 다이내믹 프로그래밍으로 푸는 방법을 소개했다. 이번에는 백트래킹으로 풀어보려고 한다. [Algorithm] 0-1 배낭문제(Knapsack Problem) - DP 풀이알고리즘 하면 나오는 대표 문제인 0-1 배낭문제에 대해서 글을 써보려고 한다.🎒 0-1 배낭 문제왜 0-1 배낭 문제일까? 0-1의 의미는 배낭에 넣기, 안 넣기 둘 중 하나만 선택이 되고, 일부만 넣는swift-library.tistory.com🛤️ Backtracking 백트래킹?나는 좀 더 간단하게 설명해보고 싶었다. 뭔가 의외로 엄청 어렵게 설명되어 있는 글들이 많았다... Backtracking이라는 단어의 뜻을 살펴보면 추적을 종료한다는 뜻으로도 보인다. 뭘 종료할 건데?? 이를 ..
알고리즘 하면 나오는 대표 문제인 0-1 배낭문제에 대해서 글을 써보려고 한다.🎒 0-1 배낭 문제왜 0-1 배낭 문제일까? 0-1의 의미는 배낭에 넣기, 안 넣기 둘 중 하나만 선택이 되고, 일부만 넣는 것은 불가능하기 때문에 0-1 배낭 문제라는 이름이 붙어졌다. 최대 15kg까지 넣을 수 있는 배낭에 다음과 같이 무게와 값어치를 가지고 있는 물건을 넣었을 때 어떻게 담아야 가장 비싸게 담을 수 있을까?물론 가장 좋은 방법은 물건을 쪼갤 수 있다면 무게당 가장 비싼 걸 1kg씩 차곡차곡 담으면 될 것이다. 하지만 이 문제의 핵심은 물건을 쪼갤 수 없다는 것이다. 그렇다고 무게당 가장 비싼 것부터 담게 된다면 이것이 가장 최적의 방법인지 장담할 수 없다.🎛️ 동적 계획법(DP)을 사용한 풀이가장 유..
🥸 문제 소개🧑🏻💻 문제 풀이사전을 순서대로 만들어 나가면서 target이 현재 추가된 단어와 같다면 값을 리턴하게 만들었다. 사전을 만들어 나가는 과정은 재귀함수를 활용하여 구현했다.func solution(_ target: String) -> Int { let vowels = ["A", "E", "I", "O", "U"] var found = false var answer = 0 func dfs(_ word: String) { if word.count > 5 || found { return } answer += 1 if word == target { found = true ..
🙇 시작하며물론 알고있는 내용들도 많지만 CPU에 대해서 간단하게 정리해보고 싶어서 이렇게 글을 먼저 작성하게 되었다. 아래와 같이 homebrew CPU라고 집에서 CPU도 만들 수 있다! (솔직히 나중에 만들어 보고 싶다... 극강의 공돌이만 도전 할 듯..?) Homebrew CPU Home PageMagic-1 is a completely homebuilt minicomputer. It doesn't use an off-the-shelf microprocessor, but instead has a custom CPU made out of 74 Series TTL chips. Altogether there are more than 200 chips in Magic-1 connected toge..
문제풀다가 사실 깜짝 놀랐다. 2차원 배열 회전을 하는 방법이 아리까리(?) 했던 것이다... 그래서 이번 기회에 확실하게 복습해보려고 한다.🕑 시계 방향 회전그림을 살펴보면 행이 열이 되고, 열은 행이 되면서 뒤집히는 효과(?)를 볼수 있다. 이것을 (n-1-열)로 나타낼 수 있다. 이것을 코드로 구현해보면 아래와 같다.func rotateClockwise(_ matrix: [[Int]]) -> [[Int]] { let n = matrix.count let m = matrix[0].count var rotated = Array(repeating: Array(repeating: 0, count: n), count: m) for i in 0..🕗 시계 반대 방향 회전반대로 ..
🧪 Test Double?항상 테스트를 하면서 Mock, Stub, Fake... 이런 키워드들을 보면서 언제 어떤 걸 쓰는 게 맞는 표현인지가 궁금해서 이번기회에 제대로 찾아보게 되었다.🤓 공식... 정의?솔직히 요즘 인공지능이 생겨나면서 인터넷에서 도대체 어떤것이 정확한 자료인지 항상 고민이 많이 된다. 그러다가 마틴 파울러 사이트에서 이것을 명확하게 정의한 것을 보게 되었다. 마틴 파울러가 누군지는 굳이 말할 필요 없을 것 같다. bliki: Test DoubleTest Double is generic term for fakes, mocks, stubs, dummies and spies.martinfowler.com마틴 파울러는 5가지를 소개하고 있다. Dummy, Fake, Stub, Spy,..
