시작이 반

Divide and Conquer에 대한 문제이다. 1. 해당 종이가 일괄된 색이 아니면 4등분을 한다. 2. 4등분된 종이를 다시 검사한다. 1, 2를 일괄된 색일때까지 반복한다. 처음 푼방법 종이를 모든 수에 대해 검사하고 4등분된 종이를 list로 만들어서 다시 재귀를 돌렸다. n = int(input()) graph = [list(map(int, input().split())) for _ in range(n)] blue_count = 0 white_count = 0 def makePaper(graph): if validPaper(graph): return left_top = list() right_top = list() left_bottom = list() right_bottom = list() ..

ex) 10 3 2 9 5 2 queue = 1 2 3 4 5 6 7 8 9 10 왼쪽으로 회전 1번 queue = 2 3 4 5 6 7 8 9 10 1 pop 9 queue = 3 4 5 6 7 8 9 10 1 오른쪽으로 회전 3번 queue = 9 10 1 3 4 5 6 7 8 pop 5 queue = 10 1 3 4 5 6 7 8 오른쪽으로 회전 4번 queue = 5 6 7 8 10 1 3 4 pop 총 횟수 8번 핵심은 오른쪽으로 회전할지 왼쪽으로 회전할지 정하는 것이다. 타겟에 대해 index를 계산하여 판단한다. from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().split()) ..

n까지의 숫자가 주어졌을때 1 ~ n을 스택에 push하고 언제 pop할 것인지 정하면된다. ex) 입력 n = 8 list = 4 3 6 8 7 5 2 1 일때 1 ~ 8까지 스택에 차례로 push를 하면서 스택의 top과 list[j]의 숫자가 같다면 pop을 하고 j 를 1증가시킨다. import sys input = sys.stdin.readline n = int(input()) input_number = list(int(input()) for _ in range(n)) stack = list() result = list() j = 0 for i in range(1, n+1): stack.append(i) result.append('+') while stack and input_number[j] ..

백준의 9012 괄호문제와 비슷한 문제이다. 문자열에서 '('와 '['를 만나면 stack에 쌓아준다. ']'를 만나면 stack의 top을 확인하여 '['일때 pop을 해주고 아니면 no를 출력한다. 마찬가지로 ')'를 만나면 stack의 top을 확인하여 '('일때 pop을 해주고 아닐때 no를 출력한다. 이전에 풀었던 9012의 코드를 이용해서 풀어서 출력이 소문자인 것을 확인 못하고 계속 왜 틀렸는지 생각했다... (시간 날림....) import sys input = sys.stdin.readline while True: string = list(input()) string.pop() if string[0] == '.' and len(string) == 1: break ps = list() sm..

스택에 관련된 문제이다. '('을 확인하면 stack에 쌓고 ')'을 확인하면 stack에서 pop한다. t = int(input()) for _ in range(t): ps = list(input()) stack = list() is_empty = False for i in range(len(ps)): if ps[i] == '(': stack.append(ps[i]) else: if not stack: is_empty = True break else: stack.pop() if not stack and not is_empty: print('YES') else: print('NO')

조합을 구하는 문제이다. 하지만 같은 종류의 옷은 동시에 입을 수 없다. 즉, 같은 종류의 옷들을 묶은다음 해당 종류별로 경우의 수를 곱해주면 된다. 만약 hat headgear sunglasses eyewear turban headgear 가 있다면 headgear : 2개 eyewear : 1개이다. (dict을 이용하면 된다.) 이러면 headgear을 고를 경우의 수 ( 2 + 1 (hat, turban, 아무것도 안고를 경우)) eyewaer을 고를 경우의 수 ( 1 + 1 (sunglasses, 아무것도 안고를 경우)) = 6인데 문제에서 아무것도 안입으면 안되기 때문에 여기서 아무것도 안입는 경우 1을 빼준다. 6-1이 답이다. 처음에는 파이썬의 combination을 사용하여 풀었지만 메모..

nCr = n!/(n-r)!r! 을 이용하면 된다. 하지만 단순 팩토리얼을 이용하여 풀면 n, m 이 20억이될 수 있기 때문에 시간초과, 또는 메모리 초과가 될 것이다. 끝자리가 0이라는 것은 2 와 5의 곱으로 이루어 졌으면 0이 된다. 만약 xxxxx00 이면 2가 2개 5가 2개의 곱으로 이루어 졌다는 것이다. 즉, 2, 5의 쌍을 구하면 0의 갯수를 구할 수 있다. 하지만 이것도 반복문으로 돌리다보니 계속 시간초과가 났다... 도저히 모르겠어서 답을 본 결과... def two_count(n): two = 0 while n != 0: n = n // 2 two += n return two 이런식으로 2의 갯수를 구하는 것을 알 수 있었는데.... 사실 이 식만봤을때 뭔소린지 이해를 못했다... ..

수학적 이론이 필요한 문제이다. M 을 찾아야한다. A = M * a + R B = M * b + R C = M * c + R 여기서 R을 제거하면 A - B = M ( a - b ) B - C = M ( b - c ) 이런 식이 나온다. 즉, M은 A-B, B-C의 공약수이다 즉 최대공약수를 구하면 된다. 최대 공약수를 구하고 해당 수의 1을 제외한 약수를 출력하면된다. 이때 최대 공약수를 구하고 약수를 구할때 반복문을 최대공약수 까지 돌려버리면 숫자 범위가 1,000,000,000까지기 때문에 엄청난 시간이 걸린다. 그래서 공약수를 구할때 18 % 2 = 0 ( 2 = 약수) 18 // 2 = 9 ( 9 = 약수) 이 2개를 한번에 구한다 이러면 반복횟수를 최대공약수의 제곱근 까지 줄일수 있다. 마지..