알고리즘(이충기 교수)

분할 정복 설계 분할정복은 크게 3가지로 설계할 수 있다. 1.분할(Divide) 단계 -문제를 같은 유형의 여러 개의 더 작은 부분 문제들로 나눈다. -부분 문제는 풀기 쉬울 때까지 계속 나눈다. 2.정복(Conquer) 단계 -부분 문제들을 보통 재귀적으로 해결하여 해를 구한다. 3.합병(Merge) 단계 -문제에 대한 해를 구하기 위해 부분 문제들의 해를 합친다. 최댓값과 최솟값 찾기 문제: 크기가 n인 배열내의 요소들 중 최댓값과 최솟값을 찾는다. 쉬운 전략 1.최댓값을 찾는다. -- 비교 횟수: n – 1 2.남은 배열 요소들의 최솟값을 찾는다. -- 비교 횟수: n – 2 총 비교 횟수 = (n – 1) + (n – 2) = 2n - 3 1.배열을 반으로 나눈다. 2.양쪽 절반들의 최댓값과 최..

시간 복잡도란? - 알고리즘이 얼마나 빨리 수행되는지를 나타내는 것 공간 복잡도란? - 알고리즘이 수행되는 동안 요구되는 메모리 공간의 크기 알고리즘은 3가지로 분석할 수 있다 - 입력크기, 실행 시간 측정 단위, 증가 차수 입력 크기 - 배열의 크기 - 연결 목록의 길이 - 행렬에서 행과 열의 크기 - 그래프에서 정점과 간선의 수 덕수궁에서 창덕궁을 가는데 가장 빠른 길은 어떻게 찾아야 할까? 일단 갈 수 있는 루트들을 모두 조사해보자 덕수궁 - 경희궁 - 경복궁 - 창덕궁 덕수궁 - 경복궁 - 창덕궁 덕수궁 - 종묘 - 창덕궁 덕수궁 - 경희궁 - 경복궁 루트는 1 + 0.7 = 1.7로 덕수궁 -경복궁 = 1.3보다 크기때문에 제외한다. 덕수궁 - 경복궁 - 창덕궁 = 3.4 > 덕수궁 - 종묘 -..

알고리즘이란? 1. 문제를 해결하기 위한 단계적 절차 또는 방법 2. 순서대로 구체적이고 명확하게 기술해야 한다. 3. 유효한 입력을 받아 실행한 결과인 해(답)를 출력한다 1.명확성 –알고리즘의 각 단계는 애매모호하지 않고 명확해야 한다. 2.정확성 –모든 유효한 입력에 대해 올바른 해를 출력해야 한다. 3.정지성 –유효한 입력이 주어지면 유한한 시간 내에 종료되어야 한다. 위와같이 알고리즘을 작성할 때는 명확하고 정확하게 작성을해야 한다. 다음 알고리즘을 구현해 보자. import java.util.Scanner; public class 함계산 { public static void main(String[] args){ int n = 5; int sum = 0; int i = 0; while(i < n..

1주차에 조를 짜기위한 사전 평가 시험을 치뤘다. 사전 평가 때 치뤘던 문제를 복습겸 분석해보려한다. 1. 다음 코드에서 while 문의 수행이 끝났을 때 count 변수와 mystery변수의 값은 각각 얼마인가? package 이충기; public class 사전평가시험1 { public static void main(String[] args){ int count = 0; int mystery = 1; while(count < 5){ count++; mystery = mystery * count; } System.out.printf("%d %d",count, mystery); } } 간단한 문제이다. count = 0, mystery = 1인 상태에서 문제를 풀면된다. 반복문 while문에서 count..