알고리즘
-
[BOJ 20957, C++] 농부 비니알고리즘/BOJ 2021. 8. 31. 23:39
https://www.acmicpc.net/problem/20957 20957번: 농부 비니 타고난 농사꾼 비니는 최근 숫자 공부에 푹 빠졌다. 열심히 숫자 공부를 하던 비니는 놀라 자빠질 수밖에 없었다. 숫자 7이 비니가 가장 아끼는 낫과 비슷하게 생겼기 때문이다. 옛말에 낫 놓고 7 www.acmicpc.net 풀이 일단 숫자의 합이 7의 배수가 되는 경우의 규칙성은 찾기가 힘들어 보이고, 숫자의 곱이 7의 배수가 되는 경우에는 곱할 때 0 또는 7이 있으면 됩니다. 7이 들어가는 것은 당연하니 생략하고, 0이 들어가는 것은 보통 배수라고 하면 1이상의 자연수부터 생각하는데 문제 힌트에서 70의 경우에도 조건을 만족한다고 했으니까 0도 가능하게 됩니다. 모듈러 연산이 있으니까 우선 DP를 생각해볼 수..
-
[BOJ 20956, Python 3] 아이스크림 도둑 지호알고리즘/BOJ 2021. 8. 31. 23:29
https://www.acmicpc.net/problem/20956 20956번: 아이스크림 도둑 지호 지호는 매일 아이스크림 가게에 방문한다. 아이스크림을 먹던 지호는 놀라 자빠질 수밖에 없었다. 실수로 민트초코 맛을 먹었기 때문이다. 대다수의 사람은 치약 맛이 난다는 이유로 민트초코 www.acmicpc.net 풀이 아이스크림의 양이 가장 많은 것부터 먹으면서 7의 배수 양을 가진 아이스크림을 먹을 경우, 아이스크림 먹는 순서를 뒤집는다고 합니다. 이건 생각해보면 딕셔너리 말고는 답이 안보입니다. 딕셔너리는 dict[아이스크림 양] = [1, 3, 5, 6] 이렇게 key값을 아이스크림 양으로 저장하고, value값은 아이스크림 먹는 번호를 저장하면 됩니다. 이때 key값은 in을 사용하면 시간이 오..
-
[BOJ 20955, Python 3] 민서의 응급 수술알고리즘/BOJ 2021. 8. 31. 23:16
https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 풀이 일단 연결되지 않은 두 뉴런을 연결할 때를 생각해보면 트리와 트리를 연결할 때만 필요하다는 것을 알 수 있습니다. 우선 이 값은 (트리의 수) - 1로 결정됩니다. 이미 연결된 두 뉴런을 끊을 때를 생각해보면 하나의 연결 요소를 트리로 만들 때만 사용한다는 것을 알 수 있습니다. 이건 bfs나 dfs를 이용해서 사용하는 간선을 구해주면 됩니다. 이러면 (해당 연결 요소의 간선의 개수) - ..
-
[BOJ 20954, Python 3] 택배 기사 민서알고리즘/BOJ 2021. 8. 31. 23:06
https://www.acmicpc.net/problem/20954 20954번: 택배 기사 민서 민서는 택배 기사이다. 활기차게 월요일을 맞은 민서는 놀라 자빠질 수밖에 없었다. 코로나19 사태로 인하여 비대면 활동이 확산되면서 택배 물량이 급증하였기 때문이다. 민서에게 배정된 택배 www.acmicpc.net 풀이 일단 x = 2의 거듭제곱 수만 살펴보면 아래와 같은 수열이 나옵니다. http://oeis.org/A048487 A048487 - OEIS A048487 a(n) = T(4,n), array T given by A048483. 14 1, 6, 16, 36, 76, 156, 316, 636, 1276, 2556, 5116, 10236, 20476, 40956, 81916, 163836, 3..
-
[BOJ 20953, Python 3] 고고학자 예린알고리즘/BOJ 2021. 8. 31. 22:31
https://www.acmicpc.net/problem/20953 20953번: 고고학자 예린 예린은 고고학자이다. 예린은 강원대학교 백록관 지하에서 고인돌이 발견되었다는 소식을 듣고 누구보다 빠르게 백록관에 도착하였다. 고인돌을 본 순간 예린은 놀라 자빠질 수밖에 없었다. 고 www.acmicpc.net 풀이 맨 마지막 줄 for문을 보면 for ( k = 0; k < j; k++) sum ++;인 것을 보아하니 sum = j가 되는 것을 알 수 있습니다. 그리고 윗 줄 for문을 보면 for ( j = 0; j < a + b; j++)이므로 sum = 1 + 2 + ... + j가 되겠네요. 이것은 1부터 n까지 수의 합을 더하는 공식인 n * (n + 1) // 2을 생각할 수 있습니다. j = ..
-
[BOJ 20952, Python 3] 게임 개발자 승희알고리즘/BOJ 2021. 8. 25. 15:57
https://www.acmicpc.net/problem/20952 20952번: 게임 개발자 승희 승희는 최근 369 게임에 푹 빠졌다. 369 게임을 하던 승희는 놀라 자빠질 수밖에 없었다. 369 게임을 잘하는 자기 자신이 너무 대견하였기 때문이다. 369 게임이 식상해진 승희는 369 게임을 변형한 71 www.acmicpc.net 1e9 + 7을 써야 하는 걸 10e9 + 7로 써두고, 알고리즘이 틀린 줄 알고 엄청 헤맸다 😭😭 풀이 N = M = 100,000이므로 하나하나씩 비교하는 O(N^2)는 돌아가지 않는 것은 당연합니다. 그래서 좀 더 빠르게 계산을 할 수 있는 방법을 찾아야 하는데, 문제에서 B[i]를 더하다가 7의 배수 원소가 나오면 삭제한다고 했으므로 7로 만들 수 있는 나머지인..
-
[BOJ 20951, C++] 유아와 곰두리차알고리즘/BOJ 2021. 8. 25. 15:41
https://www.acmicpc.net/problem/20951 20951번: 유아와 곰두리차 유아는 새해를 맞이하여 V.Nets의 자율 주행 자동차를 구매하였다. 유아는 새 차를 타고 바다로 가서 회를 잔뜩 먹고 올 것이다(유아는 감염병 예방을 위한 정부의 방역지침을 준수한다). 고속도 www.acmicpc.net 풀이 그래프 문제이니까 바로 그래프 알고리즘을 생각해볼 수 있지만, 문제를 읽다보면 같은 경로를 여러번 지나칠 수 있기 때문에 그래프 알고리즘이 아닌 다른 알고리즘을 생각해볼 수 있습니다. 모듈러 연산을 보아하니 DP 또는 그리디부터 추론할 수 있는데, 그리디는 어려우니 DP부터 생각해보면 dp[N][8]로 충분히 만들 수 있고, 1-3-2, 2-3-1 같이 길이가 2일 때 정점 3에서 ..
-
[BOJ 20950, Python 3] 미술가 미미알고리즘/BOJ 2021. 8. 25. 15:32
https://www.acmicpc.net/problem/20950 20950번: 미술가 미미 미미는 미적 감각이 뛰어난 미술가이다. 미미는 때때로 여러 물감을 섞어 새로운 색의 물감을 만들고는 한다. 어느 날 그림을 그리던 미미는 놀라 자빠질 수밖에 없었다. 미미가 가장 아끼는 곰 www.acmicpc.net 풀이 문제를 읽어보면 색을 섞을 수 있는 모든 경우의 수를 확인해야한다는 것을 알 수 있습니다. 이러면 알고리즘 범위가 좀 좁혀지고, 거기다가 N의 값이 30이라 작기 때문에 바로 백트래킹을 생각해냈습니다. 근데 백트래킹을 너무 오랜만에 풀어서 그런지 구현에서 자꾸 틀려서 좀 고생했네요 문제에서 색깔 하나만 사용할 수는 없기 때문에 그 부분을 유의해서 백트래킹을 구현해주면 됩니다. 코드 1 2 3..