알고리즘 (8) 썸네일형 리스트형 [알고리즘] 선행탐색 선형탐색이란 왼쪽 인덱스부터 차례대로 비교하여 값을 찾아내는 방식의 알고리즘이다. 논리 원하는 값을 0번 인덱스 값과 비교한다. 동일한 값이 있다면 탐색완료 동일한 값이 없다면 다음 인덱스와 비교 next .... 이미지로 보기 특징 알고리즘 구현이 간단하다. 배열이 정렬되어 있지 않은 것을 전제로한다. 단점 배열이 길어질수록 비례해서 시간이 오래걸린다. 예제 [1,3,2,4,5]에서 4라는 값을 찾아보자 예제 코드 // 배열을 선언 int[] arr = new int[5]; // 배열에 값 넣기 arr[0] = 1; arr[1] = 3; arr[2] = 2; arr[3] = 4; arr[4] = 5; // 찾고자하는 값을 지정 int key = 4; // 배열 길이만큼 반복 for(int i=0;i [알고리즘] 이진탐색 이진탐색이란 정렬된 배열에서 특정한 값을 찾기 위한 목적으로 사요하는 알고리즘이다. 논리 정렬이 되어 있다는 것을 전제로한다. 찾고 싶은 값을 설정한다. 중간 인덱스 값을 찾는다. 찾고 싶은 값을 중간 인덱스 값과 비교한다. 값이 동일하다. 탐색이 완료된다. 중간 인덱스 값이 크다. 찾는 값은 왼편에 있다는 뜻이다. 왼편에 있는 값들 중 중앙 값을 찾는다. 다시 값들을 비교한다. 중간 인덱스 값이 작다. 차는 값은 오른편에 있다는 뜻이다. 오른편에 있는 값들 중 중앙 값을 찾는다. 다시 값들을 비교한다. 이미지로 보기 특징 탐색하는 로직들 중 가장 빠르다. 탐색 범위를 절반씩 줄여나가기 때문에 선형 탐색에 비해 빠르다. 데이터가 많은 경우에도 빠르게 찾을 수 있다. 단점 데이터의 정렬이 선행된다. 예제 .. [알고리즘] 선택정렬 선택정렬이란 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 알고리즘이다. 논리 0번 인덱스를 최소 값이라고 가정한다. 0번 인덱스를 마지막 인덱스까지 비교한다. 0번 인덱스 보다 작은 값이 있다면 자리를 교체한다. next 1번 인덱스를 최소 값이라고 가정한다. 1번 인덱스를 마지막 인덱스까지 비교한다. 1번 인덱스 보다 작은 값이 있다면 자리를 교체한다. next .... 이미지로 보기 특징 알고리즘이 단순하다. 비교 횟수는 많지만, 실제로 교환하는 횟수는 적다. 교환이 많이 일어나는 상황에서 효율적이다. 단점 불안정 정렬이다. 중복 값이 있을 경우 위치 보존이 안된다. 예제 [5,3,1,4,2]가 [1,2,3,4,5]가 되도록 정렬한다. 예제 코드 // 배열 .. [알고리즘] 버블정렬 버블정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 논리 0번 인덱스와 1번인덱스를 비교한다. 1번 인덱스가 작다면 앞으로 배치한다. 1번 인덱스가 크다면 상태를 유지한다. next 1번 인덱스와 2번인덱스를 비교한다. 2번 인덱스가 작다면 앞으로 배치한다. 1번 인덱스가 크다면 상태를 유지한다. next .... 이미지로 보기 특징 알고리즘이 단순하다. 안정 정렬 이다.(동일한 값을 가진 데이터들의 순서가 원래의 순서와 같이 유지되는 정렬방법) 동일 값이라도 그 데이터가 내포하는 의미는 다를 수 있다. ex) 점수가 같은 학생 단점 특정 요소가 최종 정렬 위치에 있는 경우라도 교환이 일어난다. 예제 [3,2,5,1,4]이 [1,2,3,4,5]가 되도록 정렬한다. 예제 코드 // 배열 선.. [알고리즘] 삽입정렬 삽입정렬이란 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 논리 0번 인덱스는 정렬되있다고 가정한다. 1번 인덱스는 0번 인덱스와 비교하여 1번 인덱스가 작다면 앞으로 배치한다. 1번 인덱스가 크다면 상태를 유지한다. next 2번 인덱스는 1번 인덱스, 0번 인덱스 순으로 비교하여 2번 인덱스가 작다면 앞으로 배치한다. 2번 인덱스가 크다면 상태를 유지한다. next .... 이미지로 보기 특징 알고리즘이 단순하다. 대부분의 원소들이 정렬되어 있다면, 굉장히 효율적입니다. 안정 정렬 이다.(동일한 값을 가진 데이터들의 순서가 원래의 순서와 같이 유지되는 정렬방법) 동일 값이라도 그 데이터가 내포하는 의미는 다를.. [알고리즘] 탐색 알고리즘 종류 일반 검색 속도가 비교적 느리다. 최적화된 검색 속도가 비교적 빠르다. 정렬이 반드시 선행 되어야 한다. 논리 찾을 대상을 설정한다. 인덱스 범위를 설정할 변수를 만든다. 변수의 초기 값은 반드시 배열(대상) 범위가 아닌 값으로 해야 한다. JAVA에서는 배열에 음수 값이 없기 때문에 음수 값으로 설정한다. 대상이 없다면 범위 습득이 불가능하거나 예기치 않은 결과가 나올 수 있기 때문이다. 찾을 데이터를 기준으로 비교하며 찾아나간다. 예제 배열에 1 ~ 10의 숫자가 랜덤으로 5개 들어있다. 숫자 2와 그 인덱스 번호를 찾고자 한다. 인덱스 0번부터 대조하여 2가 존재하는지 확인한다. 일치하는 값이 있다면 그 인덱스 번호를 기록하고 대조를 멈춘다. 예제 코드 //우리가 찾을 정수 int key = .. [알고리즘] 최소 값 찾기 알고리즘 논리 0번째 인덱스가 가장 작다고 가정한다. 그 다음 인덱스부터 가정한 값과 비교하면서 확인한다. 다음 인덱스 값이 가정한 값 보다 작다면 가정한 값을 치환한다. 계속 비교해 나간다. 예제 배열에 [10, 2, 5, -3, 1]가 들어있다. 10을 가장 작다고 가정한다. 10를 1번 인덱스부터 비교를 한다. 10보다 작은 값이 없다면 10이 최소 값이 된다. 10보다 작은 값이 있다면 그 값을 최소 값으로 치환한다. 비교를 다시 시작한다. 예제 코드 // 배열에 데이터 할당 int datas[] = {10, 2, 5, -3, 1}; // 0번 인덱스가 최소 값이라고 가정 int minIndex = 0; // 1번부터 마지막 인덱스까지 반복 for(int i=1; i [알고리즘] 최대 값 찾기 알고리즘 논리 0번째 인덱스가 가장 크다고 가정한다. 그 다음 인덱스부터 가정한 값과 비교하면서 확인한다. 다음 인덱스 값이 가정한 값 보다 크다면 가정한 값을 치환한다. 계속 비교해 나간다. 예제 배열에 [2, 1, 3, 5, 4]가 들어있다. 2를 가장 크다고 가정한다. 2를 1번 인덱스부터 비교를 한다. 2보다 큰 값이 없다면 2가 최대 값이 된다. 2보다 큰 값이 있다면 그 값을 최대 값으로 치환한다. 비교를 다시 시작한다. 예제 코드 // 0번 인덱스를 가장 큰 값이라고 가정 int maxIndex=0; // 1번부터 마지막 인덱스까지 반복 for(int i=1;i datas[maxIndex]) { //i번 인덱스를 저장 maxIndex=i; } } //출력 System.out.println("최대값은 .. 이전 1 다음
