문제 링크 : https://www.acmicpc.net/problem/1053 1053번: 팰린드롬 공장 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. www.acmicpc.net 1. 접근 방법 어떤 문자열을 팰린드롬으로 만드는데, 사용할 수 있는 연산이 총 4가지가 있어 처음에는 일반적인 백트래킹으로 접근했다. 하지만 과정마다 팰린드롬임을 확인하는 것이 많은 시간이 필요하고, 각 연산을 문자열의 몇 번째 위치에서 적용할지도 고민해야 할 문제였다. 그래서 백트래킹이 아닌 재귀를 활용한 DP로 접근해 보았다. 2. 풀이 코드 🖥python 코드 링크 : https:/..

문제 링크 : https://www.acmicpc.net/problem/ 1. 문제 설명 어떤 수가 주어지면, 그 수의 약수를 구하거나 찾거나 활용해야 한다. 대부분의 경우, 그리고 코딩 테스트에 등장하는 문제는 에라토스테네스의 체를 활용하는 정도인데, 백준에서는 그 이상의 지식이 필요한 문제가 종종 있다. 이 문제도 결론을 먼저 말하자면, 오일러 피 함수를 사용해야 한다. 2. 문제 풀이 풀이 코드 : Python 우선 오일러 피 함수를 알아보자. 오일러 피 함수는, 어떤 정수가 주어졌을 때, 그 정수보다 더 작은 수 중에서 서로소인 수의 개수를 알아낼 수 있는 함수이다. 함수는 다음과 같이 계산할 수 있고, 이 값을 계산하기 위해서는 n의 약수가되는 소수를 발견해야 한다. for i in range(..

문제 링크 : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 접근 방법 양팔 저울과 추를 활용하여 특정 무게를 확인할 수 있는지 묻는 문제인데, 추가 양쪽 모두 올라갈 수 있다. 그래서 추들을 한쪽에 올려서 가능한지 뿐만 아니라, 일부 추가 반대쪽에 올라가서 가능한 경우도 고려해야 한다. DP로 배낭문제 방식으로 접근했는데, 각 무게가 가능한지 저장, 이후 주어지는 무게 별로 확인하여 출력하는 방식으로 구성했다. 2. 풀이 코드 🖥pyth..

문제 링크 : https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 1. 접근 방법 주어지는 알파벳 판에서 등장하는 단어들을 찾아내는 문제로, 알파벳 보드 판에서는 8방향 탐색이 가능하고, 찾아낸 단어들은 총 3가지 출력을 해야 한다. 문자열을 찾는 문제여서 트라이를 활용했다. 주어진 단어를 트라이 구조로 만들어 탐색에 활용했고, 시간을 줄이기 위해 몇 차례 시행착오를 거쳤다. 2. 풀이 코드 🖥python 코드 링크 : https..

문제 링크 - 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - 연구소 2 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net - 연구소 3 https://www.acmicpc.net/problem/..

문제 링크 : https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 1. 접근 방법 주어진 점으로 이루어진 그래프를 두 개의 부분 그래프로 나누는 문제인데, 다른 조건이 없다 보니 모든 경우의 수를 탐색해야 한다. 다행히도 점이 최대 10개만 주어지므로 큰 어려움 없이 해결할 수 있다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/17000/17400/17471.py..

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 1. 접근 방법 주어진 배열에 대해 연속된 구간 중 특정 값을 넘지 않는 최소 크기를 만족하는 구간을 최대한 많이 구해야 하는 문제이다. 그러한 모든 구간을 구하는 것과 동시에 정답을 같이 구하는 과정은 간단하지는 않았다. 아마 조금 더 난이도 높은 문제에서는 동시에 처리하는 방법 등을 요구할 수 있겠지만, 이 문제는 문제에서 요구하는 구간을 찾는 과정, 정답을 찾는 과정을 따로 실행해도 가능하다. 그래서 투포인터를 활용하여 문제에서 요구한 ..

문제 링크 : https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. 접근 방법 기본적으로 최단 경로를 찾아야 하는 문제인데, 추가적인 조건이 있어서 접근이 조금 까다로웠다. 시작점부터 도착지까지 최대 시간을 구하는 것은 어렵지 않게 해결할 수 있다. 모든 모로를 확인하며 더 늦은 시간으로 갱신하면 된다. 하지만, '이런 사람들이 지나는 도로의 수를 카운트하여라' 부분에서 시간이 걸렸다. 문제에서 말한 문장은 수정이 필..

1. Segment Tree 세그먼트 트리는 트리 형태의 데이터를 활용해 어떤 구간에 대한 정보를 활용하는 데 사용한다. 아직 블로그 글에서 세그먼트 트리를 다루지 않았지만, 후에 다루어 볼 것이고, 먼저 lazy propagtion의 적용을 이 글에서 다루어 볼 것이다. 2. lazy propagation 느린 전파라고도 말하지만, 게으른 전파가 알고리즘을 더 잘 나타낼 수 있는 단어라고 생각하여 게으른 전파라 부르겠다. 세그먼트 트리에서 게으른 전파는 값을 갱신할 때 특정 값이 아니라 범위의 값을 변경할 때 사용한다. 세그먼트 트리는 log(N)으로 가능하지만, 범위의 값을 경신하기 위해 Nlog(N)의 연산이 필요하게 된다. 그래서 갱신을 트리의 모든 값에 항상 적용하는 게 아니라 필요할 때만 하는..