본문 바로가기

5️⃣ CS/Algorithm9

[Java Algorithm Note] 다익스트라 (feat. BOJ #1753 최단경로) 오늘은 그래프, 그리디를 활용하는 다익스트라 알고리즘에 대해 정리해보려구 한다. 이름은 너무너무 많이 들어봤지만, 한번도 제대로 공부해본적은 없는,,!! 📎 다익스트라(Dijkstra) 알고리즘 다익스트라는 최단 경로를 찾을 수 있는 알고리즘 중 하나이다. 최단 경로 간선의 가중치가 있는 그래프에서, 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로 👉 다익스트라 알고리즘을 사용한다는 것은, 하나의 시작 정점에서 끝 정점까지의 최단 경로를 구한다는 것을 얘기한다. 아래 그림을 예로 보자. A가 시작점이고 C가 목적지라고 할 때, 가장 먼저 A에 인접해있는 정점은 B와 C이다. 이 때 A가 C로 가기 위해서는 두 가지 선택지가 생긴다. 바로 C로 가자! B를 거쳐서 C로 가자! 위의 그림을 보면 .. 2022. 8. 25.

[Java Algorithm Note] 부분집합 (feat. 재귀) 드디어 순열, 조합, 부분집합 시리즈 중 마지막인 부분집합 등쟝 (순열, 조합 정리는 아래를 참고해주세요! 👇) https://seolhee2750.tistory.com/229 [Java Algorithm Note] 순열 (feat. 재귀) 순열, 조합, 부분집합 이 세가지에 대해서 중요하게 생각을 못했는데, 이번에 배워보니 정말 너무너무 중요한 것들이어따..!! 이것들을 공부하고나니 문제에서도 다양하게 활용할 수 있음 그래 seolhee2750.tistory.com https://seolhee2750.tistory.com/230 [Java Algorithm Note] 조합 (feat. 재귀) 저번 순열에 이어 이번에는 조합에 대해 정리해보려 한다. (순열 정리는 아래 참고! 👇) https://seol.. 2022. 8. 16.

[Java Algorithm Note] 조합 (feat. 재귀) 저번 순열에 이어 이번에는 조합에 대해 정리해보려 한다. (순열 정리는 아래 참고! 👇) https://seolhee2750.tistory.com/229 [Java Algorithm Note] 순열 (feat. 재귀) 순열, 조합, 부분집합 이 세가지에 대해서 중요하게 생각을 못했는데, 이번에 배워보니 정말 너무너무 중요한 것들이어따..!! 이것들을 공부하고나니 문제에서도 다양하게 활용할 수 있음 그래 seolhee2750.tistory.com 📎 조합 조합은 서로 다른 n개의 원소에서 r개를 순서에 상관하지 않고 선택 혹은 나열하는 것을 말한다. 순열과의 차이점은 바로 '순서'!! 조합은 순서를 가지지 않으므로 {1, 2, 3}, {3, 2, 1}을 같은 것으로 본다. 그리고 조합도 순열처럼 중복 조합.. 2022. 8. 15.

[Java Algorithm Note] 순열 (feat. 재귀) 순열, 조합, 부분집합 이 세가지에 대해서 중요하게 생각을 못했는데, 이번에 배워보니 정말 너무너무 중요한 것들이어따..!! 이것들을 공부하고나니 문제에서도 다양하게 활용할 수 있음 그래서 오늘은 그 중 첫 번째로 순열을 구현하는 방법에 대해 정리해보려한다. 📎 순열 순열은 서로 다른 n개의 원소에서 r개를 순서에 상관있게 선택 혹은 나열하는 것을 말한다. 예를 들어 {1, 2, 3}의 배열이 있다고 하면, {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, ... 이런 식으로 나열되는 것! 여기서 중요한 점은 {1, 2, 3}과 {3, 2, 1}이 서로 다르다는 것이다. 기본 순열은 중복은 허용하지 않지만 순서를 가지기 때문에 순서가 다르면 다른 순열로 본.. 2022. 8. 15.

[Swift Algorithm Note] 최장 증가 부분 수열 2 (feat. BS) 저번에는 DP로 최장 증가 부분 수열 (LIS)를 구하는 방법을 알아보았는데, 오늘은 DP보다 훨씬 시간복잡도가 좋은 이분 탐색 (BS)로 구하는 방법을 정리해보려고 한다. 두 가지 방법의 차이점도 알아보고, 이분탐색으로 LIS를 구하는 알고리즘도 구현해보자. (LIS에 대한 설명, 그리고 DP로 LIS 구하는 알고리즘이 궁금하신분들은 요기👇를 참고해주세요!) 2021.08.28 - [📍 Algorithm Note/🔍 with Swift] - [Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP) [Swift Algorithm Note] 최장 증가 부분 수열 (feat. DP) 오늘은 최장 증가 부분 수열 (LIS)에 대해 정리해보려한다. LIS를 구하는 방법은 여러가지지만, .. 2021. 8. 29.

이전 1 2 다음

티스토리툴바