Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 재귀 알고리즘의 비재귀적 표현 static void recur(int n) { if(n > 0) { recur(n - 1); System.out.println(n); recur(n-2); } } 위 메소드의 꼬리 재귀를 제거하는 방법과 비재귀적 표현으로 나타내는 방법을 정리하려고 한다. 꼬리 재귀의 제거 메소드의 꼬리에서 재귀 호출하는 메소드 recur(n-2)는 파라미터로 n-2를 전달하여 recur 메소드를 호출한다는 뜻이다. 따라서 이 호출은 'n의 값을 n-2로 업데이트하고 메소드의 시작 지점으로 돌아간다'는 뜻이다. 아래는 위 방법을 그대로 구현한 코드이다. n의 값을 -2만큼 감소한 후 메소드의 시작 지점으로..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 재귀란 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(Recursive)이라고 한다. 재귀는 직접 재귀와 간접 재귀로 나뉜다. 직접 재귀 : 메소드 a가 자신(메소드 a)을 호출 간접 재귀 : 메소드 a가 메소드 b를 호출하고, 메소드 b는 메소드 a를 호출 재귀 메소드는 정지조건(재귀 앵커)을 제대로 설정하지 않으면 무한 루프와 같이 끝없이 재귀 메소드가 호출되므로 유의하여야 한다. 팩토리얼 구하기 음이 아닌 정수 n의 팩토리얼(n!)은 아래처럼 재귀적으로 정의할 수 있다. 0! = 1 n > 0 이면 n! = n * (n-1)! 위의 정의를 그대로 구현하면 아래와 같다. static ..

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! 자료구조와 함께 배우는 알고리즘 입문[자바편] 연습문제와 실습문제입니다. 클래스 배열이란 클래스로 부터 만들어진 객체로 이루어진 배열을 뜻한다. 클래스 자체가 자료형이되어서 데이터를 더 쉽게 다룰 수 있다. 아래는 이름, 키, 시력을 저장하는 클래스의 객체로 이루어진 배열을 활용하여 평균 키와 시력 분포를 출력하는 예제 코드이다. public class Main{ static class PhyscData { //이름, 키, 시력을 저장하는 클래스 String name; int height; double vision; PhyscData(String name, int height, double vision) { //생성자 this.name = name; this.height = height; t..

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