반응형 Language/알고리즘 개념정리11 자바 최빈값(Mode) 알고리즘 정리 최빈값(Mode) 알고리즘이란 주어진 데이터 중에서 가장 많이 나온(중복된) 값을 말하는데 값의 범위가 매우 넓다면 COUNT를 담아두는 방법을 변경해야 겠지만 (Map을 사용한다거나 등..) 특정 범위 안으로만 들어올 경우에는 (5이하, 100이하 등) 값의 범위와 동일하게 index 배열을 만든 뒤 for 문을 돌리면서 값에 해당하는 내용을 인덱스 배열에서 1씩 올려주고 for 문을 돌리면서 해당 인덱스 배열의 최대값을 구하면 되는데 최대값이 곧최빈값이 되므로 최대값을 가져와주면 바로 끝이 난다 예제에 사용한 코드는 다음과 같다 public static void main(String[] args) { // 최빈값 알고리즘(Mode Algorithm) // 주어진 데이터에서 가장 많이 나온(중복된) 값.. 2021. 5. 30. 자바 병합(Merge) 알고리즘 정리 병합(Merge) 알고리즘은 오름차순으로 정렬되어 있는 정수 배열을 하나의 배열로 병합해주는 알고리즘인데 먼저 두 배열을 오름차순 정렬시킨 후 while을 돌려주면서 두 배열의 값을 비교해 작은 값을 반환시킬 배열에 넣어준다 해당 while은 한 배열의 끝까지만 도달해도 종료되는 조건이기 때문에 arr1의 1 arr2의 2 arr1의 3 arr2의 4 를 넣어주면 j가 2이기 때문에 i < arr1.length && j < arr2.length 조건을 충족시키지 못하기 때문에 종료되고 더 긴 배열인 arr1만 남게 되는데 이후 while을 돌려주면서 arr1의 값을 쭉 넣어주면 오름차순으로 정렬했기 때문에 기존에 넣었던 값보다 더 큰 값이 차례대로 들어가게 된다 여기서 while(j 2021. 5. 30. 자바 이진검색(Binary Search) 알고리즘 정리 이진검색(Binary Search) 알고리즘은 정렬되어 있는 데이터를 절반씩 나눠 검색하는 방식인데 순차 검색 방법이 모든 데이터를 다 확인해본다면 이진 검색은 데이터를 절반으로 나눠가면서 찾게 된다 먼저 데이터가 오름차순으로 되어있지 않을 때는 오름차순으로 데이터를 정렬하고 low는 0으로 (배열의 처음 인덱스) high는 해당 배열의 마지막 인덱스로 초기화한다 다음은 while을 돌려주면서 low + high / 2 를 해서 mid 값을 구하는데 mid를 배열의 인덱스로 넣었을 경우의 값이 찾는 값과 동일하다면 바로 끝이 나지만 그렇지 않을 경우에는 해당 값이 찾는 값(Search)보다 크냐 작냐에 따라 low, high를 바꿔주게 되는데 Search 값이 mid를 배열의 인덱스로 넣었을 경우보다 작.. 2021. 5. 30. 자바 선택정렬(Selection Sort) 알고리즘 정리 선택정렬(Selection Sort) 알고리즘은 데이터 하나를 기준으로 다른 데이터와 비교하여 가장 작거나 / 큰 데이터와 자리를 바꾸는 식으로 반복 비교하는 정렬을 수행하게 되는데 데이터의 개수가 N개라면 N-1회 회전(for문)을 하게 된다 먼저 반복 정렬이 어느 식으로 움직이는지 알아야 하는데 이게 가장 중요한 부분인 만큼 두 눈 크게 뜨고 잘 보자 1회차 5 3 1 2 4 2회차 1 5 3 2 4 3회차 1 2 5 3 4 5 3 1 2 4 가 들어있는 배열에서 오름차순 정렬을 할 경우에는 5는 3보다 크기 때문에 5와 3의 위치를 바꿔서 3 5 1 2 4 가 되고 arr[i]에 3이 들어가게 된다 (비교 대상이 5에서 3이 된다는 말) 이후 3은 1보다 크기 때문에 3과 1의 위치를 바꿔서 1 5.. 2021. 5. 29. 자바 순위(Rank) 알고리즘 정리 순위(Rank) 알고리즘이란 주어진 범위 데이터의 순위를 구하는 알고리즘인데 중요한 점은 순위를 보관할 배열을 추가로 하나 만들어서 해당 배열에 값별 순위를 넣어줘야 한다 이후 for 문을 돌리면서 해당 값의 순위를 1로 시작하고 for 문 안에서 for 문을 한번 더 돌리면서 배열의 i값과 다른 값(j)들을 비교하는데 배열의 i값보다 큰 값이 있으면 i값에 해당하는 순위 배열의 i값을 1씩 올려주면 된다 이러면 for 문이 돌아가면서 값을 가지고 다른 값들과 비교하면서 현재 값보다 클 경우 +1을 해 주기 때문에 값별 순위가 쭉 들어가게 된다 이후 출력해보면 값별로 순위가 제대로 찍혀 나오는 것이 보인다 결국 순위 알고리즘의 포인트는 값 배열 / 순위 배열 두 배열을 만든 뒤 for 문을 2번 돌려주면.. 2021. 5. 29. 자바 근사값(Near) 알고리즘 정리 근사값(Near) 알고리즘이란 전체 데이터 중 특정 데이터와 가장 근접한 값을 말하는데 포인트는 배열의 각 값 - 특정 값 계산 뒤 절대값으로 변환해서 for문 돌리며 비교 후 가장 작은 수를 가져와주면 그게 근사값이 되겠다 먼저 변수의 최소값을 해당 변수에 지정할 수 있는 가장 큰 숫자를 넣어주고 다음으로 for 문을 돌리는 과정에서 배열의 인덱스별 값 - 특정 값 을 한 뒤에 Math.abs로 절대값을 구하는데 만약 Math.abs를 사용하지 않고 절대값을 구하려면 값 < 0 ? -값 : 값 이런 식으로 삼항연산자를 사용해 0보다 작다면 -를 한번 더 해줘서 양수로 만들고 양수면 그냥 반환하는 식으로 따라해주면 된다 근사값의 경우에는 절대값을 구한 후에는 for 문을 돌리면서 현재 최소값보다 작을 경.. 2021. 5. 29. 이전 1 2 다음 반응형
