https://www.acmicpc.net/problem/7579 ✅ 문제 설명M바이트의 메모리가 필요하다. 활성화되어있는 앱 A1~AN중에서 몇개를 비활성화해서 M 이상의 메모리를 추가 확보하자. 이 때 비활성화했을 때의 비용의 최소화하여 M이상의 바이트를 확보하자!✅ 접근 방식처음에 DP문제인 0-1 knapsack인 것까진 파악을 했다.근데 왜 못 풀었지..?음.. 나는 너무 메모리에 대해서만 집중하고 가격에 대해서 for문을 돌 생각을 못했던 것 같다.knapsack[i][j]는 i번째 앱까지 고려했을 때, j비용으로 얻을 수 있는 최대 메모리 값이다.가로축을 비용, 세로축을 선택지으로 두고, 표의 안쪽을 얻을 수 있는 가치로 기록한다고 생각하면 된다. ✅ 코드 설명import sysn, m = ..
알고리즘/백준
https://www.acmicpc.net/problem/11000 ✅ 문제 설명Si에 시작해서 Ti에 끝나는 N개의 수업이 주어질 때, 최소의 강의실을 사용해서 모든 수업이 가능하게 하자!수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다. 즉 3초에 끝난 수업이 있다면 같은 강의실에서 다른 수업을 3초에 시작할 수 있다는 것이다.)✅ 접근 방식나는 우선순위 큐에 (시간, 타입)으로 튜플을 넣어줬다.31 32 43 5 이런식으로 들어온다면(1, "S")(3, "E")(2, "S")(4, "E")(3, "S")(5, "E") 그래서 우선 순위큐를 돌면서 pop하면서 S이면 강의실을 하나 늘렸고, E면 강의실을 하나 줄였다.근데 이때, ..
https://www.acmicpc.net/problem/2015 ✅ 문제 설명수열이 주어졌을 때, 부분합이 K인 것이 몇개나 있는 지 구하는 문제다.✅ 접근 방식처음에는 인덱스 0부터 N-1까지 돌면서 해당 인덱스부터 시작하는 배열의 부분합을 구해, K가 나오는 수를 계산하려고 했다.-> 근데 이 방법은 1 ≤ N ≤ 200,000이므로, O(N^2)이 소요되면 40,000,000,000(4백억..) 절대 2초만에 들어올 수 없을 것이다. 그래서 나도 사실 답을 보고 왔다!알고리즘 분류에 해시, 트리를 사용한 집합과 맵이라 되어있어 이게 뭘까..? 딕셔너리를 사용하는 걸까 싶었는데,역시 딕셔너리를 사용하더라! 똑똑해.. ✅ 코드 설명dict = {0: 1} # 누적합을 기록해둘 딕셔너리우선 인덱스 0부..
17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net ✅ 문제 설명 1번 정점(루트)에 W만큼의 물이 고여있고, 다른 정점들에는 물이 고여있지 않은 상태입니다. 이때 모든 정점은 아래의 작업을 매초 마다 반복합니다. 물을 가지고 있으며, 자식 정점이 있다면 자식 정점 중 하나를 골라 물을 1 준다. 자식 정점이 여러 개라면 동일한 확률로 그 중 하나를 고른다. 만약 부모 정점이 자신에게 물을 흘려보냈다면 받아서 쌓아 둔다. 위 작업이 다 끝나서 더 이상 물이 움직이지 않을 때..
2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net ✅ 문제 설명 BOJ_4256 문제와 비슷한 문제입니다. (https://wnszero.tistory.com/10) 이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더를(전위순회) 구하는 문제입니다. ✅ 접근 방식 중위순회, 후위순회 2개의 결과를 종합하여 각각의 결과에서의 루트와 왼쪽서브트리, 오른쪽 서브트리를 알아내고, 이를 이용해서 (루트)(왼쪽 서브트리)(오른쪽 서브트리)순으로 탐방순서를 배치해 전위순회를 시행하면 원하는 결과를 얻을 수 있습니다. ✅ 코..
4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net ✅ 문제 설명 이진 트리의 전위순회, 중위순회 결과가 주어졌을 때, 후위 순회의 결과를 유추하는 문제입니다. 이때, 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어집니다. ✅ 접근 방식 저번 포스팅이었던 이진 검색 트리에서 썼던 로직과 같은 로직을 이용했습니다. (참고) [BOJ_5639] 이진 검색 트리 (python) 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작..
1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net ✅ 문제 설명 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 트리의 지름이라고 정의할 때, 트리의 지름을 구하는 문제입니다. ✅ 접근 방식 트리의 지름을 구하는 방법은 다음과 같습니다. 1) 시작노드(=아무노드나 가능)에서 가장 먼 노드 A를 구합니다. 2) 노드 A를 기준으로 가장 먼 노드B를 구하면 그 두 노드(A,B) 사이의 거리가 트리의 지름이 됩니다. 이게 왜 가능할까요? 어떤 노드에서 가장 먼 노드를 구하면(1번) 그 노..
14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net ✅ 문제 설명 트리에서 단절점(cut vertex)과 단절선(bridge)을 구하는 문제입니다. 단절점, 단절선? 단절점: 하나의 컴포넌트(connected componenet)로 이루어진 그래프에서 한 정점을 제거했을 때, 컴포넌트의 개수가 증가하는 정점을 단절점이라고 한다. 단절선: 하나의 컴포넌트(connected componenet)로 이루어진 그래프에서 한 간선을 제거했을 때, 컴포넌트의 개수가 증가하는 간선을 단절선이라고 한다..
