https://www.acmicpc.net/problem/12865

Knapsack 문제라고도 불리는 배낭문제다.

알고리즘을 처음 공부할 때 도대체 어떻게 푸는건지 3시간을 고민해도 못풀었던 문제인데

DP를 이용한 풀이를 공부한 뒤로 풀 수 있게 됐다.

예전에 비슷한 문제를 풀어본적이 있는데, 복습겸 한 번 더 풀어봤다.

지금 생각해도 DP는 경이롭다.. 

DP로 푼 코드(정답)

import sys
input = sys.stdin.readline

N, K = map(int, input().split(" "))
DP = [[0 for i in range(K+1)] for i in range(N+1)]
graph = [[0, 0] for i in range(N+1)]
for i in range(1, N+1):
    graph[i][0], graph[i][1] = map(int, input().split(" "))

# N은 100까지, K는 100,000까지, 총 10,000,000(1초) 필요
for n in range(1, N+1):
    for k in range(1, K+1):
        weight, value = graph[n][0], graph[n][1]
        # 탐색하려는 무게에 못미친경우 이전 무게를 그대로 가져옴
        if k < weight:
            DP[n][k] = DP[n-1][k]
        # 무게 범위 내일 경우
        else:
            # 현재 무게랑 현재 무게만큼 뺐을 때의 이전 값을 더한것과, 이전 값과 비교해서 큰거로 누적
            DP[n][k] = max(DP[n-1][k-weight]+value, DP[n-1][k])

print(DP[N][K])

백트랙킹으로 풀었다가 시간초과난 코드(오답)

# import sys
# input = sys.stdin.readline

# N, K = map(int, input().split(" "))
# graph = [[0, 0] for i in range(N)]
# for i in range(N):
#     graph[i][0], graph[i][1] = map(int, input().split(" "))

# answer = 0
# idx = 0


# def getMaxVal(idx, accw, accv):
#     if accw > K:
#         return

#     global answer
#     if idx == N:
#         answer = accv if answer < accv else answer
#         return

#     w, v = graph[idx][0], graph[idx][1]

#     getMaxVal(idx+1, accw+w, accv+v)
#     getMaxVal(idx+1, accw, accv)


# for i in range(N):
#     getMaxVal(i, 0, 0)  # idx, accweight, accval
# print(answer)

# 백트랙킹 했다가 시간초과 남.

결과

디자인 패턴 - 컴포지트 패턴 (Composite Pattern)

• Composite 란 영어사전상 "복합체" 라는 뜻.
• 소프트웨어적으로는 하나 이상의 유사한 객체를 구성으로 설계된 객체로서, 모두 유사한 기능을 나타내는 것을 뜻한다.
• 즉, 객체 그룹을 조작하는 것처럼 단일 객체를 조작할 수 있음.

• 컴포지트 패턴은 클라이언트가 복합 객체나 단일 객체를 동일하게 취급하는 것을 목적으로 함.
• 이 때, 컴포지트의 의도는 "트리 구조"로 작성하여, 전체-부분(whole-part) 관계를 표현하는 것이다.
• 즉, 전체-부분 관계를 효율적으로 정의할 때 컴포지트 패턴은 유용하다.

• Composite 패턴에는 3가지로 구조가 나뉘어져있다.
  1. Component
     • 구체적인 부분
     • Leaf 클래스와 Composite 클래스의 공통 인터페이스임
  2. Leaf
     • 구체적인 부분 클래스
     • Composite 객체의 부품
  3. Composite
     • 전체 클래스.
     • 여러개의 Component를 갖도록 정의한다.
     • 그래서 여러개의 Leaf, 여러개의 Composite를 부분으로 가질수도 있다.

예시

• 강아지와 고양이는 동물이다.
• 강아지그룹, 고양이그룹에 각각 2마리, 3마리 넣는다.
• 두 그룹을 동물원에 넣는다.
• 동물원 내의 동물들을 모두 speak 하게 만들면?

Component: IAnimal.java

// Component 역할
interface IAnimal {
    public void speak();
}

Leaf: Cat.java

public class Cat implements IAnimal{
    @Override
    public void speak() {
        System.out.println("야옹");
    }
}

Leaf: Dog.java

public class Dog implements IAnimal{
    @Override
    public void speak() {
        System.out.println("멍멍");
    }
}

Composite: AnimalGroup.java

// Composite 역할
public class AnimalGroup implements IAnimal {

    private List<IAnimal> animalGroup = new ArrayList<IAnimal>();

    public void speak() {
        for (IAnimal animal : animalGroup) {
            animal.speak();
        }
    }

    public void add(IAnimal animal) {
        animalGroup.add(animal);
    }

    public void remove(IAnimal animal) {
        animalGroup.remove(animal);
    }
}

Client: Main.java

