Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 이진 검색 이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다. 하지만 이진 검색은 데이터가 키 값으로 이미 정렬되어 있다는 전제 조건이 있어야 한다. 이진 검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 시간 복잡도 측면에서 선형 검색은 O(N)이지만 이진 검색은 O(log N)을 가지므로 이진 검색이 훨씬 효율적인 알고리즘이다. 아래와 같은 배열에 오름차순으로 정렬된 데이터에서 39를 찾는 과정을 예로 들면, 먼저 배열 중앙에 위치한 5번째 인덱스부터 검색을 시작한다. 인덱스 5의 값은 31은 39보다 작으므로 검색 대상을 뒤쪽 5개로 좁힐 수 있다. 그런 다음 검..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 선형 검색(순차 검색) 선형 검색은 직선 모양으로 늘어선 배열에서 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 것을 말한다. 선형 검색에서 검색의 종료 조건은 아래의 2개와 같다. 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 검색할 값과 같은 요소를 발견한 경우 첫 번째 조건이 성립하면 검색 실패, 두 번째 조건이 성립하면 검색 성공이다. 배열의 요솟수가 n개이면 조건 1, 2를 판단하는 횟수는 평균 n/2회이다. public class Main{ static int seqSearch(int[] arr, int key) { for(int i = 0; i < arr.length; ..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 2023.01.01을 기준으로 100일 전은2022년 9월 23일(기준날 미포함)이고, 100일 후는2023년 4월 11일이다. 이러한 알고리즘을 자바로 구현하면 아래와 같다. 클래스 선언부 static class YMD { int year; int month; int day; YMD(int y, int m, int d) //생성자 { this.year = y; this.month = m; this.day = d; } int[][] arr = { {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}, //평년 arr[0][] {31, 29, 31, 30, 31, 30, 31, 31, 3..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 4월 15일을 예로 들면 그 해의 경과 일수를 구하면 아래와 같다. 1월의 일 수 + 2월의 일 수 + 3월의 일 수 + 15 m월 d일의 그 해 경과 일수는 아래와 같다. 1, 2, ..., m-1월의 일 수의 합 + d 그런데 2월의 일 수는 평년은 28일, 윤년은 29일로 해에 따라 달라진다. 윤년, 평년 지구가 태양 둘레를 한 바퀴 도는 일수는 정확히 365일이 아니다. 이를 조정하기 위해 4로 나누어 떨어지는 해를 윤년으로 하여 1년을 366일로 한다. 하지만 그래도 정확하기 않으므로 아래와 같은 규칙을 적용한다. -해당 연도를 4로 나누어 떨어지면 우선 윤년으로 하고 -윤년 중에서 100으로 나누어 떨어지면 ..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 소수 소수는 자신과 1 이외의 정수로 나누어떨어지지 않는 정수이다. 예를 들어 소수 13은 2, 3, ..., 12 가운데 어떤 정수로도 나누어 떨어지지 않는다 그러므로 어떤 정수 n에 대하여 아래의 조건을 만족하면 소수임을 알 수 있다. "소수 n은 2부터 n-1까지의 어떤 정수로도 나누어 떨어지지 않는다." 만약 나누어 떨어지는 정수가 하나 이상 존재하면 그 수는 합성수이다. n 이하의 소수를 나열하는 알고리즘 (시간복잡도 높음, 공간복잡도 낮음) static void PrimeNumber(int n) { for(int i = 2; i

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 10진수를 n진수로 변환하는 방법을 모른다면 아래의 포스팅에서[10진수-n진수 변환] 부분을 읽고 오시는 것을 추천합니다. 2022.11.29 - [Math/이산수학] - 진수, 진법 변환, 보수 진수, 진법 변환, 보수 [진수] [10진수] 기수가 10인 수 0, 1, 2 ,3, 4, 5, 6 ,7, 8, 9 -> 10개 수로 표현 [2진수] 기수가 2인 수 0, 1 두개의 수로 표현 [8진수와 16진수] [8진수] 0~7까지 8개의 수로 표현 2진수 3자리는 8진수 1자리 2진수 rebugs.tistory.com 10진수를 2~36진수로 변환하는 알고리즘 static void cardConvR(int x, int r..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 배열 비교 두 배열의 모든 요소의 값이 같은지를 판단하는 알고리즘 static boolean equals(int[] a, int[] b) { if(a.length != b.length) return false; //배열의 길이가 다르면 false 리턴 for(int i = 0; i < a.length; ++i) if(a[i] != b[i]) return false; //요소의 값이 다르면 false 리턴 return true; //배열의 길이가 같고, 모든 요소의 값이 같으면 true 리턴 } 아래는 실행예제 public class Main{ static boolean equals(int[] a, int[] b) { i..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 배열의 요소가 1, 2, 3, 4, 5, 6, 7 이렇게 7개 있다고 하면 역순으로 정렬하면 7, 6, 5, 4, 3, 2, 1이다. 그림에서 보는 것과 같이 요소들을 서로 바꿔주면 된다. 요소들을 바꿔주려면 먼저 swap함수를 정의해야한다. static void swap(int[] arr, int a, int b) //배열의 요소 값을 스왑 { int temp; temp = arr[a]; arr[a]= arr[b]; arr[b] = temp; } 매개변수 a와 b에 교환할 배열의 인덱스를 받고, 인덱스 a의 값과 인덱스 b의 값을 바꾼다.(swap) 이 swap 메소드를 응용해서 요소를 역순으로 정렬하는 알고리즘을 구..