전체 글
-
#798 div2 6/27 virtual대회/코드포스 2022. 6. 27. 16:57
https://codeforces.com/contest/1689 Dashboard - Codeforces Round #798 (Div. 2) - Codeforces codeforces.com 매일 아침 코포 버츄얼 돌린 첫날. 머리도 깰겸 A a string, b string 에서 하나하나 뽑아서 사전순으로 가장 앞선 string c를 만드려고 한다. a,b 둘 중 하나가 빌때까지 반복하고, 연달아서 a,b에서 뽑는 것은 k번까지 제한이 있다. a, b 둘다 정렬하고 a, b index 앞부터 끝날때까지 반복한다. a index, b index 중 더 빠른 거 두고, 연달아 k번 썼는지 확인한다 단순 구현문제인데 생각이 또 둥둥 떠다닌다. 잡아서 써보자 B 순열에서 원래 순서랑 모두 다 다르게, 사전순 ..
-
백준 20932 약수 의식전공/알고리즘 2022. 4. 6. 12:46
https://www.acmicpc.net/problem/20932 20932번: 약수 의식 홍익대학교 바로 뒤편에 위치한 와우산의 와우약수터는 아직도 폐쇄되어있다. 와우산의 정기가 그대로 흘러나오는 약수를 다시 회복하기 위한 "와우 프로젝트"의 일원으로 파견된 당신은, 와우 www.acmicpc.net 1,2,3,4의 카드가 있다고 해보자 1,2,3의 카드로 만들 수 있는 수는 123 132 213 231 312 321 이렇게 6가지이다. 이 다음에 4카드를 뽑았다고 하면 1234 1324 2134 2314 3124 3214 이렇게 된다. 따라서 우리는 4를 마지막으로 뽑았을때의 모든 경우에 대해서 가지고 있어야 마지막으로 4가 나왔을때의 나머지가 0인지 아닌지 확인할 수 있다. 우리가 나머지를 구하는..
-
2022 구글 코드잼 Qualification Round 후기전공/알고리즘 2022. 4. 3. 16:08
A,B,C는 쉬운 난이도의 구현, 그리디 문제였는데 내가 아직 for문에 대한 이해도가 낮구나를 깨달았다. A구현이 한번에 되지 않고, 시행착오를 겪으면서 구현하였다. B에서도 마찬가지 D가 재밌던 문제라고 느껴졌다. 처음에 bfs로 리프부터 탐색을 할까 거리를 구하는 문제인가 생각하다가 트리구조임을 알아채고 tree dp 인것같아서 그쪽으로 생각을 돌렸다. a노드에서 자식노드 b,c,d 가 있을 때 그중 최소값으로 연결하고, 나머지는 더하면 되는데 구현에 대한 아이디어가 부족했다. 탑다운으로 짜려고 했는데 먼가 생각할게 많은 것 같았고, 위상정렬로 풀었다. 지금 생각해보니 위상정렬이랑 dp 바텀업이랑 모양새가 많이 비슷한 것 같다. #include using namespace std; #define M..
-
백준 16494 가장 큰 값전공/알고리즘 2022. 3. 15. 01:25
https://www.acmicpc.net/problem/16494 16494번: 가장 큰 값 첫째 줄에 N과 M(1 ≤ M ≤ N ≤ 20)이 주어진다. 둘째 줄에는 수열에 속한 수가 주어진다. 수는 공백으로 구분되어져 있고, 절댓값이 100보다 작거나 같은 정수이다. www.acmicpc.net 이전에 생각 안 난 문제를 적어두었는데 사람들이 유입되길래 풀어봄 문제 조건에서 빠진 부분이 있는데 중복된 index를 뽑을 수는 없다. 문제는 M개의 그룹을 뽑을 때 그 그룹 합의 최대를 구하는 문제이다. 모든 i,j 쌍에 대해서 누적합을 구한 뒤, dp식을 세운다. dp[i][j] := [i, j]에서의 연속된 수열의 최대 합 따라서 N^4으로 dp테이블을 만들 수 있다. 그 다음에 1~N까지 중 M개의 ..
-
백준 1202 (보석 도둑)전공/알고리즘 2022. 1. 12. 14:35
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 가방이 K개 존재하고, 그 가방에 보석을 단 하나만 담을 수 있다. 그리고 가방에 제한이 있는데 무게 제한이 있고, 보석은 무게와 가치를 가지고 있다. 접근은 간단하다고 생각한다. 그리디하게 보석을 가치 순으로 정렬하고, 그 가치 순서대로 가방에 넣으면 된다. 우리가 그 전에 풀어왔던 냅색 dp와 달리 가방에는 단 하나의 보석만 들어갈 ..
-
백준 1757 (달려달려)전공/알고리즘 2021. 11. 16. 13:34
https://www.acmicpc.net/problem/1757 1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 달리기 하다가 N분 지났을 때 조건을 만족하면서 갈 수 있는 최대거리 조건은 다음과 같다. 체력 한계 초과 불가 끝날 때 체력 풀 쉬기 시작하면 체력 풀 될때까지 쉬어야 한다. 이 문제가 dp인건 먼저 알고 풀었다. 그러면 dp라고 생각할 수 있게 만드는 것들이 뭐가 있는지 생각해보자 완전탐색요소가 존재한다. 모든 단계에서 할 수 있는건 그 전 단계에서 온 상태에서의 뛴다 or 안 뛴다. 결국 구하려고 하는..