본문 바로가기
728x90

기타/java 자료구조와 알고리즘

 (15)
자바 배열 선택정렬 선택 정렬은 가장 작은 요소를 찾아 앞으로 보내 배열을 정렬하는 알고리즘입니다. 첫 인덱스부터 하나씩 비교해가며 가장 작은 값을 찾아 맨 앞의 인덱스와 바꾸고 맨 앞 인덱스가 1이면 그 이후의 값들을 비교해 가장 작은 값을 인덱스 1로 보냅니다. 이 과정을 마지막에서 두 번째 인덱스까지 진행합니다. int[] a = {3,4,2,1,5}; for(int i=0;i
[JAVA] 버블 정렬 코드 예제 버블 정렬은 인접한 두 요소를 검사하고 정렬하는 알고리즘입니다. 5,4,3,2,1이라는 배열이 있다고 해봅시다. 버블 정렬을 사용해 오름차순으로 정렬하면 1. 4,3,2,1,5 5와 비교하면서 5보다 작을 경우 위치를 바꿉니다. 2.다음으로 제일 끝 인덱스 전까지 인접한 요소들 끼리 서로 비교하며 위치를 바꿉니다. 3,2,1,4,5 이과정을 반복하면 1,2,3,4,5로 정렬됩니다. 5개의 요소가 있을때 총 큰 틀에서 4번의 검사가 진행됩니다. 코드로 구현해 보도록 하겠습니다. static void bubblesort(int[] a, int n) { for (int i = 0; i
재귀 알고리즘 : 8퀸 문제 8퀸 문제는 8*8의 체스판에서 퀸 8개를 서로 공격할 수 없게 배치하는 경우의 수를 구하는 문제입니다. 수학자 사우스가 틀린 것으로도 유명하죠. 정답을 만족하기 위해서는 몇가지 조건을 반드시 지켜야 합니다. 1. 각 열에는 퀸을 1개만 배치한다. 2. 각 행에 퀸을 1개만 배치한다. 3. 대각선을 그엇을 때 그위에 퀸이 1개만 있도록 한다.(대각선은 총 30개입니다.) 이 조건을 만족하는 퀸의 배치 경우의 수를 구해야 합니다. public class eightqueen{ //가로에 퀸이 있으면 true 없으면 false 저장하는 배열 static boolean[] a= new boolean[8]; //우상향 대각선에 퀸이 있으면 true 없으면 false을 저장하는 배열 static boolean[] ..
자바 재귀함수 하노이탑 풀이 하노이탑은 작은 원반 위에 큰원반이 위치할 수 있도록 원반을 다른 기둥으로 옮기는 문제입니다. 핵심 규칙은 큰 원반 아래에 작은 원반이 올 수 없다는 것이지요. 이것을 재귀를 통해 풀어보도록 하겠습니다. 3개의 원반이 있다고 할 때 먼저 가장 먼저 해야할 것은 두개의 원반을 옮기기로 한 기둥과 다른 기둥으로 옮기는 것입니다. 예를 들어, 3개의 원반을 1기둥에서 3기둥으로 옮긴다고 할 때 2개의 원반을 1기둥에서 2기둥으로 옮겨야 합니다. 원반 3을 기둥 3으로 옮긴 후 2개의 원반을 2기둥에서 3기둥으로 옮겨야 합니다. 두개로 갈라집니다. 2개의 원반을 1->2기둥으로 옮기고 원반 3을 기둥 1->3으로 옮기고 2개의 원반을 2->3으로 옮깁니다. 즉 두개의 재귀가 필요합니다. 2개의 원반을 옮기는 과..
재귀 알고리즘 비재귀로 표현하기 재귀 알고리즘을 비재귀적으로 표현할 수 있습니다. 아래와 같은 재귀 알고리즘을 static void abc(int n) { if(n>1) { abc(n-1); } System.out.println(n); } public static void main(String[] args) { abc(4); } 1 2 3 4 같은 답이 나옵니다. for(int i=1; i
재귀 함수 알고리즘 예 하향식,상향식 분석하기 재귀 알고리즘은 복잡해서 이해하기 어렵습니다. 하향식, 상향식 분석을 이용하면 보다 쉽게 이해할 수 있습니다. 하향식 분석은 맨 위의 재귀에서 시작해 아래 단계로 가면서 하나하나 조사하는 것이고 상향식 분석은 가장 아랫단의 재귀부터 시작해 가장 위의 재귀까지 조사하는 것입니다. 예를 통해 살펴보록 하겠습니다. static void abc(int n) { if(n>1) { abc(n-1); abc(n-2); } System.out.println(n); } public static void main(String[] args) { abc(4); } 결과 : 1 0 2 1 3 1 0 2 4 코드는 간단하지만 결과는 복잡합니다. 1. 하향식 분석 -n에 4가 들어가면 abc(3) 재귀가 시작됩니다. abc(3)이..
[JAVA]유클리드 호제법이란? 유클리드 호제법은 두 정수의 최대 공약수를 재귀적으로 구하는 방법입니다. 방식은 간단합니다. 100과 10의 최대 공약수를 구한다고 했을 때, 10,100%10이 다시 재귀로 함수 안에 들어갑니다. 그렇게 되면 100%10은 0이므로 첫번째 조건에 들어가고 10이 반환됩니다. 재귀 종료 조건은 큰 값을 작은 값으로 나누었을 때의 나머지가 0일 때이므로 첫 번째 조건은 n_2이==0이다. 그렇지 않으면 큰 값을 작은 값으로 나눈 나머지와 작은 값을 다시 함수에 넣지요. static int gcd(int n_1, int n_2) { if(n_2==0) { return n_1; } else { return gcd(n_2,n_1%n_2); } } public static void main(String[] arg..
[JAVA]자바 재귀함수로 팩토리얼 계산기 만들기 재귀는 자기 자신을 반복하는 것입니다. 재귀의 대표적인 예가 팩토리얼입니다. 팩토리얼은 n을 포함한 그보다 작은 자연수를 모두 곱하는 것입니다. n!로 표기할 수 있는데 5! 는 5*4*3*2*1로 120입니다. 5! 은 5*4!로 4! 은 4*3!로 3! 은 3*2!로 2! 은 2*1로 나타낼 수 있습니다. n*(n-1)!로 나타낼 수 있습니다. 자바 코드로 나타내면 아래와 같습니다. public class javaarray{ static int factorial(int n) { if(n>0) { return n*factorial(n-1); } else { return 1; } } } n이 0보다 클 경우 n*factorial(n-1)를 반환하고 아닐 경우에는 1을 반환합니다. 3이면 3*factori..
728x90

티스토리툴바