알고리즘 문제풀이/Algorithm3 하노이의 탑 하노이 탑 알고리즘은 재귀함수의 대표적인 알고리즘 중 하나 동작방식 세 개의 기둥 중 하나의 기둥에 지름이 서로 다른 여러 개의 원판들이 크기순으로 쌓여 있음 이 원판들을 다른 기둥으로 옮기는 과정 규칙 한 번에 하나의 원판만 옮길 수 있음 큰 원판 위에 작은 원판을 올릴 수 없음 중간 단계로 사용할 수 있는 보조 기둥을 활용할 수 있음 동작방식 예시 n-1개의 원판을 보조 기둥으로 옮김 가장 큰 원판을 목표 기둥으로 옮김 보조 기둥에 있는 n-1개의 원판을 목표 기둥으로 옮김 하노이 예시 구현코드 public class HanoiTower { public static void main(String[] args) { int num = 3; solveHanoi(num, 'A', 'B', 'C'); } pu.. 2023. 8. 30. 삽입 정렬(Insertion sort) 삽입 정렬(Insertion sort) 삽입 정렬은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘 뒤섞여 있는 트럼프 카드를 순서대로 다시 정리하는 모습을 생각하면 이해하기 쉬움. 가장 왼쪽에서부터 한 장씩 카드를 꺼내서 이미 정렬된 카드들 중에 올바른 자리에 끼워넣는 것과 같음 동작 방식 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눠줌 정렬되지 않은 부분에서 원소를 선택하고, 그걸 정렬된 부분에 삽입함 이걸 정렬되지 않은 부분이 없을 때까지 계속 반복함 동작 방식 예시 5 1 6 4 2 3 위의 숫자들을 트럼프 카드라고 생각 앞의 카드 두 장을 선택하고, 오른쪽 카드가 왼쪽 카드보다 큰 지 비교해봄 왼쪽이 5, 오른쪽이 1 이니까 오른쪽이 더 .. 2023. 8. 9. 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 배열에서 가장 작은 값을 선택하여 순차적으로 정렬하는 방법 비교적 작은 배열에 적합하며, 큰 배열에는 비효율적임 선택 정렬 알고리즘 동작 단계 배열을 순회하면서 가장 작은 값을 찾음 가장 작은 값을 찾았다면 그 값을 배열의 맨 앞 원소와 교환 *최소값이 이미 왼쪽 끝에 위치하면 아무런 작업도 하지 않음 다음 위치에서부터 위의 과정을 반복하며 배열이 정렬될 때까지 반복 선택정렬 예시 public class SelectionSort { public static void main(String[] args) { int[] arr = {64, 25, 12, 22, 11}; int n = arr.length; for (int i = 0; i < n - 1; i++) { int.. 2023. 8. 9. 이전 1 다음
