알고리즘/기초9 이분탐색 (binary search), 아이디어, 작동 원리, 시간 복잡도/성능, 특징, 자바 구현 코드 이분 탐색 혹은 이진 탐색 정렬되어 있는 집합에서 원하는 값을 찾는 효과적인 탐색 방법으로 알려진 이분 탐색에 대해 알아본다. 아이디어 큰 틀은 분할 정복 원리를 이용한다. -> 배열의 가운데 원소 A[mid]와 탐색키 x를 비교한다. -> 이 때 3가지 케이스로 나뉜다. (1)탐색키=가운데원소 → 탐색성공(인덱스mid반환후종료) (2)탐색키가운데원소 → 순환호출 (이진 탐색(원래 크기 1/2의 오른쪽 부분배열)) *mid = ( 시작인덱스 i + 마지막 인덱스 i )/ 2 - 분할 과정: 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할. 탐색키와 가운데 원소가 같으면 가운데 원소의 배열 인덱스를 반환/종료 - 정복 과정: 탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을.. 2023. 7. 3. 버블 정렬 (Bubble Sort) - 아이디어, 작동 원리, 성능 및 시간 복잡도, 특징, 자바 구현 코드 버블 정렬 비교 기반 알고리즘 중 가장 기초가 되는 버블 정렬에 대해 살펴본다. 아이디어 오름차순 정렬이라고 할 때, 모든 인접한 두 값을 비교하여 왼쪽의 값이 더 큰 경우 자리를 하나씩 바꾸는 과정을 반복해서 정렬한다. 버블 정렬은 왼쪽 -> 오른쪽, 오른쪽 -> 왼쪽 진행방향을 두 가지로 나눠서 생각해볼 수 있다. 하지만 결론은 동일하게 나타난다. 작동 원리 다음과 같은 데이터를 정렬하는 과정을 통해 실제 작동 원리를 살펴보자 . int[] arr = {50 20 30 10 40}; 50 20 30 10 40의 숫자 중에서 첫 번째부터 마지막까지 각각을 왼쪽에서부터 오른쪽으로 하나씩 옮겨가면서 비교를 한다. 예를 들어 다음과 같다. i=0) 1) 먼저 50과 20을 비교한다. 왼쪽의 값이 더 크므로 .. 2023. 6. 23. 금액 표기시 천 단위로 숫자에 컴마를 찍는 6가지 방식 (자바 구현 코드) 천 단위로 금액을 계수하기 쉽도록 컴마를 찍는 표기법을 자바 코드로 구현하는 방법을 알아본다. - 1000 -> 1,000 - 123456789 -> 123,456,789 아이디어의 몇 가지 포인트들은 다음과 같다. - 숫자형을 받아 문자형으로 리턴해야 한다. - 3자리 수에 착안한다. - 자릿수 정보를 이용하여 앞에서부터 붙이거나, 자릿수 정보 없이 뒤에서부터 붙이거나. - 나눗셈과 나머지 연산을 사용할 수 있다. - Regex를 이용할 수 있다. 크게 나머지 연산을 이용한 풀이법과 Regex를 이용한 풀이법으로 나뉜다. 1~5는 나머지 연산을 이용한 코드이고 마지막 코드는 Regex를 이용한다. 1. 반복문과 나눗셈을 이용한 방식 1 private static String convert(long mo.. 2023. 6. 21. 자바 숫자의 자릿수를 판별하는 5가지 방식 숫자의 자릿수를 판별하는 5가지 방식에 대해 살펴본다. 1. 나머지 연산과 반복문을 이용한 방식 public static int calculate(int number){ int count=0; while (number>0){ number /= 10; count++; } return count; } 동작 원리 주어진 숫자를 10으로 나눈 나머지를 계산한다. 나머지 연산을 통해 숫자의 가장 오른쪽 자릿수를 구하고, 해당 자릿수를 버린 숫자를 얻는다. 버린 숫자가 0보다 큰 경우, 자릿수를 하나 증가시키고 1단계로 돌아간다. 버린 숫자가 0인 경우, 반복문을 종료하고 자릿수를 반환한다. 예를 들어, 숫자 1234를 처리하는 경우 1234를 10으로 나누고 몫인 123을 얻는다. 그리고 자릿수를 하나 증가시키고.. 2023. 6. 21. 자바 문자열 역순 뒤집기 4가지 방법 문자열을 뒤집는 4가지 방법에 대해 소개한다. 결과적으로StringBuilder를 사용해 문자열을 조작하는 일이 대부분이겠지만 그래도 밑단의 알고리즘이 돌아가는 원리를 이해해보는 취지에서 여러 가지 방법을 생각해보았다. 1. 단순 반복문 이용 단순 반복문을 이용하여 뒤에서부터 탐색하고 하나씩 새로운 String으로 만든다. 다음 메서드는 하나의 매개변수 word를 받으며, 이를 뒤집어 리턴한다. public static String reverse(String word) { StringBuilder stringBuilder = new StringBuilder(); for (int i = word.length() - 1; i >= 0; i--) { stringBuilder.append(word.charAt(.. 2023. 6. 21. 이전 1 2 다음