공부/알고리즘 (15) 썸네일형 리스트형 [분할 정복] 분할 정복에 대해서 알아보자 분할 정복은 이름 그대로 문제를 작은 부분으로 쪼개어서 해답을 찾은 뒤에 작은 조각들을 합치면서 다시 해답을 찾아내가는 방식입니다. 대표적인 분할 정복 방식으로는 병합 정렬이 있습니다. 위 그림에서 보듯이 병합 정렬은 배열을 반씩 쪼개서 가장 작은 단위로 쪼갠 다음에 정렬하고, 이 정렬된 배열을 점차적으로 정렬하는 방식입니다. 분할 정복을 할 때 가장 중요하게 고려해야 할 점이 있습니다. 바로 조그만 조각에서 나온 최적해를 이용해서 구해나간 답이 결국 최종 해답과 일치해야 한다는 것입니다. 작은 조각에서 나온 답이 결국 더 큰 조각에서는 쓸모가 없어진다면 의미없는 일을 한 것이겠죠... 또 다른 예로는 행렬의 거듭제곱을 구하는 코드가 있습니다. 보통의 방법으로 행렬의 m 제곱을 구하게 되면, n x n의.. [정렬] 병합 정렬 ( Merge Sort) 오늘은 정렬 방법 중에 하나인 '병합 정렬'에 대해서 알아봅시다! 분할 정복에 대해 간단히 설명하면, 하나의 큰 덩어리를 작게 분할하여 해결하고, 이 작은 덩어리들을 묶어서 또 다시 해결을 하다보면 최종적으로 자신이 원하는 답을 찾는다는 것입니다. 어디서 많이 들었던 소리이지 않습니까?! 바로 재귀 함수에서 나왔던 개념입니다!따라서, 분할 정복은 재귀를 통해서 해결하는 경우가 많습니다. 어쨌든, 이 병합 정렬도 분할 정복을 통해 정렬하는 방법입니다. 방법은 간단합니다! 데이터를 한 조각이 남을 때까지 계속해서 쪼개고, 쪼개고, 또 쪼갭니다.그리고 쪼개진 것들끼리 정렬을 하고, 이를 이용해서 만들어진 조금 큰 조각을 또 정렬을 하는 방법입니다! 그림으로 확인해봅시다! 그림에서 처럼 우선 데이터를 반 씩 쪼.. [완전탐색/부분집합] 비트를 이용하여 모든 부분집합을 구하자! 부분 집합이란 전체의 집합에서 하나의 원소를 '고른다 / 안 고른다' 두 가지의 경우에 대해 살펴보는 것이므로 2^n 가지의 경우가 나옵니다. 이는 비트를 이용하면 굉장히 쉽게 구할 수 있습니다! 왜냐하면 비트는 이진수이기 때문에, 하나의 자리수마다 고른다 (1) / 안 고른다(0)을 설정할 수 있기 때문입니다! 우선 코드를 보겠습니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 #include#include#include int arr[10]; void print(int bit){ int idx = 0; while (bit) { if (bit & 1) { printf("%d ", a.. [완전탐색/순열] 재귀 함수로 순열을 짜보자! (크기 순서로) 재귀함수를 통해 순열을 짜는 방법을 알아보겠습니다.우선 예제로 주어진 수가 1 2 3 4 5일 때 을 구해봅시다. 어떻게하면 순열을 구할 수 있을까요? 바로, 앞의 3 자리를 순열의 결과로 보는 것입니다.보통 결과를 앞에 3자리에 위치시키기 위해 크게 2가지 방법이 있습니다. 1. swap을 이용한 방법2. 오른쪽으로 한칸씩 원형 회전 시키는 방법 1번의 경우에는 순열을 구하는 순서가 상관이 없을 때 사용합니다.2번의 경우는 순열을 구하는 순서가 정해져 있는 경우입니다. (특히 크기 순서로) 1번을 예로 보겠습니다.1 2 3 4 5가 있을 때,맨 앞자리를 처음에는 1로 한다.그리고 다음 2번째 수를 2로 하고,3번째 수를 3으로 하면, 1 2 3 순열이 만들어집니다.이제 3과 4를 swap해서 1 2 4.. [완전탐색] 완전탐색에 대해 알아보자 완.전.탐.색! 말 그대로 무식하게 모든 경우를 다 보는 것입니다!컴퓨터의 가장 강한 이점인 '속도'를 극한으로 이용할 수 있는 방법입니다.보통 완전 탐색은 최적화 문제에서 많이 사용합니다.최적화 문제란, 여러가지 경우를 만들 수 있을 때, 가장 적합한 답의 경우를 구하는 문제를 말합니다.예를 들면, 마을 사이를 잇는 도로가 있고 도로마다 거리가 다를 때, A에서 B로 가는데 가장 짧은 도로의 길이를 구하는 문제가 있습니다.이와 같은 문제를 풀 때 완전탐색을 이용하면 A에서 B로 가는 모든 도로의 경우를 구한 뒤에 그 중 거리가 가장 짧은 값을 답으로 선정합니다.물론, 완전탐색을 이용해서 문제를 풀기 위해서는 문제의 조건에서 주어진 시간 내에 풀 수 있을지 잘 생각해보아야 합니다.완전탐색을 너무 많이하면.. [완전탐색/조합] 비트 연산을 이용하여 조합 만들기 - 비트 조합 예전에 대학생활을 하면서 '로봇 연구회' 동아리 활동을 하면서 아트메가 128을 사용했기 때문에 비트연산을 이용한 경험이 있습니다. 덕분에 프로그래밍을 하면서 비트를 이용해서 문제를 해결한 적이 있는데, 이번에는 그 중에서도 특히 인상 깊었던 '조합 만드는 법'에 대해서 설명하려고 합니다! 우선, 그 전에 비트 연산에 대해서 간단히 알아봅시다. 1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다. ex) 0b 1111 & 0b 0011 = 0b 0011 2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.ex) 0b 1100 | 0b 1010 = 0b 1110 3. ~ : 모든.. [종만북] 소문의 책을 구입하다. 많은 개발자들의 컵라면 받침대로 사용되고 있다는 종만북!! 두께마저도 정말로 두꺼웠습니다. 1권 2권 합쳐서 약 1천 페이지 정도라서 꽤 놀랐습니다. 알고리즘을 배우기 위해 입문할 때 많이 읽는다고 소문을 많이 들었기 때문에 이번에는 이 책을 다 읽어보려고 합니다. 실은 책을 산 지는 꽤 되었지만! 블로그를 시작한 것은 얼마 안되었기에! 마치 처음 보는 것 처럼 얘기하겠습니다! 종만북 1권 보다는 먼저 2 권을 읽는 분들이 많은 것 같습니다. 일단은 목차를 보면서 '알고리즘' 위주로 볼 생각이지만, 아마 앞에서부터 읽을 것 같습니다. 종만북을 라면 받침대로는 절대 사용하지 않으리..! 참! 종만북에는 알고리즘을 설명하면서 그 알고리즘에 대한 문제도 다수 존재합니다. 이 문제들은 '알고 스팟'이라는 홈페이.. 이전 1 2 다음
