코딩 소양 (24) 썸네일형 리스트형 [BFS & DFS]BFS(Breadth First Search) 저번에 *DFS*에 대해서 공부하였으니까, 이번엔 BFS에 대해서 공부해봅시다.저번에 봤던 것 처럼 BFS는 Breadth First Search라고 너비 먼저 탐색알고리즘이 되겠습니다. BFS는 그럼 어떤 장단점이 있을까요???BFS는 넓게 탐색하기 때문에 최단 경로를 찾는데에 용이합니다만,목적지까지 모든 경우가 비슷한 거리를 가지면 안 좋을 수 있고, DFS와 마찬가지로 메모리 overflow가 일어날 수 있습니다(탐색 범위가 크면). DFS를 봤던 것 처럼 BFS도 tree부터 살펴봅시다!!! BFS 그림을 보니까 이해가 되시나요??? 이번엔 DFS와 다르게 자식들을 먼저 탐색하네요!!! 우물을 넓게 파는 알고리즘!?!?!? graph에서 보면 다음과 같습니다. 그림을 보면 이해가되시나요?? 위에 .. [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.. [백준 알고리즘] 1026번 보물(정렬) 이번에 풀어볼 문제는 정렬을 활용한 문제로 백준의 1026번 보물 문제입니다. 문제는 여기 문제를 간단하게 보면 두 배열의 각 성분의 곱의 합(S = A[0]xB[0] + A[1]xB[1] + …)이 최소가 되도록 하는 거래네요. 풀이는 너무 간단하게..! 큰거에 작은거 곱해서 작게 만드는 것..!!! 간단..ㅎㅎ 저는 A를 오름, B를 내림차순 정렬해서 문제를 해결했습니다. 정렬 알고리즘은 퀵정렬을 사용해서 풀었습니다. 이건 제가 정리해본 정렬 알고리즘 글입니다..ㅎㅎ필력 제로..ㅠㅠ 제가 쓴 정렬 알고리즘ㅎㅎ - 선택,삽입정렬 제가 쓴 정렬 알고리즘ㅎㅎ -병합정렬 제가 쓴 정렬 알고리즘ㅎㅎ - 퀵정렬 코드는 다음과 같습니다!(C++사용했습니다.) #include using namespace std; .. [정렬 알고리즘 - 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를 잡고 그 전의 성분들을 비교해가면서 정렬을 해주는 알고리즘!! 코드도 매우 간단합.. [프로그래머스] 다음 큰 숫자 찾기 이번에 풀어본 문제는 프로그래머스의 다음 큰 숫자문제입니다. 문제 url은 이거입니당 문제 n의 다음 큰 숫자라는건 n보다 큰 수 중에 2진수로 변환했을 때 n과 1의 개수가 동일한 것 중 가장 작은 수를 말합니다. 처음 문제를 보고 바로 생각난건 당연히 while… 알고리즘을 풀다 보면 뭔가 실행 시간 때문에 단순하게 생각난걸 사용하기가 꺼려지는..ㅠㅠ 그래도 만점이 나오네요!!! 처음 while을 사용한 것을 배척하고 조사해본 방법은 bit operation를 사용한 방법입니다. 역시 STL이건 뭐건 가장 중요한건 기초 지식인 듯... 사용한 bit operation의 특징은 숫자 n이 있으면 n-1과 and 연산을 하는 방법입니다. n&n-1을 하게 되면 LSB에 가까운 1이 없어지게 되는데, 이렇.. [프로그래머스] 올바른 괄호 찾기 이번에 풀어본 문제는 프로그래머스의 올바른 괄호 찾기문제입니다. 오랜만에 알고리즘을 푸니까 감이 하나도 안잡히네요..ㅠㅠ 문제 url은 이거입니당 문제 문제를 설명하자면 소괄호로만 이루어진 문자열이 있는데 이 문자열의 괄호가 올바르게 되어있는지 체크하는 문제입니다!! 막상 처음 봤을때 감이 하도 안잡혀서 뭘까...하다가 stack, queue로 푸니까 금방 풀더라구요..ㅎㅎ 풀이법은 ’(‘가 나올때만 push를 해주고 ‘)’를 다시 만나면 pop해주는 방법!을 사용했습니다. 물론 예외처리로 “))))))”이런 경우도 생각해야겠죠? 그래서 변수 하나를 두고 최초 빈 공간이었는지에 대한 지표를 설정해주었어요. 코드는 이렇게~ #include #include #include using namespace std.. 이전 1 2 3 다음
