개발윗미

깊이 우선 탐색은 특정한 데이터를 탐색할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 즉, 깊이 우선 탐색은 데이터를 보다 깊은 것을 우선으로 하여 탐색한다. 깊이 우선 탐색은 스택을 이용하는데, 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에 스택을 사용하지 않고 단순히 재귀함수만을 사용해서도 구현이 가능하다. 그림과 같이 스택의 최상단 노드를 확인하고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문처리한다. 그림에 대해 구체적으로 설명하자면, (1) 먼저 스택에 시작 노드인 1을 삽입하고 방문처리한다. (2) 1과 인접한 노드 중 방문하지 않은 2를 스택에 삽입하고 방문처리한다. (3) 2와 인접한 노드 중 방문하지 않은 3을 스택에 삽입하고 방문처리한다. ..

너비 우선 탐색은 특정한 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 즉, 어떠한 시작점이 있을 때 그 시작점과 가까운 것을 우선으로 탐색을 한다. 너비 우선 탐색은 큐를 이용하는데, 큐는 먼저 들어온 데이터가 먼저 나간다는 점에서 너비 우선 탐색이 가능하도록 해준다. 그림과 같이 큐에서 하나의 노드를 꺼내고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 방문한다. 그 후 순서대로 큐에 값을 삽입하는 과정을 반복한다. 그림에 대해 구체적으로 설명하자면, (1) 먼저 큐에서 1을 꺼낸다. (2) 1과 인접한 노드 중 방문하지 않은 2와 3을 방문처리한다. (3) 2를 꺼내고 2와 인접한 노드 중 3은 이미 방문했기 때문에 넘어가고 방문하지 않은 4와 5를 방문처리한다. ..

큐 또한 스택과 같이 자료를 표현하고 처리하는 방법인데 큐는 입구와 출구가 다르기 때문에 은행 창구와 같이 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. 빈 큐가 있다고 가정하고, push(1) --> 1 --> 맨 처음 1을 삽입한다. push(2) --> 1 2 --> 2를 삽입한다. push(7) --> 1 2 7 --> 7을 삽입한다. pop() --> 2 7 --> 가장 먼저 들어간 1이 나간다. push(4) --> 2 7 4 --> 4를 삽입한다. pop() --> 7 4 --> 가장 먼저 들어간 2가 나간다. [예제] #include #include using namespace std; int main() { queue q; q.push(7); q.push(5); q.push(4)..

스택은 자료를 표현하고 처리하는 방법인데 입구와 출구가 하나밖에 없는 상태이기 때문에 택배 상하차와 같이 가장 나중에 들어온 데이터가 가장 먼저 나온다. 빈 스택이 있다고 가정하고, push(1) --> 1 --> 맨 처음 1을 삽입한다. push(2) --> 1 2 --> 2를 삽입한다. push(7) --> 1 2 7 --> 7을 삽입한다. pop() --> 1 2 --> 가장 마지막에 들어간 7이 나간다. push(4) --> 1 2 4 --> 4를 삽입한다. pop() --> 1 2 --> 가장 마지막에 들어간 4가 나간다. [예제] #include #include using namespace std; int main() { stack s; s.push(7); s.push(5); s.push(4)..

계수 정렬은 크기를 기준으로 개수를 세는 것이며, 범위조건이 있는 경우에 한해서 사용된다. 5이하의 자연수 데이터들이 있다고 가정할 때, 계수 정렬은 배열 첫번째 요소부터 시작하여 해당 값이 등장할 경우 개수를 하나씩 증가시킨다. 1, 3, 2, 4, 3, 2, 5 --> 1개, 0개, 0개, 0개, 0개 1, 3, 2, 4, 3, 2, 5 --> 1개, 0개, 1개, 0개, 0개 1, 3, 2, 4, 3, 2, 5 --> 1개, 1개, 1개, 0개, 0개 1, 3, 2, 4, 3, 2, 5 --> 1개, 1개, 1개, 1개, 0개 1, 3, 2, 4, 3, 2, 5 --> 1개, 1개, 2개, 1개, 0개 1, 3, 2, 4, 3, 2, 5 --> 1개, 2개, 2개, 1개, 0개 1, 3, 2, 4,..

