tenid's dev

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요함
• 현재 상황에서 단순히 가장 좋아 보이는 것만을 반복적으로 선택했을 경우 최적의 해가 될 수 있는지 검토해야 하기 때문에 정당성 분석이 중요하다.

각 노드 상황마다 최적의 해를 찾을 경우 총합은 4+10+5 = 19 이지만 사실은 진짜 최적의 해는 4 + 9 + 8 = 21이다.

따라서 지금 같은 상황에서는 그리디 알고리즘이 최적의 해를 보장할 수 없다 라고 표현한다.

그렇기 때문에 코딩 테스트에서 출제 되는 그리디 문제는 탐욕법으로 풀었을 경우 최적의 해가 보장 되는 경우에 출제가 된다.

[문제] 거스름 돈

어느 가게에 계산을 도와주는 점원이 있다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 가게를 방문한 손님은 점원에게 N원의 돈을 지불 했을 경우에 교환 받는 동전의 최소 개수는 몇개 인가? 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

- 해법:

가장 큰 화폐부터 돈을 거슬러 준다. 

이 정당성이 검증이 되는 이유에는 거스름 돈중 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위들을 종합해 다른 해가 나올 수 없기 때문이다.

ex) 1000원을 600원,500원,100원으로 거슬러 줄 경우 :

탐욕법(600원 1개 ,100원 4개), 최적의 해 (500원 2개)

- 시간 복잡도:

화폐의 종류가 N개 이면, for문이 화폐의 종류만큼 반복되기 때문에 시간 복잡도는 O(N)

- 코드:

n = 1260
count = 0

# 큰 단위부터 교환
array = [500,100,50,10]

for money in array:
    # 거슬러준 동전 갯수
    count += n // money
    # 교환 하고 남은 잔액
    n %= money


print(count)

- 결과:

6

• 내장 함수: 기본 입출력, 정렬 등의 기본적인 함수
• itertools: 반복되는 데이터 처리 ex) 순열,조합
• heapq: 힙 자료구조 ex) 큐, 다익스트라 최단 경로
• bisect: 이진 탐색
• collections: 덱(deque), 카운터(Counter) 등 자료구조
• math: 수학적 기능 ex) 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련함수 및 파이(pi)와 같은 수학적 상수

함수명	역할	결과
sum(iterable)	iterable안 변수 안에 수를 모두 더한 후 그 결과를 반환한다.
min(arg1, arg2, ... )	매개변수에 있는 변수들 중 가장 작은 값을 반환한다.
max(arg1, arg2, ... )	매개변수에 있는 변수들 중 가장 큰 값을 반환한다.
eval(expression, globals=None, locals=None)	문자열로 표현된 식을 수학적으로 계산한 후 그 결과를 반환한다. ※ 문자열을 그대로 실행하기 때문에 프로그램 개발 시에 나쁜 의도로 코드 내용을 삽입하여 보안이 취약할 수 있다.
sorted(iterable, *, reverse=False)	변수안에 원소들을 정렬하여 반환한다.
sorted(iterable, *, key=None, reverse=False)	key에 함수를 기준으로 정렬하여 반환한다.

# 순열과 조합

• 순열: 서로 다른 n개에서 서로 다른 r개를 선택
• 조합: 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택

# 순열 예시

from itertools import permutations

data = ['A', 'B', 'C']

result = list(permutations(data, 3))
print(result)

data에서 순서가 상관있게 서로 다른 3개를 선택한다.

- 결과 화면

# 조합 예시

from itertools import combinations

data = ['A', 'B', 'C']

result = list(combinations(data, 2))
print(result)

data에서 순서가 존재하는 순서에 상관없이 2개를 선택한다.

- 결과 화면

# 중복 순열

from itertools import product

data = ['A', 'B', 'C']

result = list(product(data, repeat=2))
print(result)

- 결과 화면

#중복 조합

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']

result = list(combinations_with_replacement(data, 2))
print(result)

- 결과화면

# Counter

• collections 라이브러리에 속한 함수로써 등장 횟수를 세는 기능
• 리스트와 같은 반복 가능한 객체가 주어졌을 때 내부의 원소가 몇 번 등장했는지를 반환

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])

print(counter['blue'])
print(counter['green'])
print(dict(counter))

