본문 바로가기
반응형

알고리즘 풀이164

[백준 13275] 가장 긴 팰린드롬 부분 문자열 (python) https://www.acmicpc.net/problem/13275 13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acmicpc.net 가장 긴 팰린드롬 부분 문자열 문제 문자열 S의 부분 문자열 중에 가장 길이가 긴 회문을 구하는 문제 Manacher 알고리즘을 이용하여 해결할 수 있었다. https://www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 문자열 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. www.acm.. 2023. 4. 16.
[백준 14444] 가장 긴 팰린드롬 부분 문자열 (python) https://www.acmicpc.net/problem/14444 14444번: 가장 긴 팰린드롬 부분 문자열 알파벳 소문자로만 이루어진 문자열 S가 주어졌을 때, S의 부분 문자열 중에서 팰린드롬 이면서 길이가 가장 긴 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 가장 긴 팰린드롬 부분 문자열 문제 문자열 S의 부분 문자열 중에 가장 길이가 긴 회문을 구하는 문제 Manacher 알고리즘을 이용하여 해결할 수 있었다. https://www.acmicpc.net/problem/13275 13275번: 가장 긴 팰린드롬 부분 문자열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있으며 길이는 1보다 크거나 같고, 100,000보다 작거나 같다. www.acm.. 2023. 4. 16.
[알고리즘] Manacher 알고리즘 정리 (python) Manacher 알고리즘 회문(Palidnrome)에 관한 문제를 빠르게 풀 수 있도록 만들어주는 알고리즘 문자열 S의 부분 문자열 중에서 팰린드롬인 것 중 가장 긴 것의 길이를 구하는 알고리즘을 해결하는 것에 최적화. 시간 복잡도 : O(n) 적용 방법 문자열 S에 대해 새로운 배열 A를 정의 배열 A의 i번째 A[i]는 i번째 문자를 중심으로 하는 가장 긴 회문의 반지름 크기 Banana를 예시로 들면, S[3]인 문자 a는 자신을 기준으로 an(a)na으로 최대 2의 반지름을 가지므로, A[3] = 2 위 방법으로 배열 A을 구성하면 [0, 0, 1, 2, 1, 0]의 값을 얻을 수 있음 문제점 어떤 위치(인덱스)를 중심으로 고려하기에 짝수가 아닌 홀수의 회문만 구할 수 있음 구한 결과가 회문의 한.. 2023. 4. 16.
[백준 16235] 나무재태크 (python) https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 나무 재태크 문제 나무를 심고, 봄 여름 가을 겨울이 지나갔을 때, 정해진 규칙대로 진행될 경우 최종적으로 생기는 나무의 수를 찾는 문제 for문을 이용한 반복구조, 3중 배열을 활용해여 해결 할 수 있었다. 📌문제 접근 포인트 1. 문제에 조건이 꽤 많다. 하나하나 정리해서 천천히 생각해보자. 조건을 놓칠 경우 꼬이게 될 수 있다. 2. 양분에 해당하는 리스트를 하나 따로 만들어.. 2023. 4. 15.
[백준 16236] 아기 상어(python) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기 상어 문제 아기 상어보다 작은 물고기들을 먹어가면서 이동하면서 걸린 총 시간을 구하는 문제 BFS를 이용한 구현 문제로, 조건에 맞춰 하나씩 구현해나가서 구현할 수 있었다. 📌 문제 접근 포인트 1. 조건이 굉장히 많다. 구현에 필요한 조건을 정리해서 생각해보자. 조건을 놓치면 찾느라 시간이 굉장히 소비가 많이 될 수 있다. 2. BFS 탐색을 구현해주는 과정에서 방문 처리 및 거리를.. 2023. 4. 15.
[백준 4134] 다음 소수 (python) https://www.acmicpc.net/problem/4134 4134번: 다음 소수 정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오. www.acmicpc.net 다음 소수 문제 n보다 크거나 같은 소수 중에서 가장 작은 소수를 찾는 문제 에라토스테네스의 체를 이용해서 풀 수 있었다 📌 문제 접근 포인트 1. n보다 크거나 같은 소수를 찾아야 하므로, n이 소수인지 아닌지 판별하고 +1씩 늘려가도록 알고리즘을 고려해보자. 2. 소수를 판별하는 과정에서 숫자가 굉장히 크므로 에라토스테네스의 체를 이용해서 빠르게 찾아내주고, 이를 활용하여 소수 판별을 해주자. 3. 소수를 판별하는 과정에서 n의 제곱근 만큼 탐색을 진행하게 되는.. 2023. 4. 14.
반응형

티스토리툴바