백준

[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] 백준 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번 노드에서 ..

[python3] 백준 1339 풀이 ( 단어 수학, 그리디 )

이 문제는 상당히 헤맸다. 결국 1시간내에 풀지 못해서 질문을 찾다보니 좋은 접근 방법이 있어서 그걸 토대로 푸니 금방 풀렸다. 길이가 최대 8인 문자열이 최대 10개가 주어진다. 각 알파벳은 숫자를 의미하는데 숫자를 대입하여 모든 문자열의 총합을 구하면 된다. 예를 들어 AB + A의 최대값은 98+9 = 117로 나타낼 수 있다. 그럼 간단한 규칙을 찾아낼 수 있다. 1. 가장 앞에 있는 문자열일수록 큰수를 대입해야한다. 2. 많이 나올수록 큰수를 대입해야한다. 그런데 이렇게 정리하면 삽질을 하게 된다. 한마디로 짧게 생각하면 스스로 함정에 빠지는 거다. 그냥 간단하게 AB -> A*10+B*1, B-> B*1 AB+B -> A*10 + B*2 가 된다. 따라서 이걸 그대로 해주면 어떤 값이 가장 크..

[python3] 백준 4195 (친구 네트워크, 유니온 파인드)

문제는 아주 심플하다. 소셜네트워크를 구성할때 서로 친구가 될때마다 해당 네트워크에 몇명이 속하는지 알아내면 된다. 테스트 케이스의 범위는 주어지지 않았지만 F의 값이 100,000으로 주어졌다. 그럼 테스트 케이스 * 100,000으로 상당히 연산량이 클것으로 예상된다. 또한 DFS를 통해 구성된 네트워크의 노드 갯수를 센다고 가정한다면 100,000 * O(N) 정도의 시간 복잡도가 걸리는데 만약 N이 100,000이 된다면 너무 시간복잡도가 크다. 즉, 매번 탐색하는 방식으로는 구할 수가 없다. 그럼 A라는 친구가 어디 네트워크에 속하고, 네트워크의 크기는 어느정도인지 한번에 안다면 우리는 testcase*100,000의 연산만으로 정답을 구할 수 있다. 딱 냄새가 난다 네트워크에 속하고 머시기 어..

[python3] 백준 1005 풀이 ( ACM Craft, 위상정렬, 다이나믹 프로그래밍, DP )

상당히 헤맸던 문제다. 갈피를 못 잡다가 문제의 알고리즘 분류를 힌트로 보고 방향성을 잡을 수 있었다. 그럼 문제를 보자 문제를 읽어보면 건물의 순서가 주어진다. 이때 목표하는 건물을 만들기까지 걸리는 최소 시간을 출력한다. 보면 건물의 순서가 그래프로 주어지기 때문에 사이클이 존재하지 않는다. 즉, DAG그래프처럼 보인다. 그럼 당연히 자연스럽게도 위상정렬이 떠오른다. 그럼 생각을 해본다. 위상정렬은 BFS처럼 동작한다. 큐에서 노드를 뽑고, 노드의 out degree접선을 제거하면서 진행한다. 그리고 만약 한 노드의 in degree접선이 0이라면 큐에 넣는다. 위상정렬의 원리는 아래의 글을 읽으면 된다. [python3] 백준 2252 풀이 ( 줄세우기, 위상정렬, DAG, 그래프 ) 위상정렬 어떤..

[python3] 백준 1238 풀이 ( 파티, 다익스트라 )

이번 문제는 참신했다. 물론 내가 생각도 못해서 참신하게 느껴진거 겠지만ㅋㅋ 우선 문제를 보자 문제를 읽어보면 여러 곳에서 학생들이 X마을로 모인다. 이후에 각자 집으로 돌아갈 때 가장 오래 걸리는 학생의 소요 시간을 출력한다. 간단히 생각해보면 파티에 참석하는 경우 마을이 N개 이기 때문에 N -> X로 가는 경우의 수가 나올것이다. 파티가 끝나고 집에 가는 경우는 X -> N으로 가는 경우의 수가 나온다. 그럼 단순하게 보면 단일 시작점 알고리즘이 적용되면 안 되는거 같다. 왜냐하면 출발할 때 N개의 마을에서 각자 출발하기 때문이다. 그래서 나도 플로이드-워샬을 적용하고 풀고자 했다. N=1000 이므로 N^3 = 1,000,000,000 = 10억, 21억 넘지 않아서 괜찮을 줄 알았다. (찾아보니..