- 결과 화면

# 최대 공약수와 최소 공배수

math.gcd()를 이용해서 최대 공약수를 구할 수 있다. 이것을 이용하면 최소 공배수도 얻어낼 수 있다.

import math


# 최소 공배수(LCM)를 구하는 함수
def lcm(a, b):
    return a * b // math.gcd(a, b)


a = 21
b = 14

print(math.gcd(a, b))  # 최대 공약수(GCD) 계산
print(lcm(a, b))  # 최소 공배수(LCM) 계산

- 결과 화면

람다 표현식은 흔히 이름없는 함수라 불리며, 이것을 이용하면 함수를 간단하게 작성할 수 있다.

특정 기능을 수행하는 함수를 한 줄에 작성할 수 있다는 점이 특징이다.

# 일반적인 add() 메서드 사용
def add(a,b):
	return a+b
    
# 람다 표현식으로 구현한 add() 메서드
print((lambda a,b:a+b)(3,7))

※ (lambda 변수명: 연산식)(변수명)

# 내장 함수에서 자주 사용되는 람다 함수

array = [('홍길동', 50), ('이순신', 32), ('아무개', 74)]


def my_key(x):
    return x[1]


print(sorted(array, key=my_key))
print(sorted(array, key=lambda x: x[1]))

보통 정렬 함수의 경우에는 한번만 사용하고 다시 사용하는 경우가 없는 경우가 많다. 따라서 람다함수를 이용하도록  하자.

- 결과 화면

# 여러 개의 리스트에 적용

list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]

result = map(lambda a, b: a + b, list1, list2)

print(list(result))

list1와 list2에 lambda 함수가 적용되어 list1=a , list2=b의 변수에 매핑되어 연산이 이루어이게 된다.

따라서 서로 다른 리스트가 인덱스가 같은 원소끼리 더하기를 수행하게 되는 것이다.

※ map(각각의 변수에 적용할 함수, 변수명들)

- 결과 화면

기존 뼈대 (클래스)는 유지하되, 이후 필요한 형태로 꾸밀 때 사용한다. 확장이 필요한 경우 상속의 대안으로 활용 된다.

SOLID중에서 개방패쇄 원칙과 의존 역전 원칙을 따른다.

- 실습

package com.company.gof.decorator;

public interface ICar {
    int getPrice();
    void showPrice();
}

package com.company.gof.decorator;

public class Audi implements ICar{

    private int price;

    public Audi(int price){
        this.price = price;
    }
    @Override
    public int getPrice() {
        return price;
    }

    @Override
    public void showPrice() {
        System.out.println("audi의 가격: "+ this.price);
    }
}

package com.company.gof.decorator;

public class AudiDecorator implements ICar{

    protected ICar audi;
    protected String modelName;
    protected int modelPrice;

    public AudiDecorator(ICar audi, String modelName, int modelPrice){
        this.audi = audi;
        this.modelName = modelName;
        this.modelPrice = modelPrice;
    }

    @Override
    public int getPrice() {
        return audi.getPrice() + modelPrice;
    }

    @Override
    public void showPrice() {
        System.out.println(modelName+" 가격 : "+getPrice());
    }
}

package com.company.gof.decorator;

public class A3 extends AudiDecorator {

    public A3(ICar audi, String modelName) {
        super(audi, modelName, 1000);
    }
}

package com.company.gof.decorator;

public class A4 extends AudiDecorator {

    public A4(ICar audi, String modelName) {
        super(audi, modelName, 2000);
    }
}

package com.company.gof.decorator;

public class A5 extends AudiDecorator {

    public A5(ICar audi, String modelName) {
        super(audi, modelName, 3000);
    }
}

package com.company.gof;

import com.company.gof.decorator.*;


public class Main {

    public static void main(String[] args) {

        ICar audi = new Audi(1000);
        audi.showPrice();

        ICar audi3 = new A3(audi, "A3");
        audi3.showPrice();

        ICar audi4 = new A4(audi, "A4");
        audi4.showPrice();

        ICar audi5 = new A5(audi, "A5");
        audi5.showPrice();

    }

}

- 결과 화면

Proxy(프록시)는 대리인이라는 뜻처럼, 어떠한 껏을 대신하여 처리하는 것을 해준다.

