본문 바로가기
Full Stack 교육 회고록

8/26 [자바]- 피보나치 수열, 버블정렬, 선택정렬, 이진탐색, 인터페이스

순두부 호랑이 2022. 8. 26. 17:49
728x90
SMALL

[재귀함수]

피보나치수열

fibo(1):첫번째 항구하기 -> 첫번째 항은 1로 정해져있다

fibo(2) -> 1 =0+1 -> 0이라는 값이 있다고 가정하기 fibo(0)+fib(1)

fibo(3) -> 2=fibo(1)+fibo(0)+fibo(1)

                                          ↓

                                      fibo(2)

fibo(n) = fibo(n-2)+fibo(n-1)

 

public class 피보나치 {

	public static void main(String[] args) {
		
		fiboPrint(7); //fibo()활용해서 특정항 까지 출력
		
		for(int i=1 ; i<=8; i++) {
			System.out.print(fibo(i)+" "); 			
		}

	}
	//
	public static void fiboPrint(int n) {
		for(int i=1 ; i<=n; i++) {
			if(i<=1) {
				System.out.println(i);
			}else {
			System.out.println(fibo(i-2)+fibo(i-1));
			}			
		}
	}

	//피보나치 수열에 특정 항의 값을 구하는 메서드
	public static int fibo(int n) {
		if(n<=1) {
			return n;
		}else {
			return fibo(n-2)+fibo(n-1);
		}
	}

}

 

정렬 알고리즘: 원소들을 일정한 순서대로 열거하는 알고리즘

 

선택정렬: 특정인덱스에 들어가는걸 차근차근 찾아감

삽입 정렬: 찾아서 중간에 삽입

버블 정렬:

병합 정렬:안에서 정렬후 통합

힙 정렬: 이진트리 형식 사용하여 정렬

퀵 정렬: 중심적으로 왼쪽을 위로 or  중심적 오른쪽을 위로

기수 정렬: 1의 자리숫자 먼저 확인하고 10의자리 숫자 확인

 

버블 정렬: 두 인접한 요소를 비교하여 정렬하는 방법 속도는 느리지만 코드가 단순함

 

<버블정렬 오름차순>

package 버블정렬;

import java.util.Arrays;

public class 버블정렬_오름차순 {

	public static void main(String[] args) {
		
		int[]arr= {10, 24, 7, 68, 42, 82, 3, 43};
		
		System.out.println("정렬 전 : " +Arrays.toString(arr));
		
		//버블정렬_오름차순
		//바깥쪽 반복문: 배열의 크기-1(크기 : 8 -> 반복문 :7)
		for(int i=0; i<arr.length-1; i++) {
			//안쪽반복문 : 0번 인덱스부터 인접요소 비교	
			//j : 기준(크기: 8인 배열, j:0~6(1회차) j:0~5(2회차))
			
			int cnt =0; //n회차 안쪽 반복문 실행 시 값이 바뀌는 횟수 카운팅
			boolean sw =false; // n회차 안쪽 반복문 실행 시 값이 한번이라도 바뀌면 -> true
			for(int j =0;j<arr.length-1-i;j++) {
				//0-1 -> 1-2 -> 2-3 -> 3-4
				if(arr[j]> arr[j+1]) {
					//j -> j+1 /j+1 -> j(치환)
					int temp = arr[j+1]; //둘 중 하나의 값으 임시적으로 저장
					arr[j+1] = arr[j];
					arr[j] = temp;
					cnt++;
					sw =true;
				}
			}
			if(!sw){ //sw 가 false 일때 반복문 나가게     !sw와 sw==false는 같은말이다
				//false -> true   true -> false
				break;
			}
			//더이상 바뀌는게 없으면 정렬을 수행(그다음 안쪽 반복문 실행)하지 않도록
			System.out.println(i+1+"번째 회 차 : "+ Arrays.toString(arr));
		}
	}

}
package 버블정렬;

import java.util.Arrays;

public class 버블정렬_내림차순 {