힙정렬은 힙 트리 구조를 이용하는 정렬 방법이다. 여기서 힙 트리 구조는 최소값이나 최대값을 신속하게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리이다. 최대 힙은 부모노드가 자식노드보다 값이 큰 힙이다. (1) 부모노드인 7이 자식노드인 5와 3보다 크다. (2) 부모노드인 11이 자식노드인 9와 8보다 크다. (3) 부모노드인 9가 자식노드인 7과 4보다 크다. ==> 그러므로 두 트리 모두 최대 힙이다. [오름차순 정렬] 위 그림들은 오름차순 정렬을 수행하기에 앞서 최대 힙을 구성한 것입니다. 부모노드가 자식노드보다 작을 경우 값을 바꿔줌으로써 부모노드의 값이 더 크게 구성해줍니다. 이제 오름차순 정렬을 수행하는데 트리를 반으로 나눈 후 가장 최상위에 있는 루트노드 값을 가장 뒤쪽으로 보내면서..

병합정렬은 원소들을 반으로 나누고 계산(정렬)한 후 나중에 합치는 것이다. 배열 {7,6,5,8,3,5,9,1} 이 있다고 가정하였을 때 오름차순으로 정렬을 시도한다면, 7 6 5 8 3 5 9 1 --> 크기가 1인 배열로 개별적으로 나눈다. 7 6 5 8 3 5 9 1 --> 67 58 35 19 --> 2개씩 묶도록 하며, 각각의 정렬 처리를 한다. 67 58 --> 5678 --> 67과 58을 비교하여 정렬 처리를 한다. 35 19 --> 1359 --> 35와 19를 비교하여 정렬 처리를 한다. 5678 1359 --> 13556789 --> 5678과 1359를 비교하여 정렬 처리를 한다. => 최종적으로 1 3 5 5 6 7 8 9 가 이루어진다. [예제] #include int num =..

퀵정렬은 특정한 배열이 있을 때 그 배열의 원소들을 반복적으로 분할하는 것이다. 즉, 퀵정렬은 특정한 피벗값(기준값)을 기준으로 왼쪽과 오른쪽으로 나누기 때문에 '분할 정복'이라고도 부른다. [퀵 정렬의 시간 복잡도] 퀵 정렬의 시간 복잡도는 O(N * logN) 이다. 예를 들어, 1 2 3 4 5 6 7 8 9 10 와 같이 10개 수가 존재할 때 선택 정렬을 사용하게 되면 O(N^2) 이기 때문에 10 * 10 = 100 이 나온다. 하지만, 퀵 정렬을 사용하면 1 2 3 4 5 와 6 7 8 9 10 으로 분할하여서 N^2 이라고 했을 때 (5 * 5) + (5 * 5) = 50 이 나오기 때문에 결과적으로 훨씬 적은 수만큼 연산을 수행하게 된다. 이렇게 수를 반으로 나누는 과정은 2씩 계속 나눈..

삽입정렬은 각 원소를 필요할 때만 적절한 위치에 삽입하는 것이다. 1 10 5 8 7 6 4 3 2 9 --> 가장 앞에 있는 1이 가장 작은 수이기 때문에 넘어간다. 1 10 5 8 7 6 4 3 2 9 --> 10은 앞에 있는 원소인 1보다 크기 때문에 유지하고 넘어간다. 1 10 5 8 7 6 4 3 2 9 --> 1 5 10 8 7 6 4 3 2 9 --> 5는 앞에 있는 원소 중 1과 10 사이에 들어가야 적절하기 때문에 삽입한다. 1 5 10 8 7 6 4 3 2 9 --> 1 5 8 10 7 6 4 3 2 9 --> 8은 앞에 있는 원소 중 5와 10 사이에 들어가야 적절하기 때문에 삽입한다. . . . 1 2 3 4 5 6 7 8 10 9 --> 1 2 3 4 5 6 7 8 9 10 -->..

버블정렬은 옆에 있는 원소와 비교하여 더 작은 값을 계속해서 앞으로 보내는 것이다. [수행1] 1 10 5 8 7 6 4 3 2 9 --> 1과 10을 비교하고 1이 더 작기 때문에 넘어간다. 1 10 5 8 7 6 4 3 2 9 --> 1 5 10 8 7 6 4 3 2 9 --> 10과 5를 비교하고 5가 더 작기 때문에 앞으로 옮긴다. 1 5 10 8 7 6 4 3 2 9 --> 1 5 8 10 7 6 4 3 2 9 --> 10과 8을 비교하고 8이 더 작기 때문에 앞으로 옮긴다. 1 5 8 10 7 6 4 3 2 9 --> 1 5 8 7 10 6 4 3 2 9 --> 10과 7을 비교하고 7이 더 작기 때문에 앞으로 옮긴다. . . . 1 5 8 7 6 4 3 2 10 9 --> 1 5 8 7 6 ..