public class Main {
    public static void main(String[] args) {

        // 강아지그룹, 고양이그룹 생성
        AnimalGroup dog_group = new AnimalGroup();
        AnimalGroup cat_group = new AnimalGroup();

        // 강아지 2마리, 고양이 3마리 만들어서 각 그룹에 넣기
        Dog dog1 = new Dog();
        Dog dog2 = new Dog();

        Cat cat1 = new Cat();
        Cat cat2 = new Cat();
        Cat cat3 = new Cat();

        dog_group.add(dog1);
        dog_group.add(dog2);

        cat_group.add(cat1);
        cat_group.add(cat2);
        cat_group.add(cat3);

        // 강아지그룹과 고양이그룹을 동물원이라는 그룹안에 넣겠음
        AnimalGroup zoo = new AnimalGroup();
        zoo.add(dog_group);
        zoo.add(cat_group);

        // 동물원의 모든 동물들을 speak 해보겠음
        zoo.speak();
    }
}

결과는 다음과 같이 나온다.

멍멍
멍멍
야옹
야옹
야옹

• 출처 : https://www.youtube.com/watch?v=XXvrHAsfTso
• 출처 : https://mygumi.tistory.com/343
• 출처 : https://gmlwjd9405.github.io/2018/08/10/composite-pattern.html

https://www.acmicpc.net/problem/23286

거쳐가는 노드의 최소값 구하는거라 다익스트라 쓰는 줄 알았는데
T가 40000번 돌아야해서 매번 최소거리를 구하는게 비효율적임을 너무 늦게 깨우쳤다.

(어딘가에서 무한루프가 도는건가? 싶어서 계속 val값을 깨작깨작 수정하고있었다.)

한 번에 모든 노드->노드 로 가는 최소거리를 구해서

단순히 2차원 배열에서 결과값만 던져주면 되는 플로이드-워셜 알고리즘이 정답이었다.

정답코드

import sys
input = sys.stdin.readline
N, M, T = map(int, input().split(" "))
INF = sys.maxsize
graph = [[INF for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    a, b, val = map(int, input().split(" "))
    graph[a][b] = val
for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            bigger = graph[i][k] if graph[i][k] > graph[k][j] else graph[k][j]
            graph[i][j] = bigger if graph[i][j] > bigger else graph[i][j]

for tc in range(T):
    a, b = map(int, input().split(" "))
    if graph[a][b] != INF:
        print(graph[a][b])
    else:
        print(-1)

틀린코드(다익스트라 써서 시간초과 난 코드)

import heapq
input = sys.stdin.readline
N, M, T = map(int, input().split(" "))
graph = [[] for i in range(N+1)]
for i in range(M):
    a, b, val = map(int, input().split(" "))
    graph[a].append((b, val))
INF = sys.maxsize
for tc in range(T):
    start, end = map(int, input().split(" "))
    distance = [INF for i in range(N+1)]
    heap = []
    heapq.heappush(heap, start)
    distance[start] = 0
    while heap:
        fr = heapq.heappop(heap)
        for g in graph[fr]:
            to, toval = g[0], g[1]
            biggerVal = distance[fr] if distance[fr] > toval else toval
            if distance[to] > biggerVal:
                distance[to] = biggerVal
                heapq.heappush(heap, to)
    print(distance[end] if distance[end] != INF else -1)

https://www.acmicpc.net/problem/14284

문제를 딱 읽어보니 최소 루트를 구하는 다익스트라 문제같았다.

그래서 다익스트라를 사용해서 풀었더니 통과됐다.

import sys
import heapq
input = sys.stdin.readline

N, M = map(int, input().split(" "))
graph = [[] for i in range(N+1)]
INF = sys.maxsize
distance = [INF for i in range(N+1)]
for i in range(M):
    a, b, val = map(int, input().split(" "))
    graph[a].append((b, val))
    graph[b].append((a, val))
finalA, finalB = map(int, input().split(" "))
distance[finalA] = 0

heap = []
for i in graph[finalA]:
    to, val = i[0], i[1]
    heapq.heappush(heap, (to, val))
    distance[to] = val

while heap:
    fr, val = heapq.heappop(heap)
    for j in graph[fr]:
        to, toval = j[0], j[1]
        newVal = val + toval
        if distance[to] > newVal:
            distance[to] = newVal
            heapq.heappush(heap, (to, newVal))

print(distance[finalB])

# 다익스트라

while문을 for문 안에 넣었더니 한 번 틀렸다.

굳이 안넣어도 되기때문에 for문 바깥으로 뺐더니 통과됐다.

https://www.acmicpc.net/problem/13023

그래프 복습.

이번 문제는 DFS를 이용하는 문제였다.

연결된 노드를 따라 건너면서 step이 4 이상이 되면 조건에 맞는다고 판단한다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split(" "))
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split(" "))
    graph[a].append(b)
    graph[b].append(a)

