알고리즘 공부를 하는 중에 그래프 탐색 파트를 공부하기 시작해서 짚고 넘어가는 것이 좋겠다고 생각하여 DFS와 BFS를 알아보고, 파이썬으로 구현까지 해본다. DFS (Depth-First Search) 깊이 우선 탐색이라고 부르고 그래프에서 깊은 부분을 우선 탐색하는 알고리즘이다. 갈 수 있는 한 맨 밑까지 탐색하여 리프노드(맨 아래 노드)를 방문하고, 이전 갈림길에서 선택하지 않은 노드들을 방문하는 식으로 탐색한다. 방문 위치를 기록 하는 스택을 이용하여 해결 할 수 있다. 또는 재귀로 해결 할 수 있다. 스택 방식 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 배열에 방문 했다고 표시한다. 스택의 최상단 노드에 방문 하지 않은 인접 노드가 있으면 해당 노드를 스택에 넣고 방문 처리를 한다. 만약..
협업 해야 할 일들이 점점 생겨나면서 Git flow정도는 기본적으로 알아 둬야 차질 없이 개발 할 수있을 거 같은 느낌을 받았다. Git으로 협업 하는 것이 왜 좋은지 Git Flow에 대한 개념이 뭔지 알아보자. git-flow는 Vincent Driessen의 branching model을 적용하여 저장소를 관리 해주도록 하는 확장된 방법론을 의미한다. Branch는 feature - develop - release - hofixes - master로 나누어 코드를 관리하는 전략을 말한다. master (main) 사용자에게 배포 되고, 기준이 되는 브랜치를 의미한다. master 브랜치의 HEAD에는 소프트웨어의 최신 배포판의 소스코드 버전이 들어있다. 배포 해도 될 만큼 안정성있는 코드들만 병합..
버블 정렬의 시간 복잡도는 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 ..
