개발자되기 프로젝트

일반적으로 정렬 알고리즘은 O(n^2)의 수행시간을 가짐. 1. Selection Sort 50 10 60 80 90 100 20 위와같이 숫자 배열이 있을 때, 오름차순으로 정렬해보자 앞에서부터 쭉 스캔해서 제일 작은 값 찾고, 가장 앞에 위치시킴. 다름 위치에는 누굴 데려올까, 쭉 스캔하다가 가장 작은 값 선택(selection) 즉, n개의 값을 n번 씩 봐야 하기 때문에 O(n^2)이다. 2. Bubble Sort 아래와 같이 숫자 배열이 있다고 하자. 50 10 60 90 80 20 100 1) 50 & 10 비교한다. 10이 더 작다. -->50 ↔ 10 위치 바꾼다. 10 50 60 90 80 20 100 3) 50 & 60 비교 --> 그대로 10 50 60 90 80 20 100 5) 6..

여러 개의 수가 정렬 되었을 경우 특정 수를 찾는 방법 단순 반복문을 사용하면 앞에서 부터 차례로 찾아가기 때문에, 입력된 값에 따라 비교 횟수가 증가한다. 즉 O(n)의 수행이 이루어진다. 정렬된 상태에서 수행 횟수를 줄이기 위해서는 binary Search가 효율적이다. 왜냐? 아래와 같은 상황이라고 가정하자. 10개의 수의 배열이 주어진다. [12, 25, 31, 43, 53, 64, 78, 82, 95, 103] 95의 위치를 찾아보자. 1) 단순 반복문을 사용해서 하나씩 비교하면, 12부터 차례대로 비교해서 95와 같은지 확인해야 한다. 2) binary search를 사용하면, 중간에 있는 값이 95보다 큰지 작은지 판단한다. 3) 중간에 있는 값은 53이다. 따라서 이제 53이전의 숫자는 고..

10개의 숫자를 입력받는다. 10개의 숫자 중 가장 큰 값과 가장 작은 값을 찾는다. 몇 번째 수인지 찾는다. 반복문을 한 번만 사용한다. 예 : 10, 65, 84, 22, 42, 100, 210, 85, 87, 32 가 주어진 경우 max : 210, 7번 째 min : 10, 1번 째 얼마나 효율적인 알고리즘을 만드느냐가 중요함. 하나의 변수를 지정해 주고, 해당 변수를 update를 진행. Time complexity? for문이 얼마나 중첩되어 있냐? for문이 도는데. 뭐에 dependent하냐? public class MinMaxProblem { public static void main(String[] args) { int n = 10; Scanner sc = new Scanner(Syst..