모영이의 블로그

2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 투포인터 : 정렬되어 있기 때문에 포인터 2개가 양쪽 끝에서 부터 만날때까지 조여오면된다. sum_waters에 넣고 마지막에 정렬하려했는데, min_water에 최솟값 1개만 저장하면되기 때문에 sort를 사용안했다. 전체코드 import sys input = sys.stdin.readline N = int(input()) waters = list(map(int, input().split())) # print(N, waters) sum_waters = [..

14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 위상정렬 : 다이나믹 프로그래밍도 사용해야 한다. 처음 진입차수 0을 큐에 넣을때, DP값을 1로 초기화 해준다. 이건 곧바로 이수할 수 있는 과목이기때문에 1을 넣는 것이다. DP[i]값 업데이트는 이전 노드의 DP값 + 1 또는 원래 DP[i]값 중 최댓값을 택하면 된다. 전체코드 import sys import collections input = sys.stdin.readline N, M = map(int, input().split()) inDegree = [0 for _ in ran..

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상정렬 : 위상정렬의 핵심은 그래프와 진입차수 같다. 여기 입력이 꼬여버리면 복잡해진다. 마지막에 주의할 점은 가수 순서를 못만들때를 고려해 주어야 한다. result의 길이로 판별을 했다. 전체코드 import sys import collections input = sys.stdin.readline N, M = map(int, input().split()) inDegree = [0 for _ in range(N + 1)] graph = c..

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬 마스터를 해야지 이런 느낌으로 위상정렬 문제만 풀고있다. 전체적으로는 비슷한 문제여서 백준 티어 경험치작을 하고싶다면 위상정렬 문제를 푸는게 어떨까 추천한다. 어차피 티어는 자기만족이니깐.. 위상정렬 : DP를 사용해서 작업시간을 업데이트 시켜준다. 주의할 점은 작업이 가장 오래걸린 것을 출력해야한다. 1로 출발해서 N으로 끝나는 작업이 예시로 들어왔지만, 그렇지 않은 경우도 있기 때문에 max값을 출력해주면 된다. 전체코드 import sys..

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬 : 위상정렬에 우선순위 큐를 사용해야 한다. 파이썬은 힙큐가 있기 때문에 너무 쉽다. 하지만 좀 막막할 수가 있다. 힙큐 쓰는 것을 솔직히 알고리즘 분류 클릭해보고 나서 알았다. 전체코드 import sys import heapq import collections input = sys.stdin.readline N, M = map(int, input().split()) inDegree = [0 for _ in range(N..

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 위상정렬 : 위상정렬 문제를 두번째 푸는 건데 느낌이 비슷한 것 같다. inDegree에 진입차수를 집어넣는게 핵심이다. 진입차수가 0이면 큐에 집어넣고 돌려준다. DP값에는 조건에 맞게 값을 넣어주면 된다. 전체코드 import sys import collections input = sys.stdin.readline N = int(input()) times = [0 for _ in range(N + 1)] dp = [0 for _ in range(N..

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 : 한번에 이해하기 어려웠다. 왜 i - 2인덱스에 접근해야 할까. 특정한 상황이 아니면 DP[i] = DP[i - 1] 이다. 하지만 뒤에 수를 가져다 붙여서 두자리 수 and 26이하의 수를 만들 수 있다면 DP[i - 2]를 추가해주어야 한다. i - 2에 접근하는 이유는 갖다 붙일 수 있는 상태의 수이기 때문이다. DP[3] (2, 5, 1), (25, 1) DP[4] (2, 5, 1, 1), (25, 1, 1), (2, 5, 11), (25, 11) ..

15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 : 중복되는 수열을 제외해야한다. 2 4 4가 있고 길이가 2이면 2 - 4(첫번째 4) 2 - 4(두번째 4)가 중복된다. 주어진 수를 제거하면 안되는게 2 4 4에서 중복되는 4를 제거하면 2 4가 되어 4 - 4 수열을 체크 못한다. 그래서 중복되는 값을 없애야하고 자연스럽게 in을 사용했지만, in은 시간복잡도가 list와 tuple일때 O(N)이지만 set, dict일때 O(1)이다. 그래서 set을 사용했다. 전체코드 import sys im..

1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 다익스트라 : 어떤 한 정점에서 가장 먼 곳의 정점은 가장 먼 두 정점 중 하나다. 문제의 핵심은 이것인데, 사실 잘 알기가 어렵다. 그래서 처음엔 DFS로 모든 경로의 거리값을 계산해 최댓값만 업데이트 시켰다. 이렇게 하면 시간초과와 메모리 초과가 발생하는데, 5까지 있다고 하면 1, 2, 3, 4, 5에서 출발하는 정점의 거리를 각각 찾아내기 때문에 이를 해결할 수 없다. 하지만, 처음 말했던 공식을 안다면, 어떤 한 정점이 무조건 포함됨을 알기에..

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 : 한번 간 곳은 다시 방문하지 않도록 설계 전체 코드 import sys input = sys.stdin.readline def bt(t:int, result:list, visited:list): if t == 0: print(*result) return for i in range(len(nums)): if i not in visited: bt(t-1, result + [nums[i]], visited + [i]) N, M = map(int, ..