	public static void main(String[] args) {
		int[] arr = { 10, 24, 7, 68, 42, 82, 3, 43 };

		System.out.println("정렬 전 : " + Arrays.toString(arr));

		// 버블정렬_내림차순
		// 바깥쪽 반복문: 배열의 크기-1(크기 : 8 -> 반복문 :7)
		for (int i = 0; i < arr.length - 1; i++) {
			// 안쪽반복문 : 0번 인덱스부터 인접요소 비교
			// j : 기준(크기: 8인 배열, j:0~6(1회차) j:0~5(2회차))

			int cnt = 0; // n회차 안쪽 반복문 실행 시 값이 바뀌는 횟수 카운팅
			boolean sw = false; // n회차 안쪽 반복문 실행 시 값이 한번이라도 바뀌면 -> true
			for (int j = 0; j < arr.length - 1 - i; j++) {
				// 0-1 -> 1-2 -> 2-3 -> 3-4
				if (arr[j] < arr[j + 1]) {
					// j -> j+1 /j+1 -> j(치환)
					int temp = arr[j + 1]; // 둘 중 하나의 값을 임시적으로 저장
					arr[j + 1] = arr[j];
					arr[j] = temp;
					cnt++;
					sw = true;
				}
			}
			if (!sw) { // sw 가 false 일때 반복문 나가게 !sw와 sw==false는 같은말이다
				// false -> true true -> false
				break;
			}
			// 더이상 바뀌는게 없으면 정렬을 수행(그다음 안쪽 반복문 실행)하지 않도록
			System.out.println(i + 1 + "번째 회 차 : " + Arrays.toString(arr));
		}
	}

}

 

선택 정렬

가장 큰 원소 또는 작은 원소를 찾아 주어진 위치(리스트 처음~끝)를 교체해 나가는 방법

 

<선택정렬_오름차순>

package 선택정렬;

import java.util.Arrays;

public class 선택정렬_오름차순 {

	public static void main(String[] args) {
		
		int[] arr= {98, 7, 70, 13, 24};
		
		System.out.println("정렬 전 : "+Arrays.toString(arr));
		
		//3번 인덱스에 들어갈 숫자만 찾으면 4번 인덱스는 이미 확정이 되어있음
		for(int i=0; i<arr.length-1; i++) {
			//현재 가장 작은 숫자에 위치 기억
			//1회차 - 0 , 2회차 - 1, 3회사 - 2
			int index = i;
			for(int j=i+1;j<arr.length;j++) { //index번호 - index 번호 바로 뒷자리 부터 비교 시작 ~ 배열의 끝
				//인덱스 번호가 바뀔 조건
				if(arr[index]> arr[j]) { //지금까지 본 배열의 값중 가장 작은 값의 위치를 저장  //방향바꾸면 내림차순
				//현재 index가 가리키고 있는 자리 저장된 값 > 비교되고 있는 자리의 숫자) 
					index=j;
				//index가 비교되고 있는 자리를 가리키게 
				}				
			}//배열내에서 n번째 가장 작은 값의 위치 저장
			
			//찾은 값이 원하는 위치에 저장될 수 있게하는 코드
			//제일 작은 값 -> 0 두번째로 작은값 ->1		
			if(i!=index) {//원래 숫자의 자리와 제일 작은숫자 저장된 자리가 다를때만
				int temp = arr[index];
				arr[index]=arr[i];
				arr[i]=temp;
    	}
			System.out.println(i+1+"회차 : "+Arrays.toString(arr));
  }
 }
}

<선택정렬- 내림차순>

package 선택정렬;

import java.util.Arrays;

public class 선택정렬_오름차순 {

