본문 바로가기

알고리즘/기초9

절대값을 이용한 i, j의 증감 규칙 찾기 (절대값과 나머지를 이용하기) 다음과 같은 출력을 해야 하는 문제가 있다. Sssss sSsss ssSss sssSs ssssS sssSs ssSss sSsss Sssss 어떻게 풀까? 직관적으로 떠오르는 규칙은 다음과 같다. 1) i == j 2) ( i + j ) % 8 == 0 이를 코드로 옮기면 다음과 같다. public static void problem1(){ for (int i =0; i j =1 i = 2 -> j =2 i = 3 -> j =3 i = 4 -> j =4 i = 5 -> j = 3 i = 6 -> j =2 i = 7 -> j = 1 i = 8 -> j =0 보면 i와 j가 순서대로 같이 증가하다가 5 시점부터 i는 증가하고 j는 감소한다. 이에 대한 수학적 규칙은 다음과 같다. j = abs(4 - abs.. 2023. 6. 18.
퀵 정렬 (Quick Sort) - 아이디어, 작동 원리, 성능 및 시간 복잡도, 특징, 자바 구현 코드 퀵 정렬 비교 기반 알고리즘 중 분할 정복 방식을 이용하며 평균적으로 좋은 성능을 보여 널리 사용되는 퀵 정렬에 대해 알아본다. 아이디어 이진 탐색과 같은 분할 정복 원리를 이용한다. -> 특정 원소를 기준으로 배열을 두 부분 배열로 분할한다. -> 각 부분배열에 대해 퀵 정렬을 순환적으로 적용한다. 이때 특정 원소, 즉 피벗을 정하는 것이 퀵 정렬의 핵심이다. 뒤에서 살피겠지만 피벗을 어떤 것으로 지정하느냐에 따라 성능 차이가 크게 나기 때문이다. 퀵 정렬에서는 결합은 별도로 필요 없다. 피벗을 기준으로 나눠진 두 부분 배열을 순환적으로 적용하되, 그 과정에서 정렬이 일어나므로 최종 분할이 끝나는 시점에는 모든 배열이 정렬되어 있다. 작동 원리 다음과 같은 데이터를 정렬하는 과정을 통해 실제 작동 원리.. 2023. 6. 11.
선택 정렬, 아이디어, 작동 원리, 자바 구현 코드 선택 정렬 비교 기반 알고리즘 중 O(n^2)의 성능을 보이며 가장 작은 값부터 정렬하는 선택 정렬에 대해 알아본다. 아이디어 주어진 데이터 중에서 가장 작은 값부터 차례대로 ‘선택’해서 나열하는 방식 -> n개의 데이터에 대해서 -> 데이터의 개수 만큼을 반복하면서 -> 정렬되지 않은 데이터 중에서 가장 작은 값을 선택 -> 선택된 값과 미정렬 데이터 부분의 첫 번째 원소와 교환 작동 원리 다음과 같은 데이터를 정렬하는 과정을 통해 실제 작동 원리를 살펴보자 . int[] arr1 = {6, 2, 7, 8, 3, 5, 4 }; 먼저 데이터의 개수 만큼 반복해줄 반복문을 선언한다. for (int i = 0; i < n - 1; i++) { 이후 정렬되지 않은 부분에 대해 최소 값을 찾는 부분이다. //.. 2023. 6. 10.
계수 정렬(countin/카운팅 정렬) 아이디어, 작동원리, 시간 복잡도, 자바 구현 코드 비교 기반의 정렬이 아닌 데이터 기반의 정렬 방식으로 계수 정렬과 기수 정렬이 있다. 데이터 기반의 정렬은 입력 데이터에 대한 메타 정보가 주어지는 정렬로, 비교 기반 정렬의 하한인 O(nlogn)보다 좋은 성능 O(n)을 낼 수 있는 정렬이다. 단, 데이터 분포에 대한 정보가 주어져야 한다. 예를 들어, 아래와 같은 데이터 입력이 주어진다고 할 때, 데이터의 분포는 4 ~ 9이다. int[] arr = {7, 5, 9, 8, 4, 5, 7, 5}; 이 글에서는 데이터 기반 정렬 중 하나인 계수 정렬에 대해 살펴본다. 계수 정렬 아이디어 아이디어는 2가지 부분으로 나뉜다. 1) 입력 값에서 데이터가 발생한 횟수를 구한다. 2) 발생한 횟수를 기반으로 누적 횟수를 구한다. 작동 원리 이 배열을 갖고 작동 .. 2023. 6. 10.

티스토리툴바