Proxy Class를 통해서 대신 전달 하는 형태로 설계되며, 실제 Client는 Proxy로 부터 결과를 받는다.

Cache의 기능으로도 활용 가능

SOLID중에서 개방폐쇄 원칙과 의존 역전 원칙을 따른다.

-브라우저 예제

package com.company.gof.proxy;

public class Html {

    private String url;

    public Html(String url){
        this.url = url;
    }
}

package com.company.gof.proxy;

public interface IBrowser {
    Html show();
}

package com.company.gof.proxy;

public class Browser implements IBrowser{

    private String url;

    public Browser(String url){
        this.url = url;
    }

    @Override
    public Html show() {
        System.out.println("browser loading html from: "+url);
        return new Html(url);
    }
}

package com.company.gof;

import com.company.gof.proxy.Browser;

public class Main {

    public static void main(String[] args) {
        Browser browser = new Browser("www.naver.com");
        for(int i=0;i<9;i++)
            browser.show();
    }

}

- 결과 화면

❖매번 show() 함수를 실행할 때 마다 로딩을 해줘야 한다.

- Proxy 패턴을 이용한 캐시 기능 

package com.company.gof.proxy;

public class BrowserProxy implements IBrowser{

    private String url;
    private Html html;

    public BrowserProxy(String url){
        this.url = url;
    }

    @Override
    public Html show() {

        if(html == null){
            this.html = new Html(url);
            System.out.println("BrowserProxy loading html from: "+url);
        }
        System.out.println("BrowserProxy use cache html:"+url);
        return html;
    }
}

캐싱을 하기 위해 속성으로 html을 추가하고, html을 가지고 있지 않으면 로딩을 하고 가지고 있으면 그것을 리턴한다.

package com.company.gof;

import com.company.gof.proxy.Browser;
import com.company.gof.proxy.BrowserProxy;
import com.company.gof.proxy.IBrowser;

public class Main {

    public static void main(String[] args) {
//        Browser browser = new Browser("www.naver.com");
//        for(int i=0;i<9;i++)
//            browser.show();

        IBrowser browser = new BrowserProxy("www.naver.com");
        for(int i=0;i<5;i++)
            browser.show();
    }

}

-결과 화면

-AOP( Aspect Oriented Programming )기능

관심사의 분리라는 의미로 각각의 비즈니스 로직에서 부가 기능으로 생각되어지는 공통의 모듈들을 분리하여 관리하여 유지보수에 대한 용이성과 비즈니스 로직을 좀 더 이해하기 쉽게 해준다.

package com.company.gof.aop;

import com.company.gof.proxy.Html;
import com.company.gof.proxy.IBrowser;

public class AopBrowser implements IBrowser {

    private String url;
    private Html html;
    private Runnable before;
    private Runnable after;

