아롱이의 PS하는 블로그

"파이썬으로 구현하는"시리즈 4세그먼트 트리(Segment Tree)Bottom-Up오늘은 파이썬으로 Bottom-Up 세그먼트 트리를 어떻게 구현하는지 알아볼 것이다.지난번에 Top-Down 구현 올리고 계속 올려야지 하다가 1달동안 미뤄졌다;;;;; 다른 블로그들을 보면 Top-Down이 Bottom-Up 보다 이해하기 쉽다고 한다.개인차일 수도 있는데, 나는 개인적으로 Bottom-Up이 훨씬 이해하기도 쉽고 구현도 간단해서 매우매우 좋아한다!! Bottom-Up의 구현에서는 Top-Down과 인덱스 저장 방식이 약간 다르다. 오늘은 [3, 1, 4, 1, 5, 9, 2]의 7개의 원소를 다뤄보도록 하자.Bottom-Up 구현에서는 Top-Down과 달리 7개의 원소가 모두 같은 높이의 리프 노드에..

왜긴 왜야. 겁나게 빠르니까. 어저께 알고리즘 스터디에서 Bulldozer Trick을 배우고 백준 9484 문제를 풀었었다.https://www.acmicpc.net/problem/9484파이썬으로 아무리 열심히 구현을 해도 메모리 초과가 뜨는 것이 아니겠는가. 친구의 말을 들어보니 파이썬으로 풀기 매우매우 어렵다고 한다.일단 알고리즘 자체는 맞는 것 같은데.... 그래서 GPT의 도움을 받아 '내 코드를 C++로 번역해줘' 했다.바로 AC 맞았다. 허망감을 느낀 나는 파이썬을 버리고 이제 C++로 옮기려고 한다. 하지만 나는 C++을 모른다.처음부터 다시 시작해야한다. 같이 배워요, C++.

https://www.acmicpc.net/problem/29157문제 무한한 크기의 2차원 격자판이 있다. 성모는 좌측 상단의 점 $(0, 0)$에 있고, 우측 하단의 $(N, M)$에 있는 찬민이를 만나러 가려고 한다. 격자판 위에는 $K$개의 폭탄들이 격자점에 있기 때문에, 성모는 폭탄들을 피해서 이동해야 한다. 성모는 오른쪽, 또는 아래로만 이동할 수 있을 때, 성모가 폭탄을 피해서 찬민이가 있는 곳까지 도착할 수 있는 이동할 수 있는 경우의 수를 구하여라.입력첫 번째 줄에 정수 $N, M, K$가 공백으로 구분되어 주어진다. $(1\leq N, M\leq 1\,000\,000;$ $0\leq K\leq 20)$ 두 번째 줄부터 $K$개의 줄에 걸쳐 각 줄에 폭탄의 위치 $(X_{i}, Y_{i}..

https://www.acmicpc.net/problem/1150 문제당신은 큰 회사들의 컴퓨터 자료를 백업하여주는 정보통신회사를 운영한다. 자료 백업이 즐거운 일이 아니므로, 당신은 서로 다른 두 회사의 자료를 서로 백업하여 주는 시스템을 개발하여 당신이 집에서 게임을 즐기는 동안 백업이 이루어지게 하려 한다.모든 회사들은 직선인 길을 따라 위치하고 있다. 당신은 서로 백업을 하여 줄 두 회사를 짝 지어 주어야 하는데, 두 회사 사이에 네트워크 케이블을 연결 사용하여야 한다.네트워크 케이블은 대단히 비쌀 뿐 아니라, 지역 통신 회사에서는 당신에게 오직 k개의 네트워크 케이블을 제공한다 –이 말은 당신이 오직 k 쌍의 회사에만 백업을 할 수 있다는 뜻이다 (전체 2k 개의 회사). 어떤 회사도 두 개 이..

