목록2024/09 (49)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/2504 2. 접근 방법이번 문제는 올바른 괄호 찾기 + 분할 정복에 대한 적용을 필요로 하는 문제 같았다.2개의 stack을 사용하여 이번 문제를 해결하였다. 괄호들이 처음 포함 된 stack을 b_stack 하나씩, pop하여 저장해 줄 stack을 a_stack이라고 선언하였다.만약, b_stack에서 pop 된 녀석이 ) 또는 ] 라면, a_stack에 append 해주었다.그 외 ( 또는 [ 을 만나게 된다면, 3개의 경우로 나누어서 판단하였다.a_stack[-1] 이 짝이 맞게 ) 을 반환하는 경우a_stack[-1] 이 짝이 만제 ] 을 반환하는 경우a_stack[-1] 이 숫자를 반환하는 경우1번의 경우엔, )을 pop 하여..
1. 문제https://www.acmicpc.net/problem/2493 2. 접근 방법2개의 stack을 이용해서 푸는 것이 적절하다고 생각하였다. 쏘기 전의 레이저들을 모아놓은 것을 b_shoot이라고 선언하였다.또한, [높이, 송신탑 번호] 로 저장해 두어, 추후에 레이저를 쏜 송신탑 번호를 계산하도록 하였다. b_shoot에서 하나 pop한 후, a_shoot에 저장된 값의 높이가 pop된 높이보다 작다면, 해당 a_shoot 위에 있는 블록이 b_shoot에서 pop 된 송신탑을 때린다고 생각하면 된다. 따라서, hit = [0] * n 으로 선언된 곳에, hit[b_shoot에서 pop된 송신탑 번호 -1 ] 로 저장하면 된다.만약, 작다면, break를 한 후, a_shoot에 하나의 새로..
1. 문제https://www.acmicpc.net/problem/1629 2. 접근 방법처음엔, 패턴을 찾아서 돌리는 방법으로 코드를 구현했었다.하지만, 가차없이 시간 초과가 떴고 다른 방법을 찾다가 '빠른 거듭제곱의 알고리즘' 에 대해서 알게 되었다.이는 분할 정복을 이용한 것이다.a^13의 경우 a^12 * a 와 동일하다또한 a^12의 경우 half = a^6 일 때, half * half와 동일하다.따라서 이를 이용해서, 재귀를 구현하면서 분할 정복이 가능해 지는 것이다. 3. 코드from collections import defaultdictimport sysdef remainder(a, b, c): if b == 0: return 1 elif b % 2 == 0: ..
1. 문제https://www.acmicpc.net/problem/2630 2. 접근 방법대상이 되는 사각형에서, 합이 n**2 혹은 0 이라면, blue +=1, white +=1을 해준 후, return을 해준다.만약, 이에 해당되지 않는다면, 4개로 자른 후, 다시 함수에 넣어주어야 한다. 3. 코드blue = 0white = 0def make_origami(n): origami = [] for i in range(n): ori = list(map(int, input().split())) origami.append(ori) return n, origamidef count_blue_white(left, right, up, down, origami, n): ..