자료구조와 알고리즘 입문16 Chapter 06-4. 정렬 알고리즘_단순 삽입 정렬 단순 삽입 정렬(straight insertion sort)선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 삽입하는 작업을 반복하는 정렬 알고리즘아직 정렬되지 않은 부분의 첫 번째 요소를 정렬한 부분의 알맞은 위치에 삽입for (int i = 1; i 0 && a[j-1] > tmp) { a[j] = a[j-1]; j--; } a[j] = tmp;} 단순 삽입 정렬package ch06_4;import java.util.Scanner;// 단순 삽입 정렬public class Ex01_insertionSort { // 단순 삽입 정렬 static void insertionSort(int[] a, int n) { for (int i = 1; i 0 && a[j - 1] > te.. 2024. 8. 16. Chapter 06-3. 정렬 알고리즘_단순 선택 정렬 단순 선택 정렬(straight selection sort)가장 작은 요소를 맨 앞으로 이동하고, 두 번째 작은 요소는 맨 앞에서 두 번째로 이동하는 작업을 반복하는 알고리즘아직 정렬하지 않은 부분에서 가장 작은 키값(a[min]) 선택a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소 교환for (int i = 0; i 단순 선택 정렬package ch06_3;import java.util.Scanner;// 단순 선택 정렬/*서로 떨어져 있는 요소를 교환하므로 안정적이지 않음만약 값이 같은 요소가 중복되어 있는 배열을 정렬할 경우 두 요소의 순서가 바뀔 수 있음 */public class Ex01_selectionSort { // a[idx1]과 a[idx2]의 값을 교환 static.. 2024. 8. 16. Chapter 06-2. 정렬 알고리즘_버블 정렬 버블 정렬(bubble sort)이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘단순 교환 정렬(straight exchange sort)이라고도 함 버블 정렬을 이용해 요솟수가 n인 숫자 배열 오름차순 정렬끝에 있는 두 요소 비교 후 더 작은 값 왼쪽으로 교환 → n-1번 비교, 교환하면 가장 작은 요소가 맨 처음으로 이동, 이런 일련의 과정(비교, 교환)을 패스(pass)라고 함배열의 두번째 이후 요소를 비교, 교환하는 패스 수행(맨 앞을 가장 작은 수로 정렬해 놨기에 패스를 수행할 때마다 정렬할 요소가 하나씩 줄어듬) → n-2회 반복모든 정렬이 끝나려면 패스가 n-1번 수행되야 함 → n-1개 요소의 정렬이 끝나면 마지막 요소는 이미 끝에 놓이기 때문// 변수 i값을 0.. 2024. 8. 16. Chapter 06-1. 정렬 알고리즘_정렬 알고리즘이란 정렬(sorting)이란이름, 학번, 키 등 핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업작은 데이터를 앞쪽에 놓으면 오름차순(ascending order) 정렬, 반대로 놓으면 내림차순(descending order) 정렬 정렬 알고리즘의 안정성정렬 알고리즘은 안정된(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있음안정된 정렬이란 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 말함(점수순으로 정렬하되, 점수가 같으면 학번순으로 정렬하는 것과 같이)안정되지 않은 알고리즘은 점수가 같을 때 반드시 학번 순서대로 정렬되지 않음 내부 정렬과 외부 정렬내부 정렬(internal sorting): 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용.. 2024. 8. 16. Chapter 05-4. 재귀 알고리즘_8퀸 문제 8퀸 문제(8-Queen problem)서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓기퀸은 현재 놓여 있는 지점에서 가로, 세로, 대각선의 8가지 방향으로 직선 이동 가능퀸 배치하기 조건(대각선 규칙 제외)각 열에 퀸을 1개만 배치 - 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로각 행에 퀸을 1개만 배치 - 자신과 같은 행에 있는 다른 퀸을 공격할 수 있으므로 분기 조작, 가지 뻗기(branching)가지가 뻗어 나가듯 문제를 나누어 푸는 과정먼저 모든 조합을 나열하는 코드 작성 각 열에 퀸 1개를 배치하는 조합을 재귀적으로 나열package ch05_4;// 각 열에 퀸 1개를 배치하는 조합을 재귀적으로 나열public class Ex01_queenB { static in.. 2024. 8. 11. 이전 1 2 3 4 다음