[C++] Data Structure & Algorithm44 [DP] Chapter 06. 실전 문제 : KART-RIDER (N모 회사) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/07670c6d8432d4635fb4fb547d9c5e4ea9c021e1 실전 문제 : KART-RIDER (N모 회사) · developeSHG/Data_Structure-Algorithm@07670c6 developeSHG committed Aug 22, 2023 github.com #include #include #include #include #include using namespace std; #include #include // 오늘의 주제 : 동적 계획법 / (DP) // KART-RIDER // - 카트는 게임이 시작하면 달리기 시작하며, 주어진 시간(T)동안 달.. 2023. 8. 18. [DP] Chapter 05. 실전 문제 : ENCHANT (K모 회사) GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/23423f2e32518517a1456e6600a483500ac09899 실전 문제 : ENCHANT (K모 회사) · developeSHG/Data_Structure-Algorithm@23423f2 developeSHG committed Aug 22, 2023 github.com #include #include #include #include #include using namespace std; #include #include // 오늘의 주제 : 동적 계획법 (DP) // ENCHANT // +0 집행검 // 무기 강화 주문서 => +1 / +2 / +3 중 하나 // +9.. 2023. 8. 18. [DP] Chapter 04. 샘플 문제 : TIC-TAE-TOE GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/e90665bf5dc4e96eed19e507e91fbcfa80b14719 샘플 문제 : TIC-TAE-TOE · developeSHG/Data_Structure-Algorithm@e90665b developeSHG committed Aug 22, 2023 github.com 틱택토 게임 - https://www.google.com/search?q=%ED%8B%B1%ED%83%9D%ED%86%A0&oq=%ED%8B%B1%ED%83%9D%ED%86%A0&gs_lcrp=EgZjaHJvbWUqBggAEEUYOzIGCAAQRRg7MgYIARBFGDvSAQgxMDM0ajBqN6gCALAC.. 2023. 8. 18. [DP] Chapter 03. 샘플 문제 : TRIANGLE_PATH GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/f3e8c575947be7453c8520077b7b38702a954ee0 TRIANGLE_PATH · developeSHG/Data_Structure-Algorithm@f3e8c57 developeSHG committed Aug 18, 2023 github.com TRIANGLE_PATH - (0,0)부터 시작해서 아래 or 아래우측으로 이동 가능 - 만나는 숫자를 모두 더함 - 더한 숫자가 최대가 되는 경로? 합? #include #include #include #include #include using namespace std; #include #include // 오늘의 .. 2023. 8. 18. [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. 이전 1 2 3 4 5 다음
