코딩 소양/알고리즘 ㅠ (12) 썸네일형 리스트형 [경우의 수] 순열, 조합, 중복 순열 이번엔 경우의 수를 구하는 순열, 조합, 중복순열에 대해서 알아보겠습니다. 여러분이 많이 알고 있는 경우의 수구하는 알고리즘인데, 이를 넘어서 해당 성분들까지 구해보는 경우를 구해봅시다!! 순열(Permutation) 먼저 순열이 어떤 건지 알아봅시다. 기호로 표현하면 nPr이라고 표현합니다. 해석하자면 n개의 성분에서 r개를 뽑아 나열시킨 경우의 수가 되겠네요.대표적인 예로 줄 세우기가 될텐데, 순열은 방향성이 있는 경우의 수입니다. 즉 123이랑 321은 다르다는 거죠.먼저 순열의 경우의 수를 구하는 식을 보면 이러합니다.한번 구현해보기에 앞서서 순열이 데이터를 선택하는 절차를 보면 이렇게 되겠죠. 그림처럼 선택된 데이터를 제외한 리스트에서 다른 데이터를 가져오는 방식으로 데이터가 선택됩니다. 제가 .. [STL] Sort,Queue,Priority_Queue 이번에는 STL의 sort, que, priority_que의 사용법에 대해서 정리해보겠습니다. 사용법은 무지 간단한데, 잊지 안기 위해..!! Sort sort는 STL중에 가장 많이 쓰는 것 같네요. 진짜 개꿀. 라이브러리는 algorithm입니다. #include sort의 사용법은 매우 간단합니다. sort(정렬할 주소의 첫 번째 값, 정렬할 주소의 마지막 값, 정렬 기준); 정렬할 주소의 첫 번째 마지막 값은 잘 아실테니 넘어가겠습니다. 중요한건 정렬 기준입니다. 간단하게 less, greater가 있습니다. less() : 이걸 넣을 경우엔 오름차순으로 정렬이 됩니다. greater() : 이건 반대로 내림차순으로 정렬이 되죠. 물론 이것만 알아도 충분하지만, 스스로 정렬 기준을 정할 수 있습.. [DP & GA] Dynamic Programming & Greedy Algorithm 이번에는 Dynamic Programming에 대해서 알아보겠습니다.해석하면 동적 프로그래밍이라고 하지만.. 절대 동적이지 않습니다.. Dynamic Programming은 각 경우에 대한 table을 만들어서 점화식을 도출해내는 방식을 말하는데 간단한 문제에 대해서 알아봅시다. 풀어볼 문제는 백준 알고리즘의 1003번 문제입니다! https://www.acmicpc.net/problem/1003 문제는 간단한 피보나치 수열에 대해서 fibonacci(n)이라고 했을 때 fibonacci(N)을 호출하면 fibonacci(0), fibonacci(1)을 얼마나 불러오는지구하는 문제입니다. 문제에 보면 피보나치 수열에 대한 함수를 줬는데, int fibonacci(int n) { if (n == 0) { .. [Shortest Path] Dijkstra Algorithm 이번에 준비한 알고리즘은 Shortest Path를 찾는 알고리즘인 Dijkstra Algorithm입니다!! 옛날에 처음 다익스트라 알고리즘 배웠을 때는 좀 노가다스럽게 배워서 엄청 어렵고 짜증난 알고리즘이었는데, 다시 공부하니까 참 쉽네요... 역시 가르치는 사람이 잘 해야하는건가.. 아무튼! Dijkstra Algorithm은 BFS기반으로 Shortest Path를 찾는 알고리즘입니다. 절차를 설명하자면! 탐색되지 않은 노드가 담긴 우선순위 큐로부터 다음 탐색 노드를 pop한다. 탐색 노드의 주변 연결된 노드들에 대해서 거리를 비교해본다. 여기서 비교란 기준 노드 탐색 노드 연결 노드의 거리값이 현재 연결 노드에 설정된 거리값보다 작은지 비교하는 것이다. 작다면 연결 노드의 거리값을 재설정해준다... [MST - 3] Prim Algorithm 다음으로 볼 알고리즘은 MST를 구하는 두 번째 알고리즘인 Prim Algorithm입니다. 일전에 MST랑 Krustal Algorithm 에 대해서 알아보았는데, 이번에는 다른 MST를 찾는 Algorithm입니다!! Prim Algorithm의 특징은 이러합니다. 어떠한 vertex로 시작해도 결과는 똑같다. 방향성을 가진다. BFS처럼 주변을 먼저 살핀다. Krustal Algorithm은 Find, Union 구동 방식을 사용하지만, Prim Algorithm의 경우는 vertex의 주변 vertex를 탐색하는 방법으로 MST를 찾습니다. Prim Algorithm의 핵심은 key값이 있다는 것인데, Krustal Algorithm의 대표값이랑 비슷하면서도 다른 사용 방법을 가지고 있습니다. K.. [MST - 2] Kruskal Algorithm MST를 알아보았고, 이번에는 MST를 구하는 첫 번째 알고리즘인 Krustal Algorithm에 대해서 알아봅시다. 저번 포스트(MST - 1)에서 MST에서 사용되는 여러 용어들에 대해서 알아보았는데, Krustal Algorithm에서는safe edge에 대한 개념이 사용됩니다. 기본적으로 Krustal Algorithm은 Find, Union의 구동 방식을 찾는데, 이에 대해서 먼저 알아봅시다. find : Vertex(정점)의 집합인 Cut의 대표값이 다른지 검색하는 단계union : 대표값이 다른 Cut 두 개를 합치는 단계 그림으로 보니까 이해가 되시나요?? Krustal Algorithm은 이게 전부입니다. 조금 유식하게 Krustal Algorithm을 표현해보면~ safe edge에 .. [MST - 1] Minumum Spanning Tree 이번에는 MST(Minumum Spanning Tree)에 관해서 알아봅시다. 한국어로는 최소 신장 트리라고하는데, MST를 보기 전에 먼저 Spanning Treed에 대해서 봅시다. Spanning Tree ? graph의 최소 연결 부분으로 나타낸 Tree 최소 연결 부분이라는 것이 안 와닿을 수 있는데, n개의 정점을 가지는 graph에서 간선의 수가 최소로해서 나타내는 것입니다. 간선의 수가 최소가 된다는 거는 정점은 일대일로 연결이 되어 있다는 것이겠네요!이런 경우 반드시 Tree의 형태가 되기 때문에 Spanning Tree라고 한다는 군요. 그림으로 보면 바로 이해가 될 것입니다. 이제 MST를 살펴봅시다. 결국 Minumum Spanning Tree라는 것은 Spanning Tree 중 .. [BFS & DFS]BFS(Breadth First Search) 저번에 *DFS*에 대해서 공부하였으니까, 이번엔 BFS에 대해서 공부해봅시다.저번에 봤던 것 처럼 BFS는 Breadth First Search라고 너비 먼저 탐색알고리즘이 되겠습니다. BFS는 그럼 어떤 장단점이 있을까요???BFS는 넓게 탐색하기 때문에 최단 경로를 찾는데에 용이합니다만,목적지까지 모든 경우가 비슷한 거리를 가지면 안 좋을 수 있고, DFS와 마찬가지로 메모리 overflow가 일어날 수 있습니다(탐색 범위가 크면). DFS를 봤던 것 처럼 BFS도 tree부터 살펴봅시다!!! BFS 그림을 보니까 이해가 되시나요??? 이번엔 DFS와 다르게 자식들을 먼저 탐색하네요!!! 우물을 넓게 파는 알고리즘!?!?!? graph에서 보면 다음과 같습니다. 그림을 보면 이해가되시나요?? 위에 .. 이전 1 2 다음
