자료구조 & 알고리즘2 [자료구조&알고리즘] 버블 정렬(Bubble Sort) - 자바 버블 정렬 시간 복잡도 : O(n2) 버블 정렬은 아래 그림에서 볼 수 있듯이 인접한 두 원소의 비교를 통해 정렬을 해나가는 알고리즘입니다. 요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 큰 요소가 맨 뒤로 이동합니다. 이러한 일련의 비교, 교환 과정을 패스라고 합니다. 두번째 패스의 비교 횟수는 첫번째 패스보다 1적은 n-2회, 세번째 패스에서는 n-3회로 패스마다 1회씩 비교 횟수가 줄어듭니다. 그 이유는 각 패스마다 요소 하나씩 정렬이 완료되기 때문입니다. 모든 정렬이 완료되려면 n-1회의 패스가 수행되어야 합니다. 소스 코드 public class Main { private static void swap(int[] arr, int n1, int n2) { int temp =.. 2021. 8. 16. [자료구조&알고리즘] 8퀸 문제 - 자바 8퀸 문제란? 8퀸 문제란 8개의 퀸이 서로 공격하여 잡을 수 없도록 체스판에 배치하는 문제입니다. 체스판의 크기는 8*8 퀸은 체스판의 대각선을 포함한 모든 방향으로 어떤 위치든 직선 이동이 가능 퀸을 배치하는 방법 8개의 퀸을 체스판에 배치하는 경우의 수는 체스판이 8*8 = 64 칸으로 되어있기 때문에 다음과 같습니다. 64*63*62*61*60 ... * 57 = 178,462,987,637,760 보기만 해도 말도 안 되는 저 경우의 수들을 어떤 조합이 조건을 만족하는지 하나하나 살펴보는 것은 상당히 비효율적입니다. 이를 해결하기 위해 규칙 두가지를 세워보도록 하겠습니다. [규칙 1] 각 열에 퀸을 1개만 배치한다. 규칙 1을 적용하면 경우의 수는 8*8*8*8*8*8*8*8=16,777,216.. 2021. 8. 4. 이전 1 다음
