나만의 개발블로그

풀이 GCD = Greatest Common Divisor = 최대공약수 최대공약수를 구하는 방법은 유클리드 호제법을 기억하고 있어서 빠르게 풀 수 있었다. def GCD(a,b): while b != 0: a,b = b,a%b return a import sys input = sys.stdin.readline for _ in range(int(input())): li = list(map(int,input().rstrip('\n').split())) result = 0 for i in range(1,li[0]+1): for j in range(i+1,li[0]+1): result += GCD(li[i],li[j]) print(result)

풀이 초기엔 재귀 함수를 사용해서 계속해서 값을 찾도록 했었지만 시간초과 이후 DP라고 해서 규칙을 찾고 난 다음 힌트를 얻게 됨. 우선 해당 수의 값은 1,2,3 번 이전의 수가 만들 수 있는 값의 합과 같다는 힌트를 얻음 그런데 여기서 또 해당 문제는 원하는 자릿수를 주기에 더 골치가 아팠다. 그래서 최대로 배열을 만든 다음 계속해서 값을 만들어준 다음 문제를 해결 정답 코드 def startSetting(): li[1][1] = 1 li[2][1] = 1 li[2][2] = 1 li[3][1] = 1 li[3][2] = 2 li[3][3] = 1 import sys input = sys.stdin.readline val = 1000000009 li = [[0]*1001 for _ in range(1..

풀이 deque를 사용하여 pop을 popleft()로 사용해서 풀이 파이썬에서는 switch가 없기에 조건문이 너무 길어서 따로 함수로 빼내어 가독성을 그나마 좋게 하려고 했음 def check(_inVal): if _inVal[0] == 'push': q.append(_inVal[1]) elif _inVal[0] == 'pop': if len(q): print(q.popleft()) else: print(-1) elif _inVal[0] == 'size': print(len(q)) elif _inVal[0] == 'empty': if len(q): print(0) else: print(1) elif _inVal[0] == 'front': if len(q): print(q[0]) else: print(..

풀이 처음 접근한 방법은 문제처럼 2차원 배열의 값을 계속해서 변경한 다음 반복문을 통해 가로, 세로의 합을 출력하는 형식으로 제출했으나... 시간초과 한참을 코드 수정하고 했지만 잘 안되서 서칭을 한 뒤 힌트를 얻게 되었는데 힌트는 2차원 배열의 값을 바꾸는 것보다 합산한 값을 미리 만들어 둔 다음 입력값으로 받아오는 v의 값을 누적합 하여 계산하는 방법. 그래서 미리 result에 배열을 만든 다음 가로, 세로 값을 0,1번째 인덱스에 추가 이후 v의 값을 위치에 맞게 누적합하여 출력해서 해결 정답 코드 import sys input = sys.stdin.readline for _ in range(int(input())): n,m = map(int,input().rstrip('\n').split())..

풀이 처음 접근한 방법은 a,b 가 같아질 때까지 값을 더하는 방식으로 풀었지만 python은 시간초과 pypy는 제출 성공 그래서 문제의 아래를 확인해보니 유클리드 호제법이 있어서 확인한 다음 풀이 최소 공배수를 찾기위해선 최대 공약수를 먼저 계산한 다음 풀이 최대 공약수는 a,b = b, a%b 로 b가 0이 될 때까지 구한 a의 값 최소 공배수는 a*b // 최대공약수 정답 코드 # 유클리드 호제법 import sys input = sys.stdin.readline for _ in range(int(input())): a,b = map(int,input().rstrip('\n').split()) result = a*b if b>a: a,b = b,a while b != 0: a,b = b, a%b ..

풀이 문제에 나와있는 것처럼 값을 만들어 낸 다음 찾는 형식으로 한시간 넘게 가지치기를 하면서 생 고생을 했지만 결국은 2% 시간초과... 이후 힌트를 얻기 위해 구글링을 했을 때 투에-모스 문자열의 점화식이 있다는 걸 확인 해당 점화식을 활용해 푼 결과 간단히 해결... (좀 애바다...) 정답 코드 def tue(n): if n == 0: return 0 elif n%2: return 1-tue(n//2) else: return tue(n//2) print(tue(int(input())-1)) 한참 고생했지만 실패한 코드 아래 코드는 k의 길이 중간 까지만 찾고 해당 idx의 반대 값을 구하는 형식으로 해결하려 했지만 실패... k = int(input()) cnt = 0 result = '0' if..

풀이 우선 s와 t중 긴 문자열을 t에 저장하기 위해 조건문을 추가 이후 단순히 len(t) // len(s)를 한 값 만큼 s를 곱한 결과가 t와 같은지 비교를 했을 때 나와있는 반례는 맞아 제출을 시도했지만 3%에서 실패 그래서 길이가 딱 떨어지지 않는 조건을 생각하였을 때 aa, aaa 를 생각하게 되어 or 뒤에 조건을 붙여 조건분기 하여 문제 해결 import sys input = sys.stdin.readline s, t = input().rstrip('\n'), input().rstrip('\n') result = 0 if len(s)> len(t): tmp = s s = t t = tmp if len(t)//len(s)*s == t or len(t)*s == len(s)*t: print(1..

풀이 처음 접근한 방법은 height를 하나씩 높혀가며 visit를 활용해서 해당 범위를 채우는 풀이로 접근 해당 방법은 알 수 없는 while 루프에 빠져서 인지 7%에서 계속 맴돌게 되는 현상 발생... 이후 다른 접근 방법을 생각 가로등 사이의 거리에 따른 범위, 즉 가로등 간의 거리 차를 구한 다음 해당 거리를 각각의 가로등이 같이 채우는 곳이 없도록 //2를 해주기! 단 차이가 홀 수의 경우 하나의 빈 공간이 생기기에 +1 해주기 그리고 사이의 가로등이 아닌 양 끝에 해당하는 가로등의 경우 시작 가로등의 경우엔 해당 가로등의 위치에서 시작 위치까지 모두 비춰야하기에 if i == 0: result = max(li[i], result) 해당 코드를 적용 마지막 가로등의 경우엔 마지막 거리에서 현재..

풀이 처음에 해당 문제를 이해하지 못했다. 역시 알고리즘은 잘 읽고 이해하는 것이 중요하다는 것을 새삼 느끼게 되었음... 해당 문제는 여러 로프가 있고 해당 로프가 버틸 수 있는 최대 중량이 있는데 예를 들어 아래 예시처럼 2개의 로프가 주어지며 해당 로프는 [10,15] 의 무게를 버틸 수 있는 최대 중량이 있다고 하자. 그렇다면 1개의 로프만 주어질 경우 가질 수 있는 최대 중량은 10보단 15가 더 크기에 15가 최대 중량이 될 테고 2개의 로프가 주어질 경우엔 10과 15가 모두 버틸 수 있는 중량인 10이 2개인 20이 결과 값이 될 테니까 1개의 로프인 10보다 2개의 로프의 값인 20이 더 크기에 20을 최대 중량으로 볼 수 있다. 위의 방법으로 해당 문제를 해결 import sys inp..

풀이 파이썬의 집합의 특성을 활용하여 교집합인 intersection을 사용하여 풀이 여기서 처음에는 문자 하나하나에 rstrip() 메서드를 적용하는 것이 더 많은 시간이 사용될 것 같아 적용하지 않고 제출했는데 이후 적용 후 제출한 시간과의 차이가 어마어마한 것을 보고 역시 입력 값이 많으면 무조건 readline을 사용하긴 해야겠다라고 생각을 다시 하게 됨. import sys input = sys.stdin.readline n,m = map(int,input().split()) no_listen = set([input().rstrip('\n') for _ in range(n)]) no_show = set([input().rstrip('\n') for _ in range(m)]) result = s..