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