본문 바로가기

Algorithm/알고리즘

Swift) 최소 신장 트리 :: 프림 알고리즘 (Prim's Algorithm) 구현 해보기

Algorithm/알고리즘 Swift) 최소 신장 트리 :: 프림 알고리즘 (Prim's Algorithm) 구현 해보기 안녕하세요, 소들입니다 :) 오늘은 저번 포스팅에 이어, 최소 신장 트리 중 프림 알고리즘에 대해 포스팅을 해볼 건데요.. 만약 최소 신장 트리가 뭐야? 크루스칼 알고리즘이 뭐야? 하시는 분은 이 포스팅을 먼저 읽고 오시길 ...!!! 👀 참고로 크루스칼보다 훨~~~~~~~~~ 쉬우니 맘 편하게 봅시다!!!!!!! 그럼 알아보러 갑시다 :) 모든 포스팅은 편의 말투로 합니다~!! 1. 프림 알고리즘의 로직 크루스칼과 마찬가지로 위 그래프를 갖고 프림 알고리즘을 통해 최소 신장 트리를 찾는 방법을 알아 보겠음!!!! 1-1. 시작 노드(A)를 정하고, 이를 "연결된 노드 집합"에 삽입한다 가장 작은 간선의 가중치부터 시작하는 크루스칼과 달리, 프림은 시작 노드를 임의로 정함! 내가 만약 시작 노드를 A로 ..

Swift) 최소 신장 트리 :: 크루스칼 알고리즘(Kruskal’s algorithm) 구현 해보기

Algorithm/알고리즘 Swift) 최소 신장 트리 :: 크루스칼 알고리즘(Kruskal’s algorithm) 구현 해보기 안녕하세요!!! 소들입니다 :) 오늘은 최소 신장 트리에 대해 포스팅을 해볼 건데요.. 제가 저번 주에 포스팅 하면서... 이번주부턴 Swift Syntax & iOS에 관련 포스팅을 들고올 거라 했는데... 저번 주의 제가 바빠서 알고리즘 포스팅이 밀려버렸음 😱 따혹혹 TMI는 집어 치우고.. 좀 어려운 내용이라 ㅠ.ㅠ 처음에 이해하기 힘들 수도 있으니..! 두번 세번 반복해서 보는 것을 추천! (나또한 그러려고 포스팅) 그럼 알아보러 갑시다 :) 모든 포스팅은 편의 말투로 합니다~!! 1. 신장트리와 최소 신장 트리 자, 먼저 신장 트리란 무엇이고, 최소 신장 트리란 또 무엇인지부터 알고가보겠음 👀 1-1. 신장 트리 모든 노드가 연결되어 있으며, 사이클이 발생하지 않는 그래프 이것이 바로 신장 트리..

Swift) 최단 경로 :: 다익스트라(Dijkstra) 구현 해보기

Algorithm/알고리즘 Swift) 최단 경로 :: 다익스트라(Dijkstra) 구현 해보기 안녕하세요:) 소들입니다! 이번 포스팅은 최단 경로 알고리즘 중 하나인, 다익스트라에 대해 공부해볼 거예요!!!!! 조금 어려울 수 있지만!!!! 내가보기엔 이론보다 이름이 젤 어려운듯; 먼저, 최단 경로의 종류에 대해 알아보고, 다익스트라 알고리즘에 대해 알아볼 것입니다 :) 모든 포스팅은 편의 말투로 합니다~!! 1. 최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾는 것 가중치 그래프의 경우, 간선 가중치의 합이 최소가 되도록 하는 경로를 찾는 것 말 그대로 우리가 앞서 배웠던 그래프에서 두 노드 간의 가장 짧은 거리를 찾는 것임 근데 보통 최단 경로를 찾는 문제는 다음과 같이 세 가지 유형으로 나뉘는데, 1-1. 단일 출발 - 단일 도착 최단 경로 그래프 내의 특정 노드 A에서 출발하여, ..

Swift) 힙(Heap) 구현 해보기

Algorithm/알고리즘 Swift) 힙(Heap) 구현 해보기 안녕하세요 :) 소들입니다..! 거의 한 달 전부터 저의 일정표 한 구석을 차지하던 Heap에 대해 드디어 포스팅을 해보려고 합니다...후후 사실 Python에선 Heap을 제공해주는데, Swift는 따로 제공해주지 않아서 최단 경로 알고리즘 구현 해보다가 막혀서.. ;ㅁ;.. 억지로 하게됨 그래서 급하게 포스팅을 해봅니다..!!!! 모든 포스팅은 편의 말투로 합니다~!! 1. 트리의 종류 Heap을 알기 전에 우리가 이전ㅇㅔ 공부했던 트리 개념에 덧붙여 트리 종류에 대해 먼저 간단하게 알고 갈 것임 :) 왜냐면 Heap을 구현하기 위해 알아야 함 1-1. 완전 이진 트리 왼쪽 자식 노드부터 채워지며, 마지막 레벨을 제외한 모든 자식 노드가 채워져 있는 트리 1-2. 포화 이진 트리 모든 노드가 0개 또..

Swift) 탐욕법 (Greedy Algorithm) + 프로그래머스 체육복 풀이

