1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 내가 짠 코드 (메모리 초과) string = list(input()) input_stack = [] output_stack = [] for s in string: if s == ")": iter_num = -1 while 1: input_top = input_stack.pop() if input_top != "(": output_stack.append(input_top) else: iter_num = input_stack.pop() break input_..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ⭐️ 사고 과정 서로 다른 2개의 용액 -> 음 포인트는 2개 numbers 의 최대 길이는 10만 -> 즉 조합은 시간초과 두 수를 더했을 때 가장 0에 가깝게. 크건 작건 상관없이 두 수의 합이 0에 가까우면 된다. 브루트포스 안돼 📌 solved point 정렬할 때 절대값이 작은 순서대로 정렬해야한다. 그렇게 하면 서로 차이가 비슷한 것끼리 모임. 어떻게 절대값이 작은 순서대로 저장할 수 있는데? -> lambda bab..

https://www.acmicpc.net/problem/1527 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 브루트 포스 냄새가 살살 나길래 permutation 으로 첨엔 접근했다. 어케 접근했냐면, 입력된 수의 길이 만큰 [4] 와 [7] 배열을 늘림. 늘린 [4] , [7] 배열을 합침. -> [4] * len(인풋값) + [7] * len(인풋값) 합쳐진 배열을 permutations 에 넣고 경우의 수를 구함. 당연히 시간 초과남... 불필요하게 4 와 7 배열을 늘려놓은게 시간초과의 원인이었..

1895번: 필터 숫자 9개가 오름차순이나 내림차순으로 정렬되어 있을 때, 중앙값은 다섯 번째 숫자이다. 예를 들어, 1, 3, 4, 1, 2, 6, 8, 4, 10의 중앙값은 4이다. (1 ≤ 1 ≤ 2 ≤ 3 ≤ 4 ≤ 4 ≤ 6 ≤ 8 ≤ 10) 이미지 I는 www.acmicpc.net R, C = map(int, input().split()) board = [list(map(int, input().split())) for r in range(R)] T = int(input()) def get_median(arr: list): arr.sort() return arr[4] moveC = C - 2 moveR = R - 2 result = [] for mr in range(moveR): for mc i..

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 풀이 deque 을 이용해 풀었다. 다른 분들은 투포인터 등의 방법을 사용했던데 나는 deque 이 가장 직관적이라 느껴졌다. 우선 가장 단순하게 접근하면 리스트 슬라이싱을 먼저 떠올릴 수 있다. 하지만 입력의 최대 크기가 십만이기 때문에 당연히 시간초과 문제가 터진다. 이정도면 b급 영화의 뻔한 시놉시스보다 더 뻔한 전개가 아닐 수 없다. 클리셰를 극복하기 위해 나는 deque 를 ..

https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 핵심 이 문제를 쉽게 풀 수 있는 핵심은 deque() 자료형의 rotate() 메서드다. rotate(n)는 deque 의 내장함수로, n 이 양수면 우측으로, 음수면 좌측으로 회전한다고 볼 수 있다. 코드 import sys from collections import deque input = sys.stdin.readline n = int(input()) q = deque(e..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A target: continue else: queue.append((num * 2, c..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 사고 과정 1. M 이랑 매칭될 때까지 차례로 더하거나 2. M 보다 커지면 break 3. 어떻게 M 을 맞추느냐는 관심없다. 연속된 숫자의 몇가지 경우가 M 을 맞추는지가 중요. 정답 코드 from sys import stdin N, M = map(int, stdin.readline().split()) arr = list(map(int, stdin.re..

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀지 못한 이유 1. 행렬 곱을 코드로 풀어내지 못함. 2. 재귀를 적절히 활용하지 못함 3. 재귀 탈출 조건 만이라도 알았다면 풀이에 접근할 수 있었음 4. 마지막 조건 (1000 이하) 에 적절히 대처하지 못함. 풀이 이 문제의 핵심은 DP 라고 하는데, 사실 행렬의 곱셈을 코드로 풀어내는 것 역시 핵심이라고 생각한다. 행렬의 곱셈은 이런식으로 진행된다. (1, 3) x (3, 1) 처럼 앞 행렬의 두번째 좌표(3) 와 뒷 행렬의 첫번째 좌표(3) 가 같아야 행렬의 곱이 이..