합니다, 개발공부📝 합니다, 개발공부📝

처음부터 모두 조회하면서 사각형 넓이를 계산하는 완전탐색 실행시 시간초과가 발생하는 문제이다. 이 부분을 해결하기 위해서는 왼쪽과 오른쪽 부분을 나눠서 진행하는데 (분할 정렬처럼) 왼쪽부분에서 가장 큰 사각형과 오른쪽부분에서 가장 큰 사각형 넓이, 가운데에서 가운데 두개의 영역(넓이2 * 둘중에 낮은 높이), 가운데영역을 포함하여 양쪽으로 넓어지면서 계산한 사각형 중에 가장 큰 사각형을 비교하여 가장 큰 넓이를 반환해주여야 한다. c = int(input()) def max_sqare(left, right, fence): # 기저 사레 : 같은 값이면 가로 1 * 높이가 최대 직사각형 if left == right : return fence[left] # 가운데를 중심으로 나아간다 mid = (left ..

이미 압축되어 출력된 부분을 다시 원래 모양대로 풀고 나서 뒤집고 다시 압축하려고 하면 초과가 발생하는 문제이다. 이미 압축되어있는 버전에서 부분 별로 위와 아래만 바꿔주도록 적용해야 한다. c = int(input()) def reverse(s, idx): if s[idx] == 'w' or s[idx] =='b' : return s[idx] # x로 시작한다는 의미이므로 한칸 앞으로 idx +=1 upperLeft = reverse(s, idx) idx += len(upperLeft) upperRight = reverse(s, idx) idx += len(upperRight) lowerLeft = reverse(s, idx) idx += len(lowerLeft) lowerRight = reverse..

완전탐색으로 시계를 모두 12시로 맞추는 모든 경우의 수를 구하고 그 중 스위치를 누른 최소의 갯수를 구하려고 했으나 시간초과가 발생하였다. import math inf = math.inf switches = [ [0, 1, 2], [3, 7, 9, 11], [4, 10, 14, 15], [0, 4, 5, 6, 7], [6, 7, 8, 10, 12], [0, 2, 14, 15], [3, 14, 15], [4, 5, 7, 14, 15], [1, 2, 3, 4, 5], [3, 4, 5, 9, 13] ] def is_aligned_clock(clock) : for time in clock : if time != 12 : return False return True def push_switch(clock, sw..

이 문제는 경우의 수를 모두 구하는 문제로 완전탐색을 이용한다. 여기서 주의할 점은 중복되는 경우의 수를 제외하기 위해서 맨 위쪽 부터 탐색하여 채워지지 않은 부분을 찾아내는 것이다. 제일 먼저 coverType을 만드는데 [dy][dx]타입으로 세 점을 작성하였으며 나중에 적용할 때는 행, 열의 순서에 맞춰 board[y + dy][x + dx]를 적용해야 하는 점에 유의하자. c = int(input()) coverType = [ [[0,0], [0,1], [1, 0]], [[0,0], [0, 1], [1, 1]], [[0,0], [1, 0], [1,1]], [[0,0], [1,0], [1,-1]] ] def isCoverable(x, y, type, board): for dy, dx in type:..

탐색가능한 모든 조합의 수를 계산 하는 문제로 완전탐색 을 이용해서 문제를 해결할 수 있었다. 여기서 중요한 것은 중복으로 계산되는 것을 제외하여야 한다는 것이다. 즉 (1,0)과 (0, 1)은 서로 같은 사람끼리 짝을 이루었으므로 같은 경우라고 인지하여야 한다. 이 부분을 해결하기 위해서 숫자 순서대로 먼저 오는 답 하나만 계산할 도록 first 인자를 이용해서 선택되지 않은 학생중에서 가장 번호가 빠른 학생의 짝을 찾도록 하였다. c = int(input()) def countPair(): cnt = 0 first = -1 for i in range(n): if not visited[i]: first = i break if first == -1 : return 1 for i in range(first..