알고리즘 문제풀이/기본문제풀이26 [기본문제풀이] 분할정복 풀이일시 : 2020-08-31 분할정복 : divide and conquer 로 성질이 똑같은 여러개의 부분문제로 문제를 나누어 해결하는 방법이다. 1. 문제 사례를 하나 이상의 작은 사례로 분할한다. 2. 작은 사례들을 각각 정복(conquer)한다. 재귀를 이용 3. 작은 사례에 대한 해답을 통합하여 원래 사례의 답을 구한다. 장점 - 문제를 나눠 풀어 어려운 문제를 해결할 수 있다. 병렬적으로 문제를 해결. 단점 - 함수를 재귀적으로 호출하여 오버헤드가 발생, 스택 오버플루우가 발생하거나 과도한 메모리사용 가능성 쓰임 - 이분검색, 최대값찾기 및 여러 알고리즘문제풀이에 쓰인다. 아래는 분할&정복 알고리즘의 대략적인 묘사도이다. 문제와 풀이 : dbstndi6316.tistory.com/10.. 2020. 12. 29. [기본문제풀이] DFS 깊이우선탐색 풀이일시 : 2020-08-30 DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http://www.aistudy.com/heuristic/depth-first_search.htm 문제 : DFS를 구현하라 풀이 : recursive하게 구현한다. #include #include #define MAX 9 using namespace std; int d[MAX] = { 0, }; //방문체크하는배열 vector a[MAX]; void dfs(int x) { if (d[x] == 1) return; d[x] = true;//방문체크하기 cout 2020. 12. 29. [기본문제풀이] BFS 너비우선탐색 풀이 일시 : 2020-08-30 BFS : 탐색 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는 것. 그 중 한 방법인 너비우선탐색은 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다. 시작정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져있는 정점을 나중에 방문한다. DFS와 비교하여 wide 하게 탐색하는 BFS는 queue를 이용하여 구현할 수 있다. 최단거리를 구할때 주로 이용된다. 문제 : BFS를 queue로 구현하라. 풀이 : 인접 노드들을 queue에 담고 그 다음 노드는 큐에서 나오는 노드가 될 것이다. 그 노드의 인접노드를 다시 queue에 넣는 작업을 queue가 비기 전 까지 반복해준다. #include #include #include.. 2020. 12. 29. [기본문제풀이] greedy 알고리즘 풀이 일시 : 2020-08-29 그리디알고리즘 : 당장 눈앞에의 최적의 상황만 쫓는 알고리즘이다. 대표적인 알고리즘으로는 가장 짧은 간선부터 연결하는 크루스칼 알고리즘이 있다. 문제 : 총 몇개의 동전을 거슬러줘야되는가? => 최소값을 구하라 풀이 : 가장 큰 단위부터 거슬러줄 수 있다면 거슬러 주는 것이 동전을 가장 적게 사용하는 방법일 것이다. #include using namespace std; //총 몇개의 동전을 거슬러 줘야되는가 int main() { int n, result = 0; cin >> n; result += n / 500; n %= 500; //나머지 연산을 해서 다음 레이어로 간다. result += n / 100; n %= 100; result += n / 50; .. 2020. 12. 29. [기본문제풀이] rabin karp 알고리즘 풀이 일시 : 2020-08-22 라빈카프 알고리즘 : 문자열 매칭 알고리즘으로 해시기법을 이용한다. 충돌하는 경우에는 포인터를 이용해 연결자료구조(link)를 이용해 해결한다. 문제 : 라빈카프 알고리즘을 이용하여 "ababacabacaabacaaba" 에서 "abacaaba"의 시작점을 찾아라 풀이 : #include #include using namespace std; void hashs(string parent, string pattern) { int parentHash=0, patternHash=0, power = 1; int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i 2020. 12. 28. [기본문제풀이] KMP알고리즘 풀이 일시 : 2020-08-21 KMP알고리즘 : Knuth Morris Pratt 알고리즘 / 대표적인 문자열(string)매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘 문제1 : 일반 문자열 매칭 알고리즘 (KMP알고리즘 X) 풀이 : BCDEF가 있고 그 중 DE를 찾을거면 자리를 하나씩 옮기며 비교하면서 매칭한다. O(N*M) #include using namespace std; int findString(string parent, string pattern) { int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i ABCDABEDFS 에서 ABE를 찾고자.. 2020. 12. 28. [기본문제풀이] bipartite matching 풀이 일시 : 2020-08-21 이분매칭 : A집단이 B집단을 선택하는 방법에 대한 알고리즘 효과적으로 집단을 매칭해준다. (최대매칭) 문제 : 연결될 수 있는 쌍을 나타내고 그 중 최대 매칭을 계산 후 매칭 된 것을 나타내자 풀이 : DFS로 풀이 가능 dbstndi6316.tistory.com/64?category=953968 [기본문제풀이] DFS 깊이우선탐색 풀이일시 : 2020-08-30 DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http:// dbstndi6316.tistory.com #include #include #define MAX 101 .. 2020. 12. 28. [기본문제풀이] network flow 풀이 일시 : 2020-08-17 네트워크 플로우 : 특정한 지점에서 다른 지점으로 데이터가 얼마나 흐르는가를 따지는 것 유량/ 용량 으로 용량보다 더 많이 보낼수는 없다. BFS를 이용해서 단순히 모든 경우의 수를 탐색해주자 1. 현재 흐르는 유량을 0으로 초기화 2. 정해진 용량안에서 가능한!! 최대 용량의 양을 반복적으로 더해준다. 3. 음의 유량을 계산해준다. (반대로 가는 유량) -> 빼준다면 다른것이 그 길로 또 갈수 있기 때문 (남은 경로를 더 찾을 수도 있다.) 문제 : 음의 유량 따져서 최대 유량을 구하라 풀이 : #include #include #include #include #define MAX 100 #define INF 1000000000 using namespace std.. 2020. 12. 28. 이전 1 2 3 4 다음 반응형
