알고리즘 정리 (3) 썸네일형 리스트형 0-1 BFS 가중치가 0과 1뿐인 노드들 사이에서 최단거리를 찾는 방법이다. 일반적인 BFS는 노드를 선택한 다음 주위의 노드들을 queue에 넣는다. 이때 queue는 FIFO, 선입선출 형태의 자료구조이다. 이후 queue가 빌때까지 queue에 있는 원소들을 탐방하고 앞으로 탐방해야하는 노드를 queue에 추가한다. 이때 이미 방문한 노드를 별도로 처리하여 중복 탐색을 방지하며 간선을 하나 씩 계산해가며 최단거리를 계산한다. 0-1BFS는 전반적으로 BFS와 비슷하지만 차이점은 queue 대신 deque를 사용한다는 부분에 있다. deque는 FIFO만 가능한 queue와 다르게 입력을 가장 앞이나 뒤에 골라서 할 수 있다. 이를 활용하여 가중치가 0이라면 앞에 1이라면 뒤에 추가하여 가장 낮은 가중치부터 계산.. 병합 정렬 병합 정렬은 분할정복 기법 알고리즘 중 하나이다. 분할: 정렬한 n개의 원소의 배열을 n/2개로 분할한다. 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다. 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다. 의 구조로 이루어져있다. 의사코드(Pseudo code) MERGE(A,p,q,r) n1=q-p+1 n2=r-q 배열 L[1...n+1]과 R[1..n+1]을 생성한다. for i=1 to n1 L[i] = A[p+i-1] for j = 1 to n2 R[j] = A[q+j] L[n1+1] = ∞ R[n2+1] = ∞ i=1 j=1 for k= p to r if L[i] 삽입 정렬 정렬 문제를 해결하는 알고리즘 중 하나 정렬 문제 입력: n개 수들의 수열 출력: a1 ≤ a2 ≤ a3 ≤ a4 ≤ an... 을 만족하는 입력수열의 순열 정렬하고자 하는 숫자를 키라고 하며 입력으로는 n개의 원소 배열 A가 주어진다면 의사코드는 아래와 같다. 의사코드(Pseudo code) Insertion-Sort(A) Insertion-Sort(A) for j=2 to A.length key = A[j] //A[j]를 정렬된 배열 A[1...j-1]에 삽입한다 i=j-1 while i > 0 and A[i] > key A[i+1]=A[i] i = i - 1 A[i+1] = key 알고리즘 타당성 초기조건 j=2 인 경우에서 시작하므로 해당 상태에서 루프의 불변성이 성립되는지를 확인해야한다. 부분 .. 이전 1 다음