for i in range(N):
    graph[i].sort()

isEnd = False


def DFS(v, step, visited):
    # print("v = {}, step = {}, visited = {}".format(v, step, visited))
    global isEnd
    if isEnd == True:
        return
    if step >= 4:
        isEnd = True
        return

    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True
            DFS(i, step+1, visited)
            visited[i] = False


for i in range(N):
    visited = [False for i in range(N)]
    visited[i] = True
    DFS(i, 0, visited)
    visited[i] = False
    if isEnd == True:
        break

print(0 if isEnd == False else 1)

백트랙킹이면 DFS함수 나올 때 visited[i] = False 해줘야하는데, 그거 까먹어서 1번 틀렸다,.

디자인 패턴 - 프록시 패턴 (Proxy Pattern)

• Proxy는 우리말로 대리자, 대변인이라는 뜻이다.
• Proxy는 흐름제어만 할 뿐, 결과값을 조작하거나, 변경시키면 안된다.

• Proxy는 실제 서비스와 같은 이름의 메서드를 구현한다. 이 때 인터페이스를 사용한다.
• Proxy는 실제 서비스에 대한 참조 변수를 갖는다.
• Proxy는 실제 서비스의 같은 이름을 가진 메서드를 호출하고, 그 값을 클라이언트에 돌려준다.
• Proxy는 실제 서비스의 메서드 호출 전후에도 별도의 로직을 수행할 수 있다.

예시

IService.java

public interface IService {
    String runSystem();
}

Service.java

public class Service implements IService {
    @Override
    public String runSystem() {
        return "시스템을 실행합니다."
    }
}

Proxy.java

public class Proxy implements IService {
    IService service1;

    @Override
    public String runSystem() {
        System.out.println("대신실행 하겠습니다.")
        service1 = new Service();
        return service1.runSystem();
    }
}

Main.java

public class Main {
    public static void main(String[] args) {
        IService proxy = new Proxy();
        System.out.println(proxy.runSystem());
    }
}

• 인터페이스를 두어서 구체 클래스에 영향을 받지 않게 하였음.
• Proxy를 통해 우회하여 접근하였다.
  • OCP, DIP 원칙이 녹아져있음을 알 수 있다.

Main.java 실행결과

• 출처: https://limkydev.tistory.com/79

ㅇhttps://www.acmicpc.net/problem/5430

뭔가 딱봐도 deque를 써야할 것 같은 문제였다.

배열의 pop(0) 보다 deque의 popleft가 더 빠르기 때문이다.

처음에 빈 배열이 들어올 때, 그걸 아무것도 들어있지 않은 배열로 입력받아야 하는데

string형태로 받으면 얘가 [''] 이런 형태로 입력해버린다.

그래서 처음에 입력받을때 int형으로 받았다가, 마지막에 str형으로 변환해준다.

꽤 비효율적인 방법인 것 같으나 어쨌든 통과는했다.

import sys
from collections import deque
input = sys.stdin.readline

TC = int(input())
for tc in range(TC):
    isReversed = False
    isError = False
    text = input().rstrip()
    n = int(input())
    try:
        nlist = list(map(int, (input().rstrip()[1:-1].split(","))))
    except:
        nlist = []
    queue = deque()
    for i in nlist:
        queue.append(i)

    for order in text:
        if order == "R":
            isReversed = not isReversed
        elif order == "D":
            if len(queue) == 0:
                isError = True
                break
            else:
                if isReversed == False:
                    queue.popleft()
                else:
                    queue.pop()

    result = list(map(str, queue))
    if isError == True:
        print("error")
    else:
        if isReversed == False:
            print("[" + ",".join(result) + "]")
        else:
            print("[" + ",".join(result[::-1]) + "]")

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=python3 

LRU가 뭔지 일단 알아야 하는 문제. 알고나면 쉽다.

배열의 pop(0) 이 아주 시간복잡도를 올리는 녀석으로 알고있는데,

배열의 index 찾아주는 기능을 사용해야 했기 때문에 deque 같은 다른 자료구조 말고 배열을 사용했다.

def solution(cacheSize, cities):
    answer = 0
    cachebox = []

    if cacheSize == 0:
        answer = 5 * len(cities)
        return answer

    for city in cities:
        ref = city.lower()
        if ref in cachebox:
            answer += 1
            cachebox.append(cachebox.pop(cachebox.index(ref)))
        else:
            answer += 5
            if len(cachebox) != cacheSize:
                cachebox.append(ref)
            else:
                cachebox.pop(0)
                cachebox.append(ref)

    return answer

# LRU (Least Recently Used) 알고리즘을 활용하는 문제
# 반례가 있었는데 못찾아서 1시간동안 헤맸다.