개발윗미

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

큐 또한 스택과 같이 자료를 표현하고 처리하는 방법인데 큐는 입구와 출구가 다르기 때문에 은행 창구와 같이 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조이다. 빈 큐가 있다고 가정하고, 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 =..

C로 구현한 2752번 세수정렬 구하기 문제 풀이입니다. https://www.acmicpc.net/problem/2752 2752번: 세수정렬 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. www.acmicpc.net #include int main() { int input[3]; int min, index, temp; for(int i=0; i

C로 구현한 2750번 수 정렬하기 문제 풀이입니다. https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include int main() { int input[1001]; int num, min, index, temp; scanf("%d", &num); for(int i=0; i

퀵정렬은 특정한 배열이 있을 때 그 배열의 원소들을 반복적으로 분할하는 것이다. 즉, 퀵정렬은 특정한 피벗값(기준값)을 기준으로 왼쪽과 오른쪽으로 나누기 때문에 '분할 정복'이라고도 부른다. [퀵 정렬의 시간 복잡도] 퀵 정렬의 시간 복잡도는 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 -->..