분류 전체보기539 [DP] Chapter 02. 샘플 문제 : LIS (Longest Increasing Sequence) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/cfc5d79d0dcc673ac44acfee9616c24a90c0715f LIS (Longest Increasing Sequence) · developeSHG/Data_Structure-Algorithm@cfc5d79 developeSHG committed Aug 18, 2023 github.com Seq : 1 9 2 5 7 부분 수열 : 일부(0개 이상) 숫자를 지우고 남은 수열 ex) 1 2 5 ex) 1 9 5 7 순 증가 부분 수열 ex) 1 2 5 LIS : 제일 긴 [순 증가 부분 수열]의 길이 1 2 5 7 = 길이 4 #include #include #inclu.. 2023. 8. 18. [DP] Chapter 01. 동적 계획법 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/fac912f7ab6a8e859eb14e7e89e9c0cff20caaf7 동적 계획법 입문 · developeSHG/Data_Structure-Algorithm@fac912f developeSHG committed Aug 18, 2023 github.com Dynamic Programming 문제를 쪼개서 해결하는데, 과정속에 반복되는 작업을 cache를 재사용해 불필요한 연산을 줄이는 것. 즉, DP는 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러.. 2023. 8. 17. [MST] Chapter 04. Prim 알고리즘을 이용한 맵 생성 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/9b505b2dbc9bb895add268c2114b1ba33fec4f3a Prim 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@9b505b2 developeSHG committed Aug 17, 2023 github.com 크루스칼 알고리즘과 거의 유사하다. 다른 부분은 간선을 어떻게 수집할 것인지 순서가 달라진다. 크루스칼 알고리즘은 탐욕적인 방법을 이용했다. 작은 간선부터 탐색해서 사이클이 발생하지 않는 간선을 추가해줬다. 위처럼 그룹을 나누다가 경우에 따라 그룹을 병합했다. 프림 알고리즘은 하나의 시작점으로 구성된 트리에.. 2023. 8. 16. [MST] Chapter 03. Kruskal 알고리즘을 이용한 맵 생성 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ea4d99bf27f79da3e7b4f924d6e2ca50d9c63744 Kruskal 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@ea4d99b developeSHG committed Aug 17, 2023 github.com 미로라면, 랜덤성이 보장이 되야하는데 코드 특성상 아래랑 우측이 일직선으로 뚫린 현상으로 맵이 만들어지게 했었다. 이 부분을 개선시키기 위해 Kruskal 알고리즘을 이용한 맵 생성을 해볼 것이다. Kruskal을 어떻게 응용할 지 생각해보면 BST를 만들 때, 어떻게 만들었는지를 생각해보자. 이전까지.. 2023. 8. 16. [MST] Chapter 02. Kruskal 알고리즘 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/e91776c4a5ed1f8b2a4cb1104ac89349e77c8bcf Kruskal · developeSHG/Data_Structure-Algorithm@e91776c developeSHG committed Aug 17, 2023 github.com 다시 복습하면 그래프는 [현실 세계의 사물이나 추상적인 개념간]의 [연결 관계]를 표현한다 했었다. 전형적인 그래프는 정점들과 정점들을 연결하는 간선으로 이루어진 것이 그래프였고, 예로 소셜 네트워크 관계도, 지하철 노선도를 그래프로 표현할 수 있었다. 위 사진처럼 정점에 대한 간선을 연결해서 모든 길을 뚫어놓은 상태이고, BF.. 2023. 8. 16. [MST] Chapter 01. Disjoint Set (Union-Find) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/131723902448c69701b98d17c20188b35e06dbc0 Disjoint Set · developeSHG/Data_Structure-Algorithm@1317239 developeSHG committed Aug 14, 2023 github.com Minimum Spanning Tree => 그래프/트리의 활용정도가 된다. 최소 스패닝 트리 (Minimum Spanning Tree)을 알기 전에 알고 가야할 부분이 "상호 배타적 집합 (Disjoint Set)"이다. DSU라고도 한다. A*에서 가장 좋은 후보를 찾을 때, 우선순위 큐를 사용을 하면 효율이 좋은 .. 2023. 8. 14. [Hash Table] Chapter 01. 해시 테이블 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/906c6c8a2bd0ad5d7ed94800c8fb95ced78cd8e6 해시 테이블 · developeSHG/Data_Structure-Algorithm@906c6c8 developeSHG committed Aug 14, 2023 github.com map은 Red-Black Tree. 균형 이진 트리 구조로 만들어져있어 트리 구조로 관리한다. 데이터가 추가, 삭제가 되면 이진 트리를 유지하지만, 균형을 맞춰줘서 한 쪽으로 무너지는 걸 예방하는 형태로 되어있다. 시간 복잡도는 O(log N)을 따른다. hash_map은 속도 측면에서 map보다 훨씬 빠르다. 메모리를 내주고,.. 2023. 8. 14. [Sorting] Chapter 03. 퀵 정렬 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2260b9e13b4c3da9221ca71a6b6d7a1515995208 퀵 정렬 · developeSHG/Data_Structure-Algorithm@2260b9e developeSHG committed Aug 14, 2023 github.com 퀵 정렬은 병합 정렬과 마찬가지로, 데이터를 둘 씩 쪼개서 진행하는 것은 비슷하다. 근데 병합 정렬은 시작부터 반으로 쪼갠 다음, 왼쪽 그룹과 오른쪽 그룹을 따로 정렬해서 정렬된 양 쪽 그룹을 합치는 형태로 조립했었다. 하지만 퀵 정렬은 처음부터 분할하기 보다는 어느정도 특정 알고리즘을 적용시켜 추출한 다음에, 왼쪽 그룹과 오른쪽 그.. 2023. 8. 14. [Sorting] Chapter 02. 힙 정렬과 병합 정렬 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2a955748fbaf3cbd0f5cf002a83f51d2bb347387 힙 정렬과 병합 정렬 · developeSHG/Data_Structure-Algorithm@2a95574 developeSHG committed Aug 14, 2023 github.com #include #include #include #include #include using namespace std; #include // 오늘의 주제 : 정렬 // C# 자료구조/알고리즘 // -> A* OpenList (PQ) // -> C# List = C++ vector // PQ O(logN) // Red-Bla.. 2023. 8. 14. [Sorting] Chapter 01. 기본 정렬 (버블, 선택, 삽입) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/0a525688c3203b9ea67f96a493d765e55d7d8694 기본 정렬 (버블, 선택, 삽입) · developeSHG/Data_Structure-Algorithm@0a52568 developeSHG committed Aug 14, 2023 github.com C++이 아니라 C#이라고 잠시 생각보자. 참고로 이전에, A* 알고리즘에서 OpenList를 만들었는데 그것을 PQ(우선순위 큐)로 만들어 관리하고 있었다. 근데 고민해보면 왜 우선순위 큐를 사용하느냐? 란 생각이 들 수 있다. C#에선 List가 C++에서 vector에 해당하는 자료구조인데, C# Lis.. 2023. 8. 14. 이전 1 ··· 4 5 6 7 8 9 10 ··· 54 다음
