컴퓨터/Algorithm26 BFS 초기상태 s를 enqueue하는 것으로 시작. while(!QEmpty) { D= Dequeue // 하나 뽑아서 for(All case)//발전 가능한 모든 상태 if(Isavail) // 발전가능하면 Enqueue } Dest 방문 체크는 InQueue, Dequeue 둘 중에 아무데서나 가능함. 방문 체크는 InQueue에서 무조건. 함수 안에서 할 수도 있음 Tip1) 2차원배열 입력 받을 때 %1d 하면 숫자 하나만 읽음 Tip2) 배열을 1,1부터 받으면 배열 외곽은 0으로 static 자동 되므로 가능 Tip3) 미로 문제에서 0, 1을 반전 시키고 싶으면 ^ 연산자 -> static 배열에서 0이 갈수 없는 곳이므로, 예외처리에 유리 Tip4) 방문시 test_case 번호로 하면 방문배열.. 2019. 11. 17. 병합 정렬(Merge Sort) (참고) 폰 노이만이 고안 QSort, MSort 둘 다 Divide & Conquer 철학에서 나온 것 머지소트는 많은 자료를 한번 정렬하는 것보다 적은 자료를 여러 번 정렬하겠다는 철학에서 나옴 Q M 전략 Pivot 기준 절반 무조건 절반 Avg O(nlogn) O(nlogn) Worst O(n2) O(nlogn) 공간 자료 공간 자료 공간 * 2 1. 영역 나누기 2. 각 영역 재귀적 진행 3. 두 개의 영역 Merge -Merge 과정 (S,m) (m+1,e) 두개의 영역을 -> (S,e) 배열로 넣는다. Idx1, idx2를 이용해 우선순위인 것을 먼저 넣어주고 그 쪽 인덱스를 ++ 한쪽이 끝나면 나머지를 전부다 넣어준다. void msort(int s, int e) { int l, r, t,.. 2019. 11. 17. 이전 1 2 3 4 5 다음