	public static void main(String[] args) {
		
		int[] arr= {98, 7, 70, 13, 24};
		
		System.out.println("정렬 전 : "+Arrays.toString(arr));
		
		//3번 인덱스에 들어갈 숫자만 찾으면 4번 인덱스는 이미 확정이 되어있음
		for(int i=0; i<arr.length-1; i++) {
			//현재 가장 작은 숫자에 위치 기억
			//1회차 - 0 , 2회차 - 1, 3회사 - 2
			int index = i;
			for(int j=i+1;j<arr.length;j++) { //index번호 - index 번호 바로 뒷자리 부터 비교 시작 ~ 배열의 끝
				//인덱스 번호가 바뀔 조건
				if(arr[index] < arr[j]) { //지금까지 본 배열의 값중 가장 작은 값의 위치를 저장 
				//현재 index가 가리키고 있는 자리 저장된 값 > 비교되고 있는 자리의 숫자) 
					index=j;
				//index가 비교되고 있는 자리를 가리키게 
				}				
			}//배열내에서 n번째 가장 작은 값의 위치 저장
			
			//찾은 값이 원하는 위치에 저장될 수 있게하는 코드
			//제일 작은 값 -> 0 두번째로 작은값 ->1		
			if(i!=index) {//원래 숫자의 자리와 제일 작은숫자 저장된 자리가 다를때만
				int temp = arr[index];
				arr[index]=arr[i];
				arr[i]=temp;
    	}
			System.out.println(i+1+"회차 : "+Arrays.toString(arr));
  }
 }
}

 

검색 알고리즘 :특정 원소를 검색하는 알고리즘

순차 검색: 가장 단순한 검색방법으로 원소의 정렬이 필요 없다 하지만 리스트 길이가 길면 비효율적

이진 검색: 리스트의 중간 값을 정해 크고 작음을 비교해 검색하는 알고리즘 정렬된 리스트에 사용할 수 있다

                   더 작은 수로/ 내가 봐야 하는 배열의 중간값 찾기

<이진 탐색>

package 이진탐색;

public class 이진탐색 {

	public static void main(String[] args) {
		
		//이진탐색 : 정렬이 되어있는 배열에서만 사용(사전)
		int[]arr = {1,7,19,25,30,33,41,66,78,90};
		
		int num = 78; // 내가 찾고 싶은 숫자
		
		int lowIndex=0; //찾아야하는 배열의 구역중 가장 낮은 인덱스 번호 포인터
		int highIndex=arr.length-1; //가장 높은 인덱스 번호 포인터
		
		while(true) {
			//현재 봐야하는 배열 구역중에서 센터 찾아야함!
			int centerIndex = (lowIndex+highIndex)/2;
			if(arr[centerIndex]==num) {
				System.out.println(centerIndex);
				break;
			}else {
				if(arr[centerIndex]>num) {
					highIndex = centerIndex-1;
				}else { //arr[centerIndex]<num
					lowIndex = centerIndex+1;
				}
			}
		}
	}

}

 

interface(인터페이스)-구현예시

 

jdbc

 

<Animal.java>

package Ex01;

public class Animal {
	
	public void eat() {
		System.out.println("냠냠 먹기!");
	}
	
	public void move() {
		System.out.println("휘적휘적 움직이기!");
	}

}

<AnimalMain>

package Ex01;

public class AnimalMain {

	public static void main(String[] args) {
		
		//Dog 객체가 잘 생성되고 사용이 되는지 확인해보기
		Dog d = new Dog();
		
		System.out.print("Dog 객체 : ");
		d.eat();
		
		Cat c = new Cat();
		
		System.out.print("Cat 객체 : ");
		c.eat();
		
		// 형변환(Casting)
		// - 기본 데이터 타입에 대한 형변환 -> 데이터의 크기를 변환하는 기능
		// - 객체 타입에 대한 형변환 -> 객체의 타입을 변환하는 기능
		// - 객체 타입에 대하여 형변환을 진행 할 때, 꼭! 상속의 개념이 있어야 한다
		
		//묵시적(자동) 형변환 -> 업캐스팅 개념
		// : 자식 클래스가 부모 클래스의 타입으로 형태가 변형 되는 것
		// ex) 강아지(자식)는 동물(부모)이다 -> O
		//     고양이는 동물이다 -> O
		
		System.out.println();
		System.out.println("-----업캐스팅-----");

		Animal a1 = new Dog();
		a1.eat();
		
		Animal a2 = new Cat();
		a2.eat();
		
		//명시적(강제) 형변환 -> 다운캐스팅
		//동물은 강아지다 -> X
		
		//Dog d1 = (Dog) new Animal();
		//문법적으로는 문제가 없으나 실행시 오류가 발생한다 -> 런타임 오류
		
		//업캐스팅 되어 있는 객체가 원래의 객체타입으로 돌아가는 것!
		System.out.println();
		System.out.println("-----다운캐스팅-----");
		
		Dog d1 =(Dog) a1;
		d1.eat();
		
		Cat c1 = (Cat) a2;
		c1.eat();

	}

}

