728x90
728x90
4장의 스택과 큐의 경우 이전에 따로 포스팅한적이 있기 때문에 (중복되는 내용밖에 없어서....) 과감히 생략하고(혼자 공부하고) 5장의 재귀 알고리즘을 정리한다. 재귀란? 어떤 사건이 자기 자신을 포함하고 다시 자기자신을 사용하여 정의될 때, 재귀적이라고한다. (*참고: 뒤에서 배울 '병합정렬', '퀵 정렬', '이진 검색 트리' 등에 사용된다) 재귀 호출(recursive call): 재귀적으로 호출된다는 말 그대로의 의미이고, 직접 재귀와 간접 재귀로 나뉜다. 직접 재귀 VS 간접 재귀 직접 재귀란 어떤 메서드 내부에서 자기 자신(메서드)을 직접 호출하는 것이고, 간접 재귀는 메서드 a가 메서드 b를 호출하고, 다시 메서드 b가 메서드 a를 호출하는 구조로 이루어진다. 유클리드 호제법 두 정수의 최..
이 글은 'Do it! 자료구조와 함께 배우는 알고리즘 입문 (자바 편)' 책(이번 포스팅의 경우 chap3)을 보고 정리한 내용입니다. (기본적인 자바 문법을 안다는 가정에서 기본적인 부분(사람마다 다르겠지만...)위주로 정리한다. 3장에서는 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘에 대해 살펴본다. 검색과 키 주소록을 검색한다고 가정했을 때, 검색(searching)은 다음과 같은 과정으로 이루어진다. 국적이 한국인 사람을 찾는다 나이가 21세이상 27세 미만인 사람을 찾는다 찾으려는 이름과 가장 비슷한 이름의 사람을 찾는다 위의 검색뿐만 아니라 어떤 검색을 하게 되더라도 특정 항목에 주목한다는 점은 '검색하기'의 공통점이다. 여기서 그 주목하는 항목을 키(key)라고 하면, ..
오늘은 최대공약수 알고리즘을 구현 및 사용하는 방법에 대해 알아보자! GCD는 Greatest Common Divisor로 최대 공약수이다. 최대공약수는 두 수의 공통 약수중 최댓값을 말합니다. (약수는 나누어서 0 이 되는 수를 말한다) 이렇게 나누어서 0 이 되는 수중 공통적으로 들어가 있으며, 최댓값을 찾는 것입니다. 자바에서는 BigInteger 클래스에 최대공약수를 구할 수 있는 gcd() 함수를 제공합니다. 함수를 이용해서 구하는 방법과 직접 함수를 만드는 방법에 대해 알아 본다. 1. BigInteger 내장 함수를 사용 private static int gcdThing(int a, int b) { BigInteger b1 = BigInteger.valueOf(a); BigInteger b2..
참고: https://gorakgarak.tistory.com/522 순열(Permutation) 알고리즘 1,2,3 와 같은 숫자들이이 있다. 이것을 중복하지 않고 순서를 끌어내는 방법을 생각해보자 1-2-3 1-3-2 2-1-3 2-3-1 3-1-2 3-2-1 여섯가지 방법이 존재한다. 이제 숫자 네개인 1,2,3,4를 한번 섞어본다. 1-2-3-4.. gorakgarak.tistory.com 프로그래머스의 코딩 테스트 문제 중에서 완적 탐색 기법 lever2 단계인 '소수 찾기'를 풀다가 '순열'의 개념이 필요하게 되었다. 직접 구현해보려고 했으나, 쉽지않아서 구글링을 통해서 학습하였다. (알고리즘이 직관적으로 이해하기가 쉽지 않아 꽤 오랜 시간 손 코딩을 하면서 따라가며 이해하였다) 참고: htt..