https://www.acmicpc.net/problem/2573
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지
www.acmicpc.net
간단한 DFS 문제, 배열 갱신 타이밍만 잘 잡으면 됨.
https://www.acmicpc.net/problem/1806
1806번: 부분합
문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길
www.acmicpc.net
투 포인터 문제, 투 포인터가 내 약점 중에 하나라, 조금 두렵긴 했는데, 그냥 쉬웠음.
한쪽은 시작점, 한쪽은 끝점해서, 최대한 합이 S에 가깝게 유지해가면서 두개 포인터 옮겨가면 됨.
https://www.acmicpc.net/problem/2056
2056번: 작업
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하는) 작업들의 번호는 모두 1 이상 (K-1) 이하이다. 작업들
www.acmicpc.net
1005번 문제인 ACM carft 문제를 풀었으면, 바로 풀 수 있음. 사실상 BFS + DP 문제
https://www.acmicpc.net/problem/11049
11049번: 행렬 곱셈 순서
첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같�
www.acmicpc.net
매우 매우 매우 많이 유명한 DP 문제, 2차원으로 DP 배열 잡고 그냥 하면 됨
https://www.acmicpc.net/problem/9252
9252번: LCS 2
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
www.acmicpc.net
LCS 구하면 되는데, O(n^2)으로도 해결됨.
그래서, O(n^2)으로 LCS DP 배열 갱신하면서, 어떻게 갱신했는지 경로 저장해놓고 나중에 따라가면 됨.
https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼��
www.acmicpc.net
간단한 BFS 문제임.
근데, 계속 틀림, 이유는 0때문이었음. 0도 고장날 수 있는 버튼이라는 것과 0의 자리수는 1이라는 거를 고려안했었음. 이제부터 기억하자. 0은 한 자릿수의 숫자이다.
Rmx
'내가 공부하려고 만들어가는 목록' 카테고리의 다른 글
| [내공만목] BOJ 행렬 곱셈 순서 시리즈를 풀고 싶었다.(WIP) (0) | 2020.10.30 |
|---|---|
| [내공만목] BOJ 트리와 쿼리 시리즈를 풀고 싶었다.(WIP) (0) | 2020.10.26 |
| [내공만목] 어쩌다가 knapsack 문제들을 풀게 되었다. (0) | 2020.05.03 |
| [내공만목] Convex Hull 공부하기 (0) | 2020.05.01 |
| [내공만목] erdos-ginzburg-ziv theorem && Zero sum problem (0) | 2020.04.11 |