<cat>

package Ex01;

public class Cat extends Animal{
	
	public void eat() {
		System.out.println("츄르 냠냠");
	}

}

<dog>

package Ex01;

public class Dog extends Animal{
	
	public void eat() {
		System.out.println("뼈다귀 냠냠");
	}

}

<<햄버거 만들기>

Burger

package Ex02;

public class Burger {
	
	public void make() {
		System.out.println("기본 햄버거 만들기");
	}

}

CheeseBurger

package Ex02;

public class CheeseBurger extends Burger {
	
	public void cheesemake() {
		System.out.println("치즈버거 만들기!");
	}
	
	//자식이 부모의 기능을 불러오기 위한 메소드
	public void make() {
		super.make();
	}

}

BurgerMain

package Ex02;

public class BurgerMain {

	public static void main(String[] args) {
		
		Burger burger = new Burger();
		
		CheeseBurger cheese = new CheeseBurger();
		
		burger.make();
		cheese.cheesemake();
		
		System.out.println();
		
		Burger b1 = new CheeseBurger();
		b1.make();
		
		System.out.println();
		
//		CheeseBurger c1 = (cheeseBurger) b1;
		cheese.make();
		cheese.cheesemake();


	}

}

<인형뽑기>

<Machine>

package Ex03;

public class Machine {
	
	//인형을 뽑을 수 있는 기계
	//기계 안에 피카츄/ 파이리/ 꼬부기 -> 인형 이라는 공통점!
	
//	public void pick(Pika p) { //피카츄 인형
//		p.pika();
//	}
//	public void pick(Pairi p) { //파이리 인형
//		p.pairi();
//	}
//	public void pick(Kkobuk k) { //꼬부기 인형
//		k.Kkobuk();
//	}
	
	public void pick(Doll d) {
		d.doll();
	}

}

<Pika>

package Ex03;

public class Pika extends Doll {
	
	public void doll() {
		System.out.println("피카츄 인형!");
	}

}

<Pairi>

package Ex03;

public class Pairi extends Doll {
	
	public void doll() {
		System.out.println("파이리 인형!");
	}

}

<kkobuk>

package Ex03;

public class Kkobuk extends Doll {

	public void doll() {
		System.out.println("꼬부기 인형!");
	}
}

<machinemain>

package Ex03;

import java.util.Random;

public class MachineMain {

	public static void main(String[] args) {
		
		//인형뽑기 기계가 실제로 실행될 수 있는 곳!
		
		Machine m = new Machine();
		
		Pika pika = new Pika();
//		m.pick(pika);
		
		Pairi pairi = new Pairi();
//		m.pick(pairi);
		
		Kkobuk kkobuk = new Kkobuk();
//		m.pick(kkobuk);
		
		System.out.println();
		System.out.println("랜덤 인형뽑기");

		//랜덤으로 인형을 뽑아보자!
		Doll[]dolls = {pika, pairi, kkobuk};
		
		Random rd = new Random();
		int choice = rd.nextInt(dolls.length);
		
		m.pick(dolls[choice]);
	}

}

<doll>

package Ex03;

public class Doll {
	
	//만들어 지는 여러 인형들을 관리할 수 있는 부모 클래스!
	public void doll() {
		System.out.println("인형 입니다~");
	}

}

 

 

 

728x90
LIST

'Full Stack 교육 회고록' 카테고리의 다른 글

8/30 [JAVA]- JDBC 응용  (0) 2022.08.30
8/29 [java] - jdbc,mvc  (0) 2022.08.29
8/25 [자바 자료구조]- 트리 [자바]- 인터페이스  (0) 2022.08.25
8/24 - 자료구조  (0) 2022.08.24
8/23 [자료구조]-선형구조,비선형구조  (1) 2022.08.23

'Full Stack 교육 회고록' Related Articles

티스토리툴바