누적 합3

• 

  [BOJ_16139] 인간-컴퓨터 상호작용 📌 문제 링크: https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net ❌ 내 풀이(Failure) - 50점: ✅ 내 풀이(Success) - 100점, PyPy3 제출: 🧐 Review: 서브테스크 1번을 맞춰서 50점을 받기는 쉽지만, 100점을 받기 위해서는 입력 값의 크기를 고려해서 시간 복잡도를 계산해야 한다. 문자열의 길이와 질문 개수 q는 최대 200,000으로 q번 동안 문자열 전체에 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 5.

• 

  [BOJ_21921] 블로그 📌 문제 링크: https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 이 문제는 약 5개월 전인 3월 5일에 풀어보려고 했으나 틀렸던 문제다. 그때 당시 풀이를 확인하지 않고 다음에 다시 풀어보겠다는 생각에 넘어갔었고 꽤 시간이 흘렀지만 이 문제를 풀기 위한 알고리즘을 공부하고 다시 풀어보니 어렵지 않게 해결할 수 있었다. 문제를 풀고 나서 다른 사람들의 풀이를 찾아보니 누적 합과 슬라이딩 윈.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 16.

• 

  [BOJ_11659] 구간 합 구하기 4 📌 문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: 특정 구간의 합을 구하기 위해 누적 합을 이용한다. 예를 들자면 인덱스 2 ~ 4 사이의 구간 합을 구하기 위해 인덱스 4까지의 누적 합에서 인덱스 1까지의 누적 합을 뺀다면 해당 구간 사이의 구간 합을 구할 수 있다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 8. 15.