알고리즘

[python3] 백준 1099 (알 수 없는 문장, DP)

접근 단어를 조합해서 비용을 최소로 만들어야 하는데 문제는 매번 다른 단어를 어떻게 조합할지가 문제다. 예를 들어 neotowheret 라는 단어가 존재할때 ne를 선택하면(문제에는 없지만 가능하다 가정하면) 비용이 0이지만, one을 선택한다면 비용이 3이다. 따라서 ne를 선택하는게 합리적으로 보이지만 ne이 이후에 가능한 단어의 조합이 없기 때문에 ne가 아닌 one을 선택해야한다. 즉, 어떤 단어를 선택해서 조합할지 + 단어를 선택하는 경우 최소비용을 적용하는등의 다양한 조합이 필요하다. 처음에는 각 단어가 가질 수 있는 모든 조합을 만들어서 대입하여 풀까도 생각했다. 예를들어 one이라면 noe,eno,oen,eon,neo 등등 모든 케이스를 뽑아서 적용하는 것이다. 그러나 50개의 단어에 대해..

[python3] 백준 7579 (앱 , DP)

우선 A,B,C,D,E 프로세스가 존재할때 메모리크기와 코스트가 존재하기 때문에 언제 최소한의 코스트를 사용하며 60이상의 메모리가 확보되는지 확인하기 위해서는 모든 경우의 수를 확인해야한다. A 활성화 비활성화 B 활성화 비활성화 C 활성화 비활성화 D 활성화 비활성화 E 활성화 비활성화 그럼 결과적으로 2**5의 경우의 수가 존재한다. 그런데 N값이 100이므로 2**100의 경우가 존재하는데 이걸 전부 확인하는 것은 말이 안된다. 따라서 백트래킹이나, DP 처럼 쳐낼수 있는 경우를 쳐내는 방식으로 진행해야한다. 그런데 이 문제는 냅색문제처럼 무게와 가중치가 존재하는 문제이다. 따라서 냅색의 알고리즘을 활용하면 되겠다는 생각이 들었다. 냅색의 경우는 무게 제한이 있었기 때문에 dp[i][w]로 2차원..

[python3] 백준 1039 (교환, BFS)

N값으로 값이 주어지는 경우 i 번째와 j 번째를 바꾸어 새로운 수를 만든다. 이때 K번 연산을 하여 나올 수 있는 최댓값을 구하면 된다. N값은 1,000,000으로 값이 커보이지만 문자열 연산을 하기 때문에 긴 값은 아니다. K값 또한 10으로 시간 복잡도상으로 큰 값이 아니다. 만약 2133이 존재할때 i=0, j=2로 하는 경우 3123이 된다. i=0,j=3로 하는 경우 3132이 된다. 그렇다면 2133을 1번 변환하여 만들수 있는 최댓값은 3132이다. 그러나 2133을 2번 변환하여 만들수 있는 값이 3321인데 3132로는 3321을 만들수 없다. 즉 K-1번의 결과값이 K번의 결과 값과는 상관이 없다. 따라서 모든 경우의 수를 탐색해야 K번 연산 했을때의 최댓값을 구할 수 있다. 그렇다..

[python3] 백준 11000 (강의실 배정, 최소힙, 그리디)

1~3시, 2~4시, 3~5시의 강의가 존재할때 최소 몇개의 강의실이 필요한지 구해야한다. 보통 강의실 문제는 그리디로 하나의 강의실이 존재할때 몇개의 수업이 가능한지는 물어보는 문제가 많았던거 같은데 이번에는 강의가 존재할때 몇개의 강의실이 필요한지 구해야한다. 처음에는 갈피를 못잡았다. 그리디 같은 느낌이 들어서 정렬을 해보고 구하려고 했는데 잘 구해지지 않았다. 그래서 알고리즘 분류를 보니 예상도 못한 우선순위 큐가 존재했다. 우선순위 큐를 사용해야한다는 힌트를 보자 바로 풀이가 떠올랐다. 우선 우선순위 큐에 들어가야하는것은 강의실이 될 수 있다. 즉, 해당 강의실을 몇시부터 몇시까지 쓰는 큐가 된다. 처음에는 1-3시에 강의실을 사용할 것이기 때문에 큐에 A(1-3)으로 넣는다. 2-4강의는 A(..

[python3] 백준 1991 (트리 순회, 트리, 재귀)

이번 문제는 순회 문제이다. 처음에는 트리를 어떻게 푸는지 몰라서 헤맸는데 어제 영상을 봤더니 쉽게 이해가 갔다. https://www.youtube.com/watch?v=QN1rZYX6QaA 정리하자면 pre order = root, left, right 순서 in order = left, root, right 순서 post order = left, right, root 순서 따라서 순서만 기억해도 나중에 쉽게 떠올릴 수 있다. 이걸 토대로 문제를 풀면 아래와 같다. adj = {} N = int(input()) for i in range(N): A, B, C = input().split() if A not in adj: adj[A] = [B, C] # 전위 순회 [root, left, right] d..

[python3] 1167 풀이 (트리의 지름, 트리, DFS)

문제가 어려워서 힌트를 봤고 이해하고 나니 쉽게 풀 수 있었다. 트리가 주어진다. 이때 트리의 지름을 구하는 문제이다. 트리의 지름을 어떻게 구해야하는지 이해하지 못하면 풀수가 없다. 트리가 주어졌을대 트리의 지름을 구하기 위해서는 가장 끝점을 알아내야한다. 처음에는 각 노드마다 다익스트라를 할지 플로이드를 할지 고민했다. 그런데 주어지는 노드가 100,000개이기 때문에 구할 수가 없다. 따라서 다른 방법을 사용해야한다. 그래서 이리저리 지지고 볶으니 한줄로 세우는 방법이면 되지 않을까 싶었다. 그래서 한줄로 세워보았다. 그런데 이렇게 세운다고 달라지지가 않았다. 더이상 고민하는게 무의미하여 찾아보니 아무 노드나 잡고 가장 먼것을 찾아본다. 그럼 지름의 끝 노드를 찾을 수 있었다. 만약 3번 노드에서 ..

[python] 조합을 DFS로 구하기

항상 combinations로만 조합을 구했는데 이제는 한번 정리를 해야할것 같아서 오랜만에 글을 쓴다. 이문제는 백준 15650번으로 조합을 구하면 되는 문제이다. 사실 라이브러리를 사용한다면 상당히 쉬운 문제이다. from itertools import combinations N, M = map(int, input().split()) for com in list(combinations([i for i in range(1, N+1)], M)): print(" ".join(map(str, com))) 그러나 이렇게 푸는게 습관이 되어 나중에 백트래킹 문제가 어렵게 느껴졌고 기초적인 문제를 코테에서 틀리는 상황이 발생했다. 따라서 이걸 DFS로 풀어보자. 4에서 3개를 뽑는 경우는 [1,2,3],[1,2,..

[python3] Trie 구현

트라이는 문자열 탐색에 굉장히 유리한 알고리즘이다. 각 문자열에 대해서 트라이 형태로 자료구조를 만들면 이후에 문자열이 존재하는지 파악할때 빠르게 파악가능하다. class Node(object): def __init__(self, key, data=None): self.key = key self.data = data self.children = {} class Trie(object): def __init__(self): self.head = Node(None) def insert(self, string): # 문자열이 삽입한다. 단순 삽입 curNode = self.head for char in string: if char not in curNode.children: curNode.children[cha..