→ 알고리즘 관련

⚙️ 벨먼 포드 (Bellman-Ford) 알고리즘최단거리를 구할 수 있는 아름다운? 알고리즘이다. 이런 알고리즘은 일단 코드로 보고 어떻게 돌아가는지 아는 게 중요하다고 생각해서 바로 Pseudo code를 가져와 봤다. 위키백과 영어버전에서 가져왔다.function BellmanFord(list vertices, list edges, vertex source) is distance := list of size n // Step 1: initialize graph for each vertex v in vertices do distance[v] := inf // The distance from the source to itself is zero distanc..

다익스트라 알고리즘을 공부하다보면 나오게 되는 플로이드-워셜 알고리즘! 정말 이 알고리즘을 볼 때마다 감탄이 나오는 것 같다. [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)을 사용한 풀이가장 유..

문제풀다가 사실 깜짝 놀랐다. 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..🕗 시계 반대 방향 회전반대로 ..

Segment Tree 란?세그먼트 트리는 범위 데이터의 조회, 업데이트에 효과적인 자료구조이다. 이진트리의 형태로 바로 O(logN)의 시간복잡도를 가지게 된다. 가장 많이 쓰이는 것은 특정 범위 내의 요소들에 대한 합계, 최솟값, 최댓값을 검색하고 처리할 수 있다. Segment Tree 만들기만약 [1, 2, 3, 4, 5] 와 같은 배열이 있다고 해보자. 이것을 Segment Tree 자료에 넣어 합계를 쉽게 검색하고 싶다. 어떻게 해야 할까? 이진트리의 기본 개념처럼 계속 반으로 쪼개서 저장해 주면 된다. 하지만 우리가 원하는 것은 합계 뿐... 아래처럼 저장해 주면 Segment Tree 끝!이다. 참 쉽죠? 이것을 코드로 구현해 보자. Segment Tree를 만들기 위한 고민Tree의 크기..

Bitmask란?Bitmask는 단어 그대로 비트에 마스킹을 한다라는 뜻인데, 비트 연산을 활용하여 데이터를 효율적으로 저장하고 조작하는 방법이다. 비트(Bit)는 컴퓨터 과학에서 정보의 가장 작은 단위이다. 비트는 이진법(Binary System)을 기반으로 하며, 두 가지 값(0, 1) 중 하나를 가질 수 있다. 비트연산Bitmask를 하기 전에 비트 연산에 대해서 알아야 한다. 비트 연산에는 AND, OR, XOR, NOT, Shift연산이 있다. 아래와 같은 게이트들을 접해봤을 것이다. (직접 그려봤는데 생각보다 그리기 힘들다 😅)처음에는 OR과 XOR이 약간 헷갈렸는데 아래의 개념으로 생각한다면 아주 이해가 쏙쏙 된다.AND 연산 ( & )1101 & 1011 을 하게 되면 두 비트가 모두 1..