버블 정렬 bubble sort 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복 액체 안의 공기 방울(액체보다 가벼운 공비 방울)이 보글보글 위로 올라오는 모습에서 착안 ▶︎패스(pass) 비교, 교환 작업 요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하고나면 작은 요소가 맨 처음으로 이동하게 된다. 수행하는 패스의 횟수가 n회가 아닌 n-1회인 것은 n-1개 요소의 정렬이 끝나고 나면 마지막 요소는 이미 끝에 놓이기 때문이다. 1. 버블 정렬 프로그램 서로 이웃한 요소에 대해서만 교환하므로 이 정렬 알고리즘은 안정적이라고 할 수 있다. 비교 횟수 : n ( n - 1 ) / 2회 ❔ ( n - 1) + ( n - 2 ) + ... + 1 = n ( n -1 ) 교환 횟수 : n ( n - ..
정렬 정렬(sorting) 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업 데이터를 정렬하면 검색을 더 쉽게 할 수 있다. 오름차순(ascending order) : 키 값이 작은 데이터를 앞에 놓는 정렬 방식 내림차순(descending order) : 키 값이 큰 데이터를 앞에 놓는 정렬 방식 ▶︎ 정렬 알고리즘의 안정성 1. 안정된(stable) 알고리즘: 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것 2. 안정되지 않은(unstable) 알고리즘: 같은 값의 키를 가진 요소의 순서가 정렬 전후에 달라지는 것 ▶︎ 내부 정렬과 외부 정렬 1. 내부 정렬 (internal sorting) 하나의 배열에서 작업할 수 있는 경우에 사용된다..
8퀸 문제 재귀 알고리즘에 대한 이해를 돕기 위한 예제로 자주 등장 19세기 유명 수학자 카를 프리드리히 가우스(C. F. Gauss)가 잘못된 해답을 내놓은 사실로도 유명 Q. 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 X 8 체스판에 놓으세요. 퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향 직선 이동이 가능. 즉, 상하좌우 + X 모양의 대각선 방향으로의 이동이 가능! 이 문제의 정답은 92가지의 조합이다. 8퀸 문제나 하노이의 탑 같은 문제는 문제를 세분화하고 세분된 작은 문제의 풀이를 결합해 전체 문제를 풀이해야 하는데, 이와 같은 방식을 분할 정복법(divide and conquer)이라고 한다. 물론, 이때 작은 문제의 풀이 방식은 전체 문제를 풀이하기 위한 부분이므로, 설계시..
하노이의 탑 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘 '64개의 황금 원반을 3개의 기둥 사이에서 바꿔 옮기는 작업을 완료하면 세계의 종말이 찾아온다.' 라는 고대 인도의 신화에서 유래된 이름 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제 원반은 1개씩만 옮길 수 있고, 큰 원반을 작은 원반 위에 쌓을 수 없다. 1.하노이의 탑 전체 실행 순서 (원반의 수 = 3) 2. '그룹'개념으로 이해하기 가장 마지막 원반을 제외하고 그 위에 쌓인 원반들을 '그룹'이라고 생각했을 때, 가장 큰 원반을 최소의 단계로 옮기기 위해서는 '그룹'들이 중간 기둥으로 옮겨져야 한다. 3. 하노이의 탑 구현하기 하노이의 탑은 탑 3개를 가지고 풀이한다. 따라서 기둥..
1. 하향식 분석: top - down - 출력 형태를 만들어놓고 회수하는 형태 - 결과가 이전의 결과에 영향을 받는 것 → 앞에서 보았던 재귀 메소드의 형태. 위에서 재귀 복습을 단계적으로 풀이 해 놓은 것을 하향식 분석이라고 할 수 있다. 하향식 분석이란, 가장 위쪽에 위치한 상자의 메소드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법을 말한다. top부터 분석하면 같은 메소드의 호출이 여러 번 나올 수 있기 때문에 "하향식 분석이 반드시 효율적이다" 라고는 할 수 없다. 2. 상향식 분석: bottom - up 상향식 분석이란, 가장 아래쪽부터 위로 쌓아 올리며 분석하는 방법을 말한다. 하향식 분석과는 분석 방향이 반대이다. - 루프(대표적으로 while) - 꼬리 재귀(tail recurs..
1. 재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 여기서 어떤 사건이 자기 자신을 포함하고, 다시 자기 자신을 사용하여 정의된다는 것을 "자연수 n(자기 자신)의 바로 다음 수도 자연수"로 볼 수 있다. 2. 팩토리얼 구하기 ▶︎ 음이 아닌 정수의 팩토리얼(factorial) 구하기 package com.study.Algorithm; import java.util.Scanner; // 팩토리얼을 재귀적으로 구현 class Factorial { // 양의 정수 n의 팩토리얼을 반환합니다. static int factorial(int num) { if (num > 0) { return num * factorial(num - 1); }..
