알고리즘 공부를 하는 중에 그래프 탐색 파트를 공부하기 시작해서 짚고 넘어가는 것이 좋겠다고 생각하여 DFS와 BFS를 알아보고, 파이썬으로 구현까지 해본다. DFS (Depth-First Search) 깊이 우선 탐색이라고 부르고 그래프에서 깊은 부분을 우선 탐색하는 알고리즘이다. 갈 수 있는 한 맨 밑까지 탐색하여 리프노드(맨 아래 노드)를 방문하고, 이전 갈림길에서 선택하지 않은 노드들을 방문하는 식으로 탐색한다. 방문 위치를 기록 하는 스택을 이용하여 해결 할 수 있다. 또는 재귀로 해결 할 수 있다. 스택 방식 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 배열에 방문 했다고 표시한다. 스택의 최상단 노드에 방문 하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리를 한다. 만약..
버블 정렬의 시간 복잡도는 O(N^2)이다. 버블 정렬 알고리즘을 C언어로 작성 한 것이다. #include int main(void) { int i, j, temp; int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; for(i = 0; i array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } for(i = 0; i < 10; i++) { printf("%d ", array[i]); } return 0; } 백준 11931번 문제는 이런식으로 해결 할 수 있습니다. htt..
선택 정렬 알고리즘의 시간 복잡도는 O(N^2)이다. 선택 정렬 알고리즘을 C언어로 작성 한 것이다. #include int main(void){ int i, j, min, index, temp; int array[10] = {1, 10, 5, 8, 7 , 6, 4, 3, 2, 9}; for(i = 0; i array[j]) { min = array[j]; index = j; } } temp = array[i]; array[i] = array[index]; array[index] = temp; } for(i = 0; i
for문 구현문제인 별찍기이다. 1-2학기 중간고사 대비를 위해 문제를 풀어보았다. 안이 채워지지 않은 직사각형 구현하기 #include int main() { int n; scanf_s("%d", &n); for (int i = 1; i i * 2 + 1; j--) { printf("*"); } printf("\n"); } } 1~n까지 한줄에 출력하기, 숫자가 커지면 커진만큼 숫자 출력 #include int main() { int n; scanf_s("%d", &n); for (int i = 1; i n / 2) { for (int j = 0; j i * 2 + 1; j--) { if (n*2 ==..
유클리드 알고리즘(Euclidean algorithm)은 2개의 자연수의 최대공약수를 구하는 알고리즘입니다. 비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘입니다. ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8 라고 한다..... c언어로 알고리즘을 파악해보자. (C프밍 과제) 먼저 최소 공약수 알고리즘이다. 1. 두 수를 입력 받는다. 2. 두 수중 큰 수를 x, 작은 수를 y라고 한다. 3. y=0이면 최대공약수는 x이며 프로그램을 종료한다. 4. r = x % y 5. x = y 6 y = r ..
