본문 바로가기

#자바#JAVA#알고리즘#DoIt#기본 알고리즘#

[자바 Do It! 알고리즘]Chapter06 정렬 (단순삽입정렬) [단순삽입정렬] 1. 단순삽입정렬은 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는'작업을 반복하여 정렬하는 알고리즘입니다. 2. 단순 삽입정렬은 2번째 요소부터 선택하여 진행합니다. 3. 정렬된 부분과 아직 정렬되지 않은 부분에서 배열이 다시 구성된다고 생각하면서 아래의 작업을 n-1회 반보갛면 정렬을 마치게 됩니다. 1) 아직 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입합니다. 2) '알맞은 위치'란 왼쪽에 이웃한 요소가 선택한 요소보다 크면 그 값을 대입하고 앞으로 이동하면서 이 작업을 반복합니다. 그러다가 선택한 값 이하의 요소를 만나면 그보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 삽입할 값을 대입합니다. 3) 즉, tmp에 a[i]를 대입하고 반복 제어용.. 더보기
[자바 Do It! 알고리즘]Chapter06 정렬 (단순선택정렬) [단순선택정렬] 1. 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘입니다. 2. 아직 정렬하지 않은 부분에서 값이 가장 작은 요소를 선택하고 아직 정렬하지 않은 부분의 첫 번째 요소와 교환합니다. 3. 단순 선택 정렬의 교환 과정은 아래와 같습니다. 1) 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택합니다. 2) a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환합니다. 3) 이 과정을 n-1회 반복하면 됩니다. 4. 단순 선택 정렬 알고리즘의 요솟값을 비교하는 횟수는 (n의 제곱 - n) / 2회입니다. 5. 이 정렬알고리즘은 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않습니다. ​ 더보기
[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (8퀸) [8퀸 문제 - 서로 공격하여 잡을 수 없도록 8개의 퀸을 8 x 8 체스판에 놓으세요.] ※ 퀸은 서 있는 지점에서 체스판의 어떤 지점으로든 여덟 방향으로 직선 이동이 가능합니다. 1. 이 문제의 정답은 92가지의 조합입니다. 2. 체스판의 가로 줄을 행, 세로 줄을 열이라 하고 배열 인덱스에 맞추어 행과 열에 0~7의 번호를 부여합니다. 3. 퀸 배치하기 1) 규칙 1 : 각 열에 퀸을 1개만 배치합니다. 2) 규칙 2 : 각 행에 퀸을 1개만 배치합니다. 4. 가지뻗기(branching) 1) 퀸의 배치를 나타내는 배열 pos를 생성합니다. 2) i열에 놓인 퀸의 위치가 j행이면 pos[i]의 값을 j로 합니다. (1) 예를 들어, pos[0]의 값이 0이면 '0열의 퀸이 0행에 배치된 상태'를 의.. 더보기
[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (하노이의 탑) 그림으로 보면 이해가 가는데, 코드로 보면 이해가 안가네요.. ​ [하노이의 탑] - 쌓아 놓은 원반을 최소의 횟수로 옮기기 위한 알고리즘 이 챕터는 글보다는 그림이 더 나은 것 같습니다. ​ 1. 기둥 번호를 정수 1,2,3 으로 나타냅니다. 2. 기둥 번호의 합이 6이므로 시작기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6-x-y로 구할 수 있습니다. 3. 원반은 no개이므로 move 메서드는 아래와 같은 과정을 거칩니다. 1) 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no-1])을 시작 기둥에서 중간 기둥으로 옮깁니다. 2) 바닥 원반 no를 시작 기둥에서 목표 기둥으로 옮겼음을 출력합니다. 3) 바닥 원반을 제외한 그룹(원반[1] ~ 원반[no-1])을 중간 기둥에서 목표 기둥으로 옮깁니.. 더보기
[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (재귀 알고리즘 분석 - recur 메서드) [재귀 알고리즘의 분석 - recur 메서드] 1. recur 메서드는 메서드 안에서 재귀호출을 2회 실행합니다. 2. 이처럼 재귀 호출을 여러 회 실행하는 메서드를 순수하게(genuinely) 재귀적이라 하며, 실제 동작은 매우 복잡합니다. 3. 이런 복잡한 구조를 가진 재귀 메서드는 좀 더 전략적으로 분석해야합니다. ' 왼쪽 화살표를 따라 하나 아래 상자로 이동하고, 다시 원래의 상자로 돌아오면 상자 안의 값을 출력하고 이어서 오른쪽 화살표를 따라 칸 아래 상자로 이동한다'로 그림을 해석하시면 되겠습니다. ​ 1. 매개변수 n으로 4를 전달하면 recur 메서드는 아래 과정을 순서대로 실행합니다. 1) recur(3)을 실행합니다. 2) 4를 출력합니다. 3) recur(2)를 실행합니다. 2. 물론.. 더보기
[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (유클리드 호제법) 알고리즘 책을 보면 볼수록, 세상에는 천재가 많다고 느껴집니다. 이런 천재들과 같은 세상에서 살고 있다는 것이 신기하기도 하며 한없이 작아집니다. 그럼에도 천재들의 시야를 빌릴 수 있어서 감사합니다. ​ [유클리드 호제법] 1. 두 정수의 최대공약수(greatest common divisor)를 재귀적으로 구하는 방법입니다. 두 정수를 직사각형의 두 변의 길이라고 생각하면 두 정수의 최대공약수를 구하는 문제는 다음 문제처럼 바꿀 수 있습니다. ★ 직사각형을 정사각형으로 완전히 채웁니다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하세요. (1) 22 X 8 크기의 직사각형에서 짧은 변(8)을 한 변으로 하는 정사각형으로 분할합니다.(a). 이렇게 하면 (b)처럼 8 X 8 크기의 정사각형 타.. 더보기
[자바 Do It! 알고리즘]Chapter05 재귀 알고리즘 (팩토리얼 구하기) [재귀] 1. 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 합니다. ※ 1은 자연수입니다. 자연수 n의 바로 다음 수도 자연수입니다. 재귀적 정의(recursive definition)에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의할 수 있습니다. ​ [음이 아닌 정수의 팩토리얼(factorial)을 구하는 프로그램] 1. 음이 아닌 정수 n의 팩토리얼(n!) 아래처럼 재귀적으로 정의할 수 있습니다. 0! = 1 n > 0 이면 n! = n x (n-1)! factorial 메서드를 사용해 3의 팩토리얼 값을 구체적으로 구하는 과정 1. 메서드 호출식 factorial(3)을 실행하면 factorial 메서드가 시작됩니다. 이 메서드는.. 더보기
[자바 Do It! 알고리즘]Chapter04 스택과 큐(큐) (2) ​ 1. 링 버퍼는 '오래된 데이터를 버리는' 용도로 사용할 수 있습니다. ※ 요소의 개수가 10인 배열에서 최근에 입력한 10개의 데이터만 출력하기 ☞ 입력한 값을 a[cnt++ % N]에 저장합니다. 1) 1번째 값 입력하기 cnt 는 0 이고 10으로 나눈 나머지는 0입니다. 입력한 값은 a[0] 에 저장됩니다. 2) 2번째 값 입력하기 cnt 는 1이고 10으로 나눈 나머지는 1입니다. 입력한 값은 a[1]에 저장됩니다. (중략) 3) 11번째 값 입력하기 cnt 는 10이고 10으로 나눈 나머지는 0입니다. 입력한 수는 a[0]에 저장됩니다. 1번째 위치의 데이터를 11번째 데이터가 덮어씁니다. ☞ 출력할 때 조금 더 생각해 볼 내용이 있습니다. 입력한 값의 개수(cnt)가 10 이하면 다음을 .. 더보기

티스토리툴바