코딩 소양/알고리즘 ㅠ (12) 썸네일형 리스트형 [BFS & DFS] DFS(Depth First Search) 이번에는 DFS, BFS에 대해서 공부해보겠습니다. 두 알고리즘은 graph를 탐색한는 알고리즘인데.. 먼저 의미하는게 무엇인지..!? DFS Depth First Search 깊이 먼저 탐색BFS Breadth First Search 너비 먼저 탐색 오호! 깊이와 너비의 차이가 있네요ㅎㅎ 이번 페이지에서는 DFS만 보고 다음 페이지에서 BFS를 해보겠습니다.ㅎㅎㅎ DFS의 장단점은 어떤거가 있을까요???DFS는 깊이있게 먼저 탐색하기 때문에 엄청 넓은 tree, graph에서 탐색에 용이하다는 점을 가지고 있습니다.하지만! (뒤에서 나오겠지만) stack을 사용하기 때문에 너무 깊게 들어가다보면 overflow가 일어날 수 있다는 거죠.보통 DFS는 Cycle Detection에 사용됩니다. 전 gra.. [정렬 알고리즘 - 3]퀵 정렬(Quick Sort) Quick Sort 다음은 정렬 알고리즘 이름부터 빠른 Quick Sort입니다. Quick Sort는 빠른 알고리즘으로 O(NlogN)의 시간복잡도를 가지는 알고리즘인데요 한번 알아봅시다. 먼저 Quick Sort의 구동 방식을 말로 설명하자면 이러합니다. pivot(기준점)을 기준으로 양 끝점(0,n이겠죠 보통)에서 비교를 시작한다(오름차순인 경우 오른쪽이 pivot보다 커야하고, 왼쪽이 작아야 합니다.) 비교하면서 pivot과 값을 비교하고 값을 정렬하면서 중간쪽으로 온다. 왼쪽(0)에서 시작한 기준점이 오른쪽(n)에서 시작한 기준점보다 커지게 되면 왼쪽에서 시작한 기준점을 기준으로 pivot을 정하고 다시 정렬한다. 무슨말인지 잘 모를 수가 있습니다. 동영상으로 보면 완전 이해가 잘 되는데 제가 .. [정렬 알고리즘 - 2] 병합 정렬(Merge Sort) 병합 정렬(Merge Sort) 이번에 알아볼 정렬 알고리즘은 Merge Sort 입니다. Merge Sort는 정렬할 배열을 최소 단위로 분할 후에 정렬을 하는 알고리즘인데요. 그림으로 보면 무슨 뜻인지 알 수 있습니다. 처음 병합 정렬이라고 하면 느낌이 오지 않더라구요. 저도 처음 강의자료로 봤는데 뭔소린가 싶어서..ㅋㅋ 이리저리 찾아보니까 쪼개고 합치는거로... 그러면 코드로 만든다면 어떻게 만들까요!?!? 정답은 recursive에 있습니다! 먼저 절차를 한번 잘 생각해봅시다. 배열을 반으로 잘게잘게 쪼개버린다. 다시 합쳐버린다. 간단하게 쪼개는 함수를 sort라고 하고 합치는 함수를 merge라고 하고 pseudo code를 써보면 이렇게 나타낼 수 있겠죠. 배열 A와 길이 n이 있다고 하고, .. [정렬 알고리즘 - 1] 삽입정렬(Insertion Sort), 선택정렬(Insertion Sort) Insertion Sort(삽입 정렬) 먼저 알아볼 정렬 알고리즘은 삽입 정렬(Insertion Sort) 입니다! 말그대로 두 수를 비교해서 조건(크거나 작거나)에 맞으면 사이에 끼워 넣는(삽입)하는 알고리즘입니다. 그림으로 보면 바로 알 수 있어요! 그림에서 보면 기준점(노란색)을 정하고 앞으로 비교하면서 맞는 곳에 집어넣는 것을 알 수 있습니다. pseudo code로 보면 다음과 같습니다. A배열이 1~n까지 있을 때 정렬 for i= 2 ~ n key = A[i] j = i-1 while(j>0 && A[i] > key) A[j+1] = A[j] A[j+1] = key 매우 간단!!!! 코드를 보면 기준점 key를 잡고 그 전의 성분들을 비교해가면서 정렬을 해주는 알고리즘!! 코드도 매우 간단합.. 이전 1 2 다음
