알고리즘 공부를 하는 중에 그래프 탐색 파트를 공부하기 시작해서 짚고 넘어가는 것이 좋겠다고 생각하여 DFS와 BFS를 알아보고, 파이썬으로 구현까지 해본다. DFS (Depth-First Search) 깊이 우선 탐색이라고 부르고 그래프에서 깊은 부분을 우선 탐색하는 알고리즘이다. 갈 수 있는 한 맨 밑까지 탐색하여 리프노드(맨 아래 노드)를 방문하고, 이전 갈림길에서 선택하지 않은 노드들을 방문하는 식으로 탐색한다. 방문 위치를 기록 하는 스택을 이용하여 해결 할 수 있다. 또는 재귀로 해결 할 수 있다. 스택 방식 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 배열에 방문 했다고 표시한다. 스택의 최상단 노드에 방문 하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리를 한다. 만약..
선택 정렬 알고리즘의 시간 복잡도는 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 ..