11. 14 알고리즘 강의/ JAVA 기초 강의/ 그림으로 배우는 알고리즘/ Leetcode

1. 알고리즘 강의

Dynamic Programming(동적 계획법)

1) 피보나치 수열: 첫째, 둘째항이 1이며 그 뒤의 모든 항은 앞의 두 수의 합 표시되는 수열

 

*피보나치 수열 구현 : 재귀함수

input = 20


def fibo_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)


print(fibo_recursion(input))  # 6765

#내가 쓰기엔 매우 간단해 보이지만,

출처: 강의자료. 피보나치 수열 5항을 구하기 위해 계속 반복해야한다

 

동적 계획법: 복잡한 문제를 간단한 여러 문제로 나누어 푸는 것

조건 1. 반복되는 형태로 문제가 계속해서 파생되는 게 있다.

조건 2. 메모이제이션을 위한 메모가 필요하다

input = 100

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}
#1. 만약 메모에 있으면 그 값을 바로 반환하고
#2. 없으면 아까 수식대로 구한다
#3. 그리고 그 값을 다시 메모에 기록한다.


def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo)
    fibo_memo[n] = nth_fibo
    return nth_fibo


print(fibo_dynamic_programming(input, memo))

참고)

방식 : Top down 방식과 Bottom up 방식이 있다

 

2. JAVA 기초강의

객체지향 프로그래밍: 객체들 간의 상호 작용을 코드로 표현한 것이다

1) 객체 지향 언어 : 접근 제어자

왜 사용할까? : 상호 작용간 클래스 내부에 선언된 데이터에 부적절한 접근을 막기 위해 ~ 캡슐화

→ private : 같은 클래스 내에서만 접근이 가능합니다

→ default(nothing) : 같은 패키지 내에서만 접근이 가능합니다.

→ protected : 같은 패키지 내에서, 그리고 다른 패키지의 자손클래스에서 접근이 가능합니다.

→ public : 접근 제한이 전혀 없습니다.

 

Super : 상속받은 부모클래스를 가리키는 키워드

import pkg.ModifierTest;

class Child extends ModifierTest {
    void callParentProtected() {
        System.out.println("call my parent's protected method");
        super.messageProtected();
    }
}
//패키지 클래스를 호출할때 패키지 이름까지 포함한 클래스 이름이 정확한 이름이다 ex) pkg.modifier != pkg2.modifier
public class Main {
    public static void main(String[] args) {
        ModifierTest modifierTest = new ModifierTest();
        modifierTest.messageOutside();
        //modifierTest.messageInside(); 같은 클래스 내
        //modifierTest.messageProtected(); 같은 패키지, 상속 시
        //modifierTest.messagePackagePrivate(); 같은 패키지 내

        Child child = new Child();
        child.callParentProtected(); //자식 클래스에서 호출하므로 출력가능
    }
}

2) 객체 지향 언어: 추상클래스, 인터페이스

 

추상 클래스: 추상메소드를 선언할 수 없는 클래스, 상속받는 클래스 없이 그 자체로 인스턴스 생성이 불가능하다

 

추상 메소드:

설계만 되어 있으며, 자식클래스에서 반드시 오버라이딩(abstract 클래스를 상속하는 클래스에서 해당 abstract 메소드를 구현)해야만 사용 가능한, 수행 코드가 미작성된 메소드 =

메소드 시그니쳐(메소드 이름, 파라미터 목록)만 작성되어 있다

자식클래스에서 무조건 오버라이딩이 일어나는 경우에 효율을 위해 추상메소드로 작성한다

출처: https://www.scaler.com/topics/method-signature-in-java/, 두 메소드 시그니쳐는 다른 것으로 인식된다

abstract class Bird {
    private int x, y, z;

    void fly(int x, int y, int z) {
        printLocation();
        System.out.println("이동합니다");
        this.x = x;
        this.y = y;
        if(flyable(z)) {
            this.z = z;
        } else {
            System.out.println("그 높이로는 날 수 없습니다");
        }
        printLocation();
    }

    abstract boolean flyable(int z); //추상메소드는 중괄호를 추가하는 것이 불가능하다
    // 구현체가 없지만, fly 메소드에서 구현체가 있는 것처럼 실행되고, 그 내용은 자식 클래스인
    // pigeon, peacock 클래스에 구현되어 있다.

    public void printLocation() {
        System.out.println("현재 위치 (" + x + " , " + y + " , " + z + ")");
    }
}

class Pigeon extends Bird {
    //Override
    boolean flyable(int z) {
        return z < 10000;
    }
}

class Peacock extends Bird {
    boolean flyable(int z) {
        return false;
    }
}

public class Main {
    public static void main(String[] args) {
        //Bird bird = new Bird(); (X) 추상클래스는 그 자체로 인스턴스를 생성할 수 없다
        Bird pigeon = new Pigeon();
        Bird peacock = new Peacock();
        System.out.println("-- 비둘기 --");
        pigeon.fly(1, 1, 3);
        System.out.println("-- 공작새 --");
        peacock.fly(1, 1, 3);
        System.out.println("-- 비둘기 --");
        pigeon.fly(3, 3, 30000);
    }
}

인터페이스: 객체의 특정 행동의 특징에 대한 문법, 다중 상속의 개념이 필요할 때(다중 상속은 아니다) 사용한다

함수의 특징(method signature)인 접근제어자, 리턴타입, 메소드 이름만을 정의

인터페이스 타입으로 선언된 변수는 인스턴스가 어느 클래스에서 생성된 지에 관계없이, 인터페이스에 정의된 행동만 할수 있다

interface Bird {
    void fly(int x, int y, int z);
}

class Pigeon implements Bird{
    //인터페이스에 필드가 없으므로(생성할 수 없으므로), 자식 클래스에 필드를 생성한다
    private int x,y,z;

    @Override
    public void fly(int x, int y, int z) {
        printLocation();
        System.out.println("날아갑니다.");
        this.x = x;
        this.y = y;
        this.z = z;
        printLocation();
    }
    public void printLocation() {
        System.out.println("현재 위치 (" + x + ", " + y + ", " + z + ")");
    }
}

public class Main {

    public static void main(String[] args) {
        Bird bird = new Pigeon();
        bird.fly(1, 2, 3);
//        bird.printLocation(); // compile error
    }
}

3. 그림으로 배우는 알고리즘

1장 알고리즘이란

4. Leetcode

로마 글자를 정수로 변환 :

13. Roman to Integer