Algorithm/알고리즘 Swift) 탐욕법 (Greedy Algorithm) + 프로그래머스 체육복 풀이 안녕하세요 :) 소들입니다! 으으.. 알고리즘 이론 공부도 점점 끝이 보여 가네요!!! 물론 이론만 끝이지 실제 문제풀이 해봐야 하는 게 20배는 더 많지만..ㅎ 요즘 Swift 포스팅을 못해서 마음 한 켠이 찝찝한데.. 다음 주 부턴 Swift & iOS 포스팅이 더 많이 올라올 것 같아요 😇 알고리즘 포스팅은 재밌지만 조회수가 많이 안 나온다^^;; 이번엔 이름도 무시무시한 탐욕법에 대해 공부해볼 거예요! 그리디 알고리즘이라고 하는데, 딱히 막 트리, DP 같이 정해진 알고리즘은 아니라... 이번엔 프로그래머스에서 탐욕법 Lv.1에 해당하는 쉬운 체육복이란 문제로 이해해보려고 합니다 :) (제가 푼 게 정답은 아니겠지만..!?) 그럼 간단하게 공부해볼게요!!!! 모든 포스팅은 편의 말투로 합니다~!!..

Swift) 깊이 우선 탐색(DFS) 구현 해보기

Algorithm/알고리즘 Swift) 깊이 우선 탐색(DFS) 구현 해보기 안녕하세요 :) 소들입니다!!! 이번 포스팅에선 깊이 우선 탐색(DFS)에 대해 알아보려고 해요!!!! 깊이 우선 탐색이란, 너비 우선 탐색(BFS)과 마찬가지로 그래프를 탐색하는 방법 중 하나인데, 그래프를 모르면 이해할 수 없으니, 혹시 그래프를 모르면 이 포스팅을 꼭! 먼저 읽고 와주세요 모든 포스팅은 편의 말투로 합니다~!! 1. 깊이 우선 탐색(DFS)이란? 깊이 우선 탐색이란 Depth-First Search로, 보통 DFS라고들 많이 부름!!! :) 머 정의는 다음과 같은데.. 탐색하려는 노드의 자식 노드부터 우선 탐색하는 방식 음.. 정의만 보면 역시 이해가 안 갈 테니까:) 깊이 우선 탐색 방식에선, 다음과 같은 순서로 그래프의 노드를 탐색함!! 숫자가 순서라고 생각하면 됨!!! 탐색 노..

Swift) 너비 우선 탐색(BFS) 구현 해보기

Algorithm/알고리즘 Swift) 너비 우선 탐색(BFS) 구현 해보기 안녕하세요 :) 소들입니다!!! 이번 포스팅에선 너비 우선 탐색(BFS)에 대해 알아보려고 해요!!!! 먼저, 너비 우선 탐색이란 그래프를 탐색하는 방법 중 하나인데, 그래프를 모르면 이해할 수 없으니, 혹시 그래프를 모르면 이 포스팅을 꼭! 먼저 읽고 와주세요 그래프가 알고리즘? 자료구조? 중에 어려운 축에 속해서.. 쉽게 이해하실 수 있게 노력해보겠습니다 :) 깊이 우선 탐색은 다음 포스팅에서!! 모든 포스팅은 편의 말투로 합니다~!! 1. 너비 우선 탐색(BFS)이란? 너비 우선 탐색이란 Breadth-First Search로, 보통 BFS라고들 많이 부름!!! :) 머 정의는 다음과 같은데.. 인접한 노드들을 우선 탐색하는 방식 음.. 정의만 보면 역시 이해가 안 갈 테니까:) 너비 우선 탐색 방..

Swift) 탐색 :: 이진 탐색(Binary Search) 이해하기

Algorithm/알고리즘 Swift) 탐색 :: 이진 탐색(Binary Search) 이해하기 안녕하세요 :) 소들입니다!!!!!!! 이번 포스팅은 탐색 알고리즘 중에서도, 이진 탐색 알고리즘에 대해 다뤄볼까 합니다!!! 👀 이전에 공부한 완전 탐색 알고리즘은, 최악의 경우 모든 배열을 순회하기 때문에, 시간 복잡도가 O(n)으로 성능이 좋은 편은 아니였어요 :) 이진 탐색은 완전 탐색보다 좋은 성능을 자랑한답니다 하하하ㅏㅎ 그럼 어떻게 탐색하길래 성능이 좋아진 것인지.. 알아보러 갑시다 💩 모든 포스팅은 편의 말투로 합니다~!! 1. 이진 탐색이 모야? 이진 탐색은 어떤 알고리즘이냐면, 탐색할 자료를 둘로 나누어, 해당 데이터가 있을 곳을 탐색함 탐색할 자료가 정렬되어 있을 때만 사용 가능함 오.. 정의는 뭔 🐶소린가 싶겠지만, 여기서 중요한 것은 "둘로 나누어"와, "정렬되어 있는 자료만 가능..

Swift) 탐색 :: 완전 탐색(Brute Force) 이해하기

Algorithm/알고리즘 Swift) 탐색 :: 완전 탐색(Brute Force) 이해하기 안녕하세요 :) 소들입니다!!!!!!! 이번 포스팅은 탐색 알고리즘 중에서도 완전 탐색 알고리즘에 대해 다뤄볼까 합니다!!! 👀 참고로 말하자면, 가장 간단하면서도 가장 쉬운 방법이라.. 별도로 포스팅을 해야하나..? 했지만, 일단 알고리즘 이름이 존멋이잖아요? 뭔가 있어보이는 완.전.탐.색 ㅎ 따라서 간단하게 끄적여볼까 합니당! 모든 포스팅은 편의 말투로 합니다~!! 1. 탐색이란? 자, 먼저 "탐색"이라고 했는데, 우리는 이전에 사실 이진 "탐색" 트리(BST)란 것을 이미 공부 했었음 :) 그럼 도대체 탐색 알고리즘이 뭐를 하는 것일까?? 여러 데이터 중 원하는 데이터를 찾아내는 것 을 말함 ㅎㅎ 그중 이진 탐색 트리는, 데이터들을 특정 규칙에 따라 트리로 구성되어 있는 것을 말한 것이였음! 그럼 ..

이전 1 2 다음

Calendar

최근 댓글

Visits

Today

Yesterday

티스토리툴바