전공/알고리즘
-
백준 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 안 뛴다. 결국 구하려고 하는..
-
백준 20500 (Ezreal 여눈부터 가네 ㅈㅈ)전공/알고리즘 2021. 11. 16. 13:19
https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 1과 5로만 이루어진 수 중에서 15로 나누어 떨어지는 수가 몇 개있는지 세보자 1자리 1 5 X 2자리 15 O 55 11 51 1가지 이렇게 하다가 알 수 있는 간단한 사실 15 = 3*5 따라서 15의 배수이려면 k*(3*5) 이어야 하고, 5로 나누어 떨어져야 15로 나누어 떨어진다. 그러므로 1의 자리 수가 1이라면 불가능 끝에는 5만 올 수 있다. 여기서부터 조금 막혔다. 근데 10^N은 15로 나누었을때 나머지가 10이며 5*10^N은 15로 나누었을때 나머지가 5였다. 9876..
-
백준 233328 (마을 구하기)전공/알고리즘 2021. 11. 7. 17:29
https://www.acmicpc.net/problem/23328 23328번: 마을 구하기 미소가 사는 마을에는 $N$채의 집이 일렬로 있다. 어느 날 밤, 마을 내 모두가 잠든 사이에 집마다 폭탄 혹은 폭탄 쉴드가 배치되었다. 폭탄과 폭탄 쉴드는 다음과 같은 특징이 있다. 폭탄은 알파 www.acmicpc.net 폭탄을 뭉쳐놓아야 우리가 원하는 문제를 해결 가능 왜냐면 폭탄을 쉴드나 벽으로 감싸서 최대한 마을과 인접한 폭탄이 없도록 만들기 위함이다. 문자열로 받고 폭탄을 방어할 쉴드가 몇개인지 세준다. 2개 이상 1개 0개 간단한 0개부터 가장 좌측 or 가장 우측에 모아두면 0개에서 1개의 마을이 폭파된다. 0개인경우는 마을이 없는 경우 BBBB... -> 1 ....BBBB -> 2 1번은 B보..