본문 바로가기

알고리즘

 (4)
[JAVA] DFS (Depth-Frist Search) 깊이 우선 탐색 DFS (Depth-Frist Search) DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. DFS는 스택 자료구조(혹은 재귀 함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. 탐색 순서 : 1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5 import java.util.ArrayList; public class Main { public stati..
[C언어] 정렬 알고리즘 (삽입정렬, 퀵정렬, 합병정렬) 정렬 알고리즘 중 삽입정렬, 퀵정렬, 합병정렬에 대해 알아보자. 1. 삽입정렬(Insertion sort) 삽입정렬은 정렬된 수와 정렬할 수를 나누어서 모든 수가 정렬된 수가 될 때까지 과정을 반복하는 알고리즘이다. 삽입정렬의 과정은 다음과 같다. 1. 정렬된 수와 정렬할 수로 섹션을 나눈다. (처음에는 정렬된 수가 없기 때문에 가장 정렬할 수의 가장 첫 번째 수를 둔다.) 2. 정렬할 수를 들어 올려서 (실제로 들어 올리는 건 아니지만 그렇다고 생각하고) 정렬된 수와 비교한다. 정렬된 수보다 작으면 정렬된 수를 한 칸 뒤로 보내고 그 자리에 들어 올린 수를 둔다. 비교가 끝나면 그 수는 정렬된 수에 포함된다. 3. 모든 수가 정렬된 수가 될 때까지 위 과정을 반복한다. 참고 유튜브 링크: https:/..
[C언어] 정렬 알고리즘 (버블정렬, 선택정렬) 컴퓨터는 한 번에 두 개의 수만 비교할 수 있다. 컴퓨터상에서의 대표적인 정렬방법인 버블정렬과 선택정렬에 대해 알아보자. 1. 버블정렬 버블정렬의 과정은 다음과 같다. 1. 첫 번째 숫자와 두 번째 숫자를 비교한다. 더 작은 수가 앞에, 큰 수가 뒤에 오도록 위치를 바꾼다. 2. 두 번째 숫자와 세 번째 숫자를 비교한다. 3. 세 번째 숫자와 네 번째 숫자를 비교한다. . . . 4. 마지 막번째 수를 비교할 때까지 위 과정을 반복한다. . 5. 위 과정을 마치면 제일 큰 수가 맨 뒤로 가있을 것이다. 그러면 잘 정렬된 맨뒤의 수를 빼고 나머수들로 위 과정을 반복한다. 더 이상 비교할 나머지 수가 없으면 정렬 끝! #include int main(void) { int arr[10] = { 10, 8, 3..
[C언어] 탐색 알고리즘 (순차탐색, 이진탐색) 알고리즘이란? 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것. 한마디로 문제 해결방법을 공식화한 형태라고 할 수 있다. 탐색 알고리즘에 대해 알아보자. 1. 순차탐색 배열의 순서대로 확인하면서 값을 찾는 방법이다. 매우 단순한 탐색방법이며 웬만하면 이 방법을 사용한다고 한다. 그러나 찾는 값이 맨 끝에 있다면 모든 값을 다 비교해야 하기 때문에 비효율적이다. #include int main(void) { int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int key = 8; int index; for (int i = 0; i < 10; i++) { if (key == arr[i]) index = i; } printf("%d는 a..

티스토리툴바