DP10 [Python] 백준 1053 팰린드롬 공장 문제 링크 : https://www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. www.acmicpc.net 1. 접근 방법 어떤 문자열을 팰린드롬으로 만드는데, 사용할 수 있는 연산이 총 4가지가 있어 처음에는 일반적인 백트래킹으로 접근했다. 하지만 과정마다 팰린드롬임을 확인하는 것이 많은 시간이 필요하고, 각 연산을 문자열의 몇 번째 위치에서 적용할지도 고민해야 할 문제였다. 그래서 백트래킹이 아닌 재귀를 활용한 DP로 접근해 보았다. 2. 풀이 코드 🖥python 코드 링크 : https:/.. 2023. 1. 16. [Python] 백준 2629 양팔저울 문제 링크 : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 접근 방법 양팔 저울과 추를 활용하여 특정 무게를 확인할 수 있는지 묻는 문제인데, 추가 양쪽 모두 올라갈 수 있다. 그래서 추들을 한쪽에 올려서 가능한지 뿐만 아니라, 일부 추가 반대쪽에 올라가서 가능한 경우도 고려해야 한다. DP로 배낭문제 방식으로 접근했는데, 각 무게가 가능한지 저장, 이후 주어지는 무게 별로 확인하여 출력하는 방식으로 구성했다. 2. 풀이 코드 🖥pyth.. 2022. 10. 2. [Python] 백준 20181 꿈틀꿈틀 호석 애벌레 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 1. 접근 방법 주어진 배열에 대해 연속된 구간 중 특정 값을 넘지 않는 최소 크기를 만족하는 구간을 최대한 많이 구해야 하는 문제이다. 그러한 모든 구간을 구하는 것과 동시에 정답을 같이 구하는 과정은 간단하지는 않았다. 아마 조금 더 난이도 높은 문제에서는 동시에 처리하는 방법 등을 요구할 수 있겠지만, 이 문제는 문제에서 요구하는 구간을 찾는 과정, 정답을 찾는 과정을 따로 실행해도 가능하다. 그래서 투포인터를 활용하여 문제에서 요구한 .. 2022. 9. 4. [Python] 백준 2533 사회망 서비스(SNS) 문제 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 1. 접근 방법 DP와 DFS를 고민했는데, 나는 둘 다 사용한 방법으로 가닥을 잡았다. 문제를 해결하고 DP로만 해결하는 등의 풀이도 고민했지만, 잘 되지는 않아 시간은 조금 오래 걸렸지만, 해결했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2500/2533.py Git.. 2022. 3. 22. [Python] 백준 5557 1학년 문제 링크 : https://github.com/mintropy/baekjoon_py/blob/master/5000/5557.py GitHub - mintropy/baekjoon_py Contribute to mintropy/baekjoon_py development by creating an account on GitHub. github.com 1. 접근 방법 처음에 문제를 잘못 읽어 해결법을 잘 접근하진 못했다. 문제를 몇차례 읽고, 잘 이해하고는 생각보다 쉬운 DP로 해결했다. 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/5000/5557.py GitHub - mintropy/baekjoon_py Contri.. 2021. 12. 13. [Python] 백준 23257 비트코인은 신이고 나는 무적이다 문제 링크 : https://www.acmicpc.net/problem/23257 23257번: 비트코인은 신이고 나는 무적이다 코인 경력 4년차, 차트에 통달한 찬호는 이전 $N$개의 월봉을 통해 다음 월봉의 절댓값을 예측할 수 있는 아래의 공식을 만들어냈다. (다음 월봉의 절댓값) = 이전 $N$개의 월봉 중 중복을 허용해 www.acmicpc.net 1. 접근 방법 처음에는 XOR 연산에 대해 고민했는데, XOR 연산 처리는 비교적 쉽게 방법을 찾았다. https://stackoverflow.com/questions/52108901/xor-operation-on-three-values XOR operation on three values I have three boolean values. I nee.. 2021. 10. 30. [Python] 백준 16888 루트 게임 문제 링크 : https://www.acmicpc.net/problem/16888 16888번: 루트 게임 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 105)가 주어진다. 둘째 줄부터 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어지며, N(1 ≤ N ≤ 106)이 주어진다. www.acmicpc.net 1. 접근 방법 소수 판정 에라토스테네스 체와 비슷한 방식으로 해결될 것이라 생각이 들었다. 처음에는 각 조건마다 다음 턴을 거꾸로 탐색하는 과정을 반복했는데, 시간이 생각보다 많이 걸려서, 에라토스테네스 체에서도 사용하는 아이디어인, 소수를 발견하면 배수를 모두 소수가 아님을 표시하는 방법을 채용하여 해결했다. 2. 풀이 코드 🖥python코드 import sys input = sys.stdi.. 2021. 10. 28. [Python] 백준 10835 카드게임 문제 링크 : https://www.acmicpc.net/problem/10835 10835번: 카드게임 첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오 www.acmicpc.net 1. 접근 방법 각 차례마다 할 왼쪽 카드, 오른쪽 카드, 양쪽 카드를 버리를 행동을 할 수 있다. 오른쪽 카드를 버릴때만 조건이 있고, 점수를 얻을 수 있어서 모든 카드쌍에 대한 경우의 수를 탐색하지는 않을 것이다. 그래도, 각 카드가 최대 2000개씩이므로, DFS와 DP두가지 방법을 고민했다. 깊어야 4000번 들어가고, 더 깊게 탐색하지 않을 것 같.. 2021. 10. 10. [Python] 백준 2572 보드게임 문제 링크 : https://www.acmicpc.net/problem/2572 2572번: 보드게임 첫째 줄에 카드의 수 N이 주어진다. 둘째 줄에 N장의 카드의 색깔이 번호 순서대로 빈칸을 사이에 두고 주어진다. 셋째 줄에는 마을의 수 M과 길의 수 K가 빈칸을 사이에 두고 주어진다. 이어 K개 www.acmicpc.net 1. 접근 방법 처음에는 문제를 잘못 읽어 너무 많은 경우의 수가 아닌가 하는 생각을 했다. 카드를 순서대로 뽑으며 각 이동하는 모든 경우의 수를 계산해야 되고, 최대 탐색 마을의 수와 카드의 수가 적지 않아 DP와 DFS 중 고민했다. 그런데 길의 수가 마을에 비해 너무 많아 DP가 더 적절할 것 같아 DP로 접근했지만, 쉽지는 않았다. 2. 풀이 코드 🖥python import.. 2021. 9. 21. 이전 1 2 다음
