Today, I will

1. 백준 14719번(빗물) 풀이 방법 모노톤 스택 알고리즘을 활용하여 풀 수 있습니다. Monotonic stack 모노톤 스택 알고리즘은 다음과 같은 방법으로 동작합니다. 스택이 비어 있거나, 스택의 맨 위에 있는 원소가 현재 원소보다 큰 경우, 현재 원소를 스택에 push 합니다. 스택의 맨 위에 있는 원소가 현재 원소보다 작은 경우, 스택에서 원소를 꺼내면서 빗물의 양을 계산합니다. 이 때, 빗물의 양은 스택에서 꺼낸 원소와 현재 원소 사이에 고일 수 있는 빗물의 양입니다. 빗물의 양을 계산한 후, 스택에 현재 원소를 push 합니다. 이 과정을 모든 원소에 대해 반복하면, 스택에는 모노톤한 부분 수열이 저장되고, 빗물의 양을 계산할 수 있습니다. 모노톤 스택 알고리즘은 시간 복잡도가 O(n)으..

1. 백준 13334번(곱셈) https://www.acmicpc.net/problem/13334 안녕하세요! FlyDuck_Dev🦢 입니다. 오늘은 백준 13334번 철로 문제를 푸는 해결 과정을 정리하는 포스팅을 작성해보도록 하겠습니다. 2. 기존 풀이 left, right 투포인터를 잡고 각각 선분 d의 시작과 끝이라고 생각하고, left를 통근자들의 home 좌표 기준을 삼아 D만큼(백준 문제에서의 L) 밀면서 사실상의 완전탐색 형식으로 문제를 풀면 되겠다고 생각해서 아래와 같이 코드를 작성하였습니다. a = int(input()) dis = [] for i in range(a): dis.append(tuple(map(int, input().split()))) d = int(input()) di..

1. 백준 1629번(곱셈) 안녕하세요! FlyDuck_Dev🦢 입니다. 오늘은 백준 1629를 풀면서 겪었던 어려움과 문제 해결을 위해 이해한 합동식, 모듈러 연산에 대해 정리하는 포스팅을 작성해도록 하겠습니다. 2. 기존 풀이 factorial을 짜듯이 재귀를 활용해서 문제를 풀면 되겠다고 생각해서 아래와 같이 코드를 작성하였습니다. import sys a, b, c = map(int, sys.stdin.readline().strip().split()) def power(a,n): if n