알고리즘/이론 (16) 썸네일형 리스트형 깊이우선탐색 (Depth First Search) DFS는 자기가 방문했던 자취를 기억하는 스택의 특징을 이용하여 인적한 노드부터 차례대로 그래프를 순회하는 방법이다. 주어진 그래프에서 1부터 DFS를 한다고 예시를 들어보자. 여기에서는 더 작은 숫자가 먼저 탐색한다고 가정하면,2와 6중에서 2를 먼저 방문하게 된다. 2에서 다시 DFS를 시행하는데, 방문할 노드가 3과 6이 있으므로더작은 3을 방문하게 되고, 3에서 DFS를 다시 시행하여 4를 방문하고, 4에서 다시 DFS를 해서 5를 방문한다.이제 5에서 더 방문할 곳이 없기 때문에 그 동안 왔던 순서 대로5 --> 4 --> 3--> 2 로 돌아간다. 2로 다시 돌아와서 DFS를 하면 3과 6을 탐색하려고 하는데,3은 이미 방문한 노드이기 때문에 6을 방문한다. 6까지 방문하고 6에서 DFS를 해.. [DP-예제 2] 숫자 만들기 입력 N 과 M 이 주어지면, 1~M 까지 숫자를 더하여 N을 만드는 경우의 수를 구해보자.5와 3 같은 경우는 1~3의 숫자를 임의로 골라 더해서 5를 만드는 경우의 수를 구하는 것이다. 숫자 1~3을 가지고 더해서 5를 만드는 경우의 수를 따지면 위와 같이 13가지가 나온다.이제 문제를 해결하기 위해서 부분 문제를 정의해야 한다.동적 계획법으로 기준을 세우기 위에서 마지막 숫자를 기준으로 3가지로 나눌 수 있다.① 마지막에 숫자 1을 더하는 경우② 마지막에 숫자 2를 더하는 경우③ 마지막에 숫자 3을 더하는 경우 세분류로 나눈 것들이 뜻하는 것은 이렇게 해석 할 수 있다.① 마지막에 숫자 1을 더하는 경우 -> 5에서 1을 뺀 나머지 부분에서 4를 만들어야 한다.② 마지막에 숫자 2를 더하는 경우 -.. [DP-예제 1] 블럭채우기 동적 계획법의 예제인 블록채우기에 대해서 공부하면서 DP를 공부해 보자.세로 길이가 2 이고, 가로 길이가 N 인 블럭에 세로 2, 가로 1의 블럭을 채우는 경우의 수를 구하는 예제이다.쉬운 이해를 위해서 입력 N 이 4일 때(가로 길이가 4) 블럭을 채우는 경우의 수는 5이다. 블럭을 채우는 방법을 보면 이러한 식으로 채울 수 있는 방법이 생각해 보면 5가지가 있다.그런데 이 문제를 코딩으로 어떻게 해결 할 수 있을까? 블럭 채우기 알고리즘을 세울려면 먼저 전체 경우를 어떻게 나눌 것인지 생각해야 한다.이 부분이 동적 계획법에서 가장 생각 해 내기 어려운 부분 문제를 정의하는 과정이다. 모든 경우의 수를 보면 위와 같은데, 어떻게 기준을 세우냐면 가장 마지막에 들어가는 블럭을 본다.그러면 1개가 세로로.. 동적 계획법 (Dynamic Programming) 동적 계획법 (Dynamic Programming) 은 각 단계에서 해결해야 할 일련의 문제들이 상호 관련성을 맺고 있을 경우에, 어느 단계에서 하나의 결정이 이루어지면 그 결정은 그 다음 단계의 문제를 결정하는 데 영향을 미치게 되고 그 결과 달성하고자 하는 목표에도 영향을 미치게 되기 때문에 이러한 문제를 해결하기 위해서 필요한 알고리즘이다. 대표적인 예로 [피보나치 수] 가 있다. 피보나치 수는 1 1 2 3 5 8 ... 형식으로 이루어져 있는 수열을 의미하는데,초기값인 첫번째 항과 두번째 항은 1이고, n-2 번째 항과 n-1 번째 항을 더해서 n번째 항을 구한다.n 번째 피보나치 수열을 구하는 코드는 위와 같다. 하지만 피보나치 수를 구하는 알고리즘을 위의 코드 같이 재귀적으로 짜면 문제가 발.. 분할정복법 (Divide & conquer) 분할정복법은 문제를 여러 개로 분해하여 해결한 후 풀린 부분 문제들을 거꾸로 조합하여 원래의 문제를 푸는 방식이다.대표적인 예로 합병, 퀵 정렬이 있는데, 합병 정렬에서는 정렬을 반으로 나눠서 숫자를 비교해서 합치는 것이 분할정복법의 원리라고 할 수 있고,퀵정렬도 마찬가지로 pivot 보다 작은 왼쪽부분, pivot 보다 큰 오른쪽 부분을 구해서 pivot 의 자리를 찾아가는 과정이 분할정복법이라 할 수 있 다. 출처 : Algorithm LABS 이진탐색 (binary search) (1) 재귀적 구현 이진탐색은 처음부터 끝까지 한개씩 확인하면서 찾는 선형탐색의 시간복잡도 보다 훨씬 빠른 의 시간복잡도를 가지고 있는 함수다. 하지만 이진탐색의 시간복잡도가 의 성능을 가지려면 전제조건이 필요한데, 배열이 정렬 되어있어야 한다. 이진탐색은 정렬되있는 배열에서 중간값을 확인하여 중간값보다 작으면 작은쪽을, 크면 큰쪽에서 다시 이진탐색을 수행하는 탐색이다. 이진탐색의 재귀적과 비재귀적 두가지 방법으로 구현할 수 있는데, 여기에선 재귀적으로 구현을 해볼것이다. 이미지 출처 : https://anster.tistory.com/152 위의 사진에서 만약에 내가 찾는 숫자가 76이라고 가정해보자. 1. 처음에 중간값 47을 찾고 47은 내가 찾는 76보다 작기 때문에 오른쪽에서 다시 이진탐색을 한다. 47보다 작은 .. 퀵정렬 (quick sort) 퀵정렬도 합병정렬과 마찬가지로 시간복잡도가 으로 빠르게 정렬할 수 있는 효율적인 정렬이다. 이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=hero1014&logNo=20191727330&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dimages%26cd%3D%26ved%3D2ahUKEwjX0NO0upzgAhUx7GEKHbbxC8AQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252Fhero1014%252F20191727330%26psig%3DAOvVaw2SoIOMtqZXX83.. 합병정렬 (merge sort) 선택, 삽입, 버블정렬의 시간 복잡도는 이지만 합병정렬의 시간 복잡도는 으로 더 빠르게 정렬할 수 있다. 합병정렬의 절차를 그림으로 보게 되면 이렇게 된다. 이미지 출처 : https://m.blog.naver.com/PostView.nhn?blogId=itperson&logNo=220833815418&categoryNo=89&proxyReferer=http%3A%2F%2Fwww.google.co.kr%2Furl%3Fsa%3Di%26rct%3Dj%26q%3D%26esrc%3Ds%26source%3Dimages%26cd%3D%26ved%3D2ahUKEwitzbP5upzgAhWXMt4KHYBVCpQQjRx6BAgBEAU%26url%3Dhttp%253A%252F%252Fm.blog.naver.com%252FP.. 이전 1 2 다음