"파이썬으로 구현하는"시리즈 3매내처(Manacher)오늘은 갑자기 뜬금없이 파이썬으로 구현하는 매내처에 대해서 알아볼 것이다.원래는 세그먼트 트리 바텀업을 먼저 적었어야 했는데, 문제풀다가 매내처라는 천재적인 알고리즘을 공부하게 되어서 정리해본다. 먼저 매내처가 뭐하는 알고리즘인지 알아보자.팰린드롬이란 무엇인가?앞뒤가 대칭인 문자열을 팰린드롬이라고 한다. 우리말로 회문이라고 한다.예시로는 다음이 있다. 'bob''ABCBA''WAS IT A CAT I SAW' (이상한 나라의 앨리스에 나오는 유명한 회문)'다시합창합시다' 다음과 같은 예시들은 팰린드롬이 아니다. 'apple''팰린드롬''알고리즘' 매내처는 팰린드롬을 다루는 알고리즘인데, 구체적으로는 다음과 같은 문제를 풀 때 쓰인다. 문자열 S가 주어..

이 문제는 백준 14505 팰린드롬 개수 구하기 (Small)과 N의 범위만 다르고 똑같은 문제입니다.(그런데 Small 알고리즘은 생각 안나고 이 풀이가 먼저 바로 생각나서 그냥 Small도 이렇게 품..ㅋㅋㅋ) https://www.acmicpc.net/problem/14517https://www.acmicpc.net/problem/14505문제팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다.승수는 주어진 문자열의 부분수열 중 팰린드롬이 되는 부분수열의 개수를 알고싶어한다. (공집합은 포함하지 않는다)예를들어 'abb' 의 부분수..

https://www.acmicpc.net/problem/10220문제자연수 N이 주어질 때 다음과 같은 길이 N인 수열 A의 개수를 구하여라$A_i$ = A에서 i가 등장하는 횟수 (0 ≤ i 입력입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다. 그 다음에는 T개의 테스트 케이스가 주어진다.각 테스트 케이스에는 수열의 길이를 의미하는 하나의 자연수 N (1 ≤ N ≤ 100)이 입력으로 주어진다.출력각 테스트 케이스마다 한 줄에 가능한 A의 개수를 1,000,000,007로 나눈 나머지를 출력한다. 풀이내 백준 인생 처음으로 '찍어서' 맞춘 문제이다.(물론 증명도 이 글 뒷부분에 할 것이다. 맞추기만 하고 증명을 안하면 뭔가 찜찜하달까.) 일단 처음에는 작은 N에 대해서 ..

https://www.acmicpc.net/problem/28123문제 $2^n$은 십진법으로 표기했을 때 $k$자리 수이고, 가장 높은 자리의 숫자는 $x$이다.양의 정수 $n$, $k$, $x$가 주어질 때, $1$부터 $2^n$까지의 정수 중 4로 시작하는 2의 거듭제곱수의 개수를 구해 보자.입력첫째 줄에 양의 정수 $n$, $k$, $x$가 주어진다. ($1 \le n, k \le 10^{18};$ $1 \le x \le 9;$ $x \times 10^{k-1} \le 2^n \lt (x + 1) \times 10^{k-1}$) $|2^n/10^{k-1} - x - 0.5| \lt 0.5 - 10^{-6}$인 경우만 주어진다.출력 $1$부터 $2^n$까지의 정수 중 4로 시작하는 2의 거듭제곱수의..

https://www.acmicpc.net/problem/3015문제오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 ((2^{31})) 나노미터 보다 작다.사람들이 서 있는 순서대로 입력이 주어진다.출력..

https://www.acmicpc.net/problem/15824문제주헌이는 매운맛을 좋아한다. 정확히는, 매운맛을 먹음으로써 느낄 수 있는 고통에서 희열을 느끼는 진정한 '즐기는 자'다.'스코빌 지수'란 고추류가 가진 매운맛의 원인인 캡사이신의 농도를 수치화 한 단위이다. 주헌이가 느끼는 매운 정도는 굉장히 독특한데, 먹고 있는 메뉴의 절대 수치가 아닌 음식과의 상대수치에 기반한다. 예를 들어 [5, 2, 8]의 스코빌 지수를 가진 음식을 먹을 때 주헌이가 느끼는 매운 정도는 가장 높은 수치인 8과 가장 낮은 수치인 2의 차이인 6만큼의 매운맛을 느낀다. 이처럼 메뉴들의 스코빌 지수가 있을 때 그 최댓값과 최솟값의 차이를 "주헌고통지수"라고 정의한다.그림1. 고추처럼 보이지만 문제와는 무관합니다. 최..