Stargazer

단순 합병 문제: 두 시퀀스 A, B를 오름차순으로 주어진다고 할때, 두 시퀀스를 하나로 합병한, 정렬된 시퀀스 C를 구하라(C 크기 = n) 합병 전략: A,B의 최소값 중 더 작은값을 C에 넣는데, 만약 최소값이 A 에 있다고 가정하면, A의 최소값을 C에 넣고, A의 나머지와 B, 그리고 C 를 재귀적으로 함수를 호출하여 합병을 한다.(분할 정복) 합병 수도코드: Merge(A,B,C) if(A is empty) rest of C = rest of B else if(B is empty) rest of C = rest of A else if (first of A

추가 공간을 일반 퀵소트보다 줄이는 알고리즘 추가 공간: $O(n)$->$O(1)$( 재귀적일때는 $O(lgn)$을 사용) 전략은 이전 퀵소트와 같이, 분할 정복을 이용할 것이다. 다만 공간을 추가적으로 사용하지않고, 해야하므로, 요소끼리 스위칭하는 방식으로 해야한다. In-place Quick sort 수도코드: Algorithm inPlaceQuickSort S, l, r Input sequence S , ranks l and r Output sequence S with the elements of rank between l and r rearranged in increasing order if l >= r return i

특징: Worst case에 대해서는 $O(n^2)$ 시간이지만, Average case 에 대해서는 $O(n\log n)$ 시간이 걸린다. 전략: Divide and Conquer(분할 정복): 큰 문제를 여러개의 작은 문제로 분할하여 재귀적으로 처리 후 합쳐서 해결하는 방법 *단계: 1. 분할: 작게 문제를 나눈다.(이때, 나눈 것도 해결전략이 동일한 문제여야한다.) 2. 정복: 재귀적으로 계속 작게 나누면서, 문제를 해결한다.(문제를 해결할 수 있는 가장 작은 단위 까지 나눔) 3. 조합: 해결한 문제들을 조합하여 원래 input에 대한 결과값을 리턴한다. * 분할 정복 알고리즘 수도 코드: solve(I) n=size(I) if(n

*자료구조 시간에 문제풀다가 배운 내용을 정리한 것입니다. 입력: 후위 순회한 결과와 그 노드의 깊이 출력: 전위 순회한 결과 예를 들어 후위 순회한 결과가 다음과 같이 주어 졌을때, 값: 5 2 8 9 10 6 7 3 4 1 깊이: 2 1 3 3 3 2 2 1 1 0 출력은 다음과 같다 1 2 5 3 6 8 9 10 7 4 트리를 그림으로 그리면 다음과 같다. #솔루션 우선 깊이의 개념을 이해해야한다. 깊이는 노드가 루트에서부터의 간선의 개수이다. 그리고 후위 순위는 가장 왼쪽 것부터 그리고 가장 깊이가 깊은 것부터 처리한다. 따라서 깊이의 변화로 이들의 관계가 무엇인지 알 수 있다. 우선 노드 1의 자식은 깊이가 1인 녀석들이다. 그래서 입력값으로부터 2 3 4 임을 알 수 있다. 여기서 더 내려가면..

군대컴에는 컴파일러를 깔수 없다 ????? 근데 어떻게 개발 했냐!! 윈도우7이상의 컴퓨터에는 .net framwork 가 내장 되어있었다!! 덕분에 짬짬이 만들었다 기간은 2주 정도 걸린것 같다 만든 코드를 다시 복사해서 인터넷으로 옮기는 작업은 일일이 손으로 타이핑 해야만 했다 그작업만 1시간 30분이 걸렸다. (손아파ㅠㅠㅠㅠ... 특히 새끼손가락 너무 많이 썼어) 어찌저찌 해서 복사 완성 하였다 코드는 걍 공개 하겠다 원래는 저작권을 중시하는 성격 이지만 굳이 지뢰찾기를 숨길 필요가 뭐가 있겠나 공유하면서 발전할 수 있다면 나는 상관 없다(크~ 멋있다(ㅈㅅ)) 보기 좋게 코드 스크립터로 공개 합니다. 이참에 프로그램도 같이 업로드 합니다. 아, 참고로 개발 언어는 c#입니다. .net framewo..