    public  AopBrowser(String url, Runnable before, Runnable after){
        this.url = url;
        this.before = before;
        this.after = after;
    }
    @Override
    public Html show() {
        before.run();
        if(html==null){
            this.html = new Html(url);
            System.out.println("AopBrowser html loading from: "+url);
            try {
                Thread.sleep(1500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        after.run();
        System.out.println("AopBrowser html cache: "+url);
        return null;
    }
}

show 함수가 너무 빠를 수 있기 때문에 시간을 측정하기 위해 1.5초의 지연시간과 Runable before, after를 추가했다.

package com.company.gof;

import com.company.gof.aop.AopBrowser;
import com.company.gof.proxy.IBrowser;

import java.util.concurrent.atomic.AtomicLong;

public class Main {

    public static void main(String[] args) {

        //동시성 문제
        AtomicLong start = new AtomicLong();
        AtomicLong end = new AtomicLong();

        IBrowser aopBrowser = new AopBrowser("www.naver.com",
                ()->{
                    System.out.println("before");
                    start.set(System.currentTimeMillis());
                },
                ()->{
                    long now = System.currentTimeMillis();
                    end.set(now - start.get());
                }

        );
        aopBrowser.show();
        System.out.println("loading time : "+ end.get());

        aopBrowser.show();
        System.out.println("loading time : "+ end.get());

    }

}

-결과 화면

실제 우리 일상생활에서 쓰이는 어댑터와 유사하다. ex) 100v -> 220v

호환성이 없는 기존 클래스의 인터페이스를 변환하여 재사용함

SOLID중에서 개방패쇄 원칙을 따른다.

package com.company.gof.adapter;

public interface Electronic110V {
    public void powerON();
}

package com.company.gof.adapter;

public interface Electronic220V {
    public void connect();
}

package com.company.gof.adapter;

public class Hairdryer implements Electronic110V{
    @Override
    public void powerON() {
        System.out.println("Hair Dryer Power On By 110V");
    }
}

package com.company.gof.adapter;

public class Cleaner implements Electronic220V{
    @Override
    public void connect() {
        System.out.println("Cleaner On by 220V");
    }
}

package com.company.gof.adapter;

public class AirConditioner implements Electronic220V {

    @Override
    public void connect() {
        System.out.println("AirConditioner ON by 220V");
    }
}

package com.company.gof.adapter;

public class SocketAdapter implements Electronic110V{

    // 변환 대상
    private Electronic220V electronic220V;

    public SocketAdapter(Electronic220V electronic220V){
        this.electronic220V = electronic220V;
    }

    @Override
    public void powerON() {
        electronic220V.connect();
    }
}

package com.company.gof;

import com.company.gof.adapter.*;

public class Main {

    public static void main(String[] args) {
        Hairdryer hairdryer = new Hairdryer();
        connect(hairdryer);

        Cleaner cleaner = new Cleaner();
//        사용불가 콘센트가 맞지 않아서
//        connect(cleaner);

        Electronic110V adapter = new SocketAdapter(cleaner);
        connect(adapter);

        AirConditioner airConditioner = new AirConditioner();
        Electronic110V airAdapter = new SocketAdapter(airConditioner);
        connect(airAdapter);


    }

    // 콘센트
    public static void connect(Electronic110V electronic110V){
        electronic110V.powerON();
    }
}

-결과 화면

노드와 노드의 연결로 표현된 형태를 말하며 여기서 말하는 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체이다.

# 특징

• 트리는 부모 노드와 자식 노드의 관계로 정의된다
• 트리의 최상단 노드를 루트 노드라고 한다
• 트리의 최하단 노드를 단말 노드라고 한다
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합

-이진탐색트리

• 부모 노드보다 왼쪽 자식 노드가 작다
• 부모 노드보다 오른쪽 자식 노드가 크다
• 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 탐색 방법 : 부모 노드와 타켓 비교(더 작은 경우 왼쪽으로 이동, 더 클 경우 오른쪽으로 이동) -> 찾을 때까지 반복
• 방문 순서 ex)37 : 30 - 48 -37

3개지 변수 시작점, 중간점, 끝점을 이용하여 찾으려는 데이터와 중간점에 위치한 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 것

탐색 범위가 2000만을 넘어가면 이진 탐색을 떠올려보자 => log(n)의 시간 복잡도가 필요한 경우

# 재귀 함수를 통한 이진 탐색
def binary_search(array, target, start, end):
    # 탐색 결과 일치하는게 없는 경우
    if start > end:
        return None
    mid = (start + end) // 2
    # 중간 지점이 찾는 데이터와 일치하는 경우
    if array[mid] == target:
        return mid
    # 중간 지점의 데이터가 찾는 데이터보다 클 경우
    elif array[mid] > target:
        return binary_sort(array, target, start, mid - 1)
    # 중간 지점의 데이터가 찾는 데이터보다 작은 경우
    else:
        return binary_sort(array, target, mid + 1, end)


# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력하기
n, target = map(int, input().split())

# 전체 원소 입력받기
array = list(map(int, input().split()))

# 결과 출력
result = binary_search(array, target, 0, n - 1)

if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)

# 반복문을 이용한 이진 탐색
def binary_search(array, target, start, end):
    while start<=end:
        mid = (start + end) // 2
        # 찾은 경우 중간 지점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간 지점 데이터보다 찾는 데이터 값이 작은 경우
        elif array[mid] > target:
            end = mid -1

        # 중간 지점 데이터보다 찾는 데이터 보다 값이 큰 경우
        else:
            start = mid + 1

    return None

# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력하기
n, target = map(int, input().split())

# 전체 원소 입력받기
array = list(map(int, input().split()))

# 결과 출력
result = binary_search(array, target, 0, n - 1)

if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)