본문 바로가기

ps45

[Python] 백준 2629 양팔저울 문제 링크 : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 접근 방법 양팔 저울과 추를 활용하여 특정 무게를 확인할 수 있는지 묻는 문제인데, 추가 양쪽 모두 올라갈 수 있다. 그래서 추들을 한쪽에 올려서 가능한지 뿐만 아니라, 일부 추가 반대쪽에 올라가서 가능한 경우도 고려해야 한다. DP로 배낭문제 방식으로 접근했는데, 각 무게가 가능한지 저장, 이후 주어지는 무게 별로 확인하여 출력하는 방식으로 구성했다. 2. 풀이 코드 🖥pyth.. 2022. 10. 2.
[Python] 백준 9202 Boggle 문제 링크 : https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net 1. 접근 방법 주어지는 알파벳 판에서 등장하는 단어들을 찾아내는 문제로, 알파벳 보드 판에서는 8방향 탐색이 가능하고, 찾아낸 단어들은 총 3가지 출력을 해야 한다. 문자열을 찾는 문제여서 트라이를 활용했다. 주어진 단어를 트라이 구조로 만들어 탐색에 활용했고, 시간을 줄이기 위해 몇 차례 시행착오를 거쳤다. 2. 풀이 코드 🖥python 코드 링크 : https.. 2022. 9. 20.
[Python] 백준 연구소 시리즈 문제 링크 - 연구소 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/.. 2022. 9. 8.
[Python] 백준 17417 게리맨더링 문제 링크 : 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.. 2022. 9. 5.
[Python] 백준 20181 꿈틀꿈틀 호석 애벌레 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 1. 접근 방법 주어진 배열에 대해 연속된 구간 중 특정 값을 넘지 않는 최소 크기를 만족하는 구간을 최대한 많이 구해야 하는 문제이다. 그러한 모든 구간을 구하는 것과 동시에 정답을 같이 구하는 과정은 간단하지는 않았다. 아마 조금 더 난이도 높은 문제에서는 동시에 처리하는 방법 등을 요구할 수 있겠지만, 이 문제는 문제에서 요구하는 구간을 찾는 과정, 정답을 찾는 과정을 따로 실행해도 가능하다. 그래서 투포인터를 활용하여 문제에서 요구한 .. 2022. 9. 4.
[Python] 백준 1948 임계경로 문제 링크 : https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 1. 접근 방법 기본적으로 최단 경로를 찾아야 하는 문제인데, 추가적인 조건이 있어서 접근이 조금 까다로웠다. 시작점부터 도착지까지 최대 시간을 구하는 것은 어렵지 않게 해결할 수 있다. 모든 모로를 확인하며 더 늦은 시간으로 갱신하면 된다. 하지만, '이런 사람들이 지나는 도로의 수를 카운트하여라' 부분에서 시간이 걸렸다. 문제에서 말한 문장은 수정이 필.. 2022. 8. 22.
[알고리즘] Segment Tree, lazy propagation 1. Segment Tree 세그먼트 트리는 트리 형태의 데이터를 활용해 어떤 구간에 대한 정보를 활용하는 데 사용한다. 아직 블로그 글에서 세그먼트 트리를 다루지 않았지만, 후에 다루어 볼 것이고, 먼저 lazy propagtion의 적용을 이 글에서 다루어 볼 것이다. 2. lazy propagation 느린 전파라고도 말하지만, 게으른 전파가 알고리즘을 더 잘 나타낼 수 있는 단어라고 생각하여 게으른 전파라 부르겠다. 세그먼트 트리에서 게으른 전파는 값을 갱신할 때 특정 값이 아니라 범위의 값을 변경할 때 사용한다. 세그먼트 트리는 log(N)으로 가능하지만, 범위의 값을 경신하기 위해 Nlog(N)의 연산이 필요하게 된다. 그래서 갱신을 트리의 모든 값에 항상 적용하는 게 아니라 필요할 때만 하는.. 2022. 8. 19.
[Python] 백준 13258 복권 + 은행 문제 링크 : https://www.acmicpc.net/problem/13258 13258번: 복권 + 은행 두 번째 예제의 경우에 첫 주가 지난 후 1/3의 확률로 (3, 2, 2)가, 1/3의 확률로 (2, 3, 2)가, 1/3의 확률로 (2, 2, 3)이 된다. 둘째 주에 (3, 2, 2)는 기댓값이 3.4286이 되고, (2, 3, 2)와 (2, 2, 3)은 기댓값이 2.2857 www.acmicpc.net 1. 접근 방법 간단한 확률 계산 문제로, 기댓값을 알아내면 된다 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/13000/13200/13258.py GitHub - mintropy/PS:.. 2022. 8. 5.
[Python] 백준 1655 가운데를 말해요 문제 링크 : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1. 접근 방법 입력을 계속 받으며 중간 값을 출력해야 한다. 이때, 입력이 많기 때문에 계속 정렬을 한다거나 탐색을 하면 시간 초과가 날 것으로 보인다. 그렇기 때문에 중간값을 기준으로 큰 값, 작은 값을 각각 보관하고, 입출력이 많을 수 있기 때문에 heap 구조를 활용했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintr.. 2022. 8. 3.

티스토리툴바