모두 소인수분해 해준 뒤 각 소인수마다의 지수를 변화시킨다고 생각하면 된다. 곱하기를 만나면 지수가 +1이 되고, 나누기를 만나면 지수가 -1이 된다. 유리수가 되려면 지수가 음수인 소인수가 존재하면 된다. 그래서 소인수 분해를 어떻게 하냐면 -> 에라토스테네스의 체 개념을 이용하면 된다. import sys input = sys.stdin.readline def primelist() : primes = [i for i in range(10**6+1)] for i in range(2, (10**3)+1) : if primes[i] != i : continue for j in range(i*i, 10**6+1, i) : if primes[j] != j : continue primes[j] = i retur..

하나를 놓쳐서 시간이 걸린 문제 먼저 A = a*gcd, B = b*gcd라고 놓고, lcm*gcd = A*B니까 식 전개해서 a*b = lcm//gcd여야 한다는 것까지는 파악을 했고 이 때 합이 최소가 되는 두 수여야 하기에 a와 b가 가장 가까운 숫자여야 한다는 것까지는 알았다. 그래서 a*b의 제곱근 근처에서 탐색을 시작해서 a와 b를 찾아내도록 했는데... a와 b가 서로소여야 한다는 것을 놓쳐서 바로 정답을 맞추지는 못했다. a와 b가 서로소가 아니라면 gcd가 해당 값이 아니게 되기 때문에 짚고 넘어가야 하는 조건이다. 놓치지 말기! import sys input = sys.stdin.readline def calc_gcd(a, b) : if b == 0 : return a return ca..

이름값하는 문제! 처음에는 에라토스테네스의 체를 그대로 이용해서 소수 목록을 만들고, 그 소수 목록의 값을 하나씩 꺼내가며 구하는 방식을 생각했으나... 답은 나오는데 계속 시간 초과가 떴다. 다른 방법은 이렇다. 각 숫자가 어떤 소인수를 가지고 있는지 알 수 있도록 해야 한다. 예를 들면 9는 3을 가지고 있도록! 가장 작은 소인수를 기억해 놓으면 원래의 숫자에서 거슬러 올라가며 소인수를 모두 가져올 수 있다. import sys input = sys.stdin.readline def era(n) : check = [0 for _ in range(n+1)] for i in range(2, n+1) : if check[i] != 0 : continue for j in range(i, n+1, i) : i..

제목 어그로 죄송합니다. 하지만 틀린 말은 아니라서 ... 오늘 알잘딱깔센(사실 엄청 힘들게) 알고리즘 문제를 풀고 잔디 심었음 잔디 구경이나 해볼까 하고 깃허브 들어갔는데 알림이 와 있더라고요 변방의 깃헙에 무슨 알림이 와있나 봤더니... 짜잔! 바야흐로 2년반 전... 아주 어렸을 때 우연히 하게 된 인턴에서... 한번도 해본 적 없던 네트워크 드라이버 개발을 하게되었었는데, (사실 원하던 직무는 아니었으나 인턴 붙은 뒤 철회하기도 어려워서 그냥 맨땅에 헤딩으로 배워보자! 하고 다녔다. 그리고 커리가 꼬여서 살짝 후회하지만...) 아주 작은 회사라 이걸 할 줄 아는 사람도 없었고, 한글로 된 최신 자료도 없어서 마이크로소프트 공식 문서들을 열심히 번역하며 정말 제로베이스부터 공부했던 기억이 난다. 결..

문제 잘 읽기... 에라토스테네스체를 구현해서 소수를 남기는 게 목적이 아니고, 소수도 지워버려야 한다는 것에 유의하기... 코드 depth가 너무 깊어지지 않도록 주의하기... import sys input = sys.stdin.readline def getnumber(n, k) : isPrime = [True for _ in range(n+1)] isPrime[0] = False isPrime[1] = False cnt = 0 for i in range(2, n+1) : if isPrime[i] == False : continue for j in range(i, n+1, i) : if isPrime[j] == False : continue isPrime[j] = False cnt += 1 if cnt..

어렵지 않은 문제였고. import sys from collections import deque input = sys.stdin.readline def josephus(n, k) : circle = deque([i for i in range(1, n+1)]) i = 1 ans = [] while circle : if i % k == 0 : ans.append(circle.popleft()) else : circle.append(circle.popleft()) i += 1 return ans n, k = map(int, input().split()) print("") 위와 같이 풀었는데... deque에 rotate라는 요망한 친구가 있었음. import sys from collections import ..

temp에 곱해주고 ans에 더해주는 개념까진 생각했는데 앞의 괄호 모양을 판단하여 더해준다는 생각을 못해서 고생했다. 괄호 판별은 기본적인 스택 문제와 유사하니 괄호마다 값을 할당해서 계산하는 것만 잘 생각하면 된다. import sys input = sys.stdin.readline paren = [] numbers = [] pair = {')' : '(', ']' : '['} values = {'(' : 2, ')' : 2, ']' : 3, '[' : 3} def calc(arr) : ans = 0 temp = 1 for i in range(len(arr)) : if arr[i] == '(' or arr[i] =='[' : paren.append(arr[i]) temp*=values[arr[i]] ..

역시 골드는 어렵구나 스택을 사용한 문제이며, 이 문제에서 고려해야 하는 것들은 이렇다. 1. 피연산자(문자)는 무조건 바로 집어넣는다. 2. 연산자는 스택에 넣는데, 이 때 우선순위가 높은 연산자는 무조건 상위에 있어야 한다. (그래야 먼저 뽑아서 정답에 집어넣을 수 있다.) 따라서 우선순위가 더 같거나 낮은 연산자를 만나면 그것보다 높은 연산자들은 모두 뽑아져야 한다. - 여기서 우선순위가 같은 연산자를 만날 때도 pop을 해야하는 이유는, 우선순위가 같더라도 새로운 연산자가 더 뒤에 나와야 하기 때문으로, 즉 우선순위가 같아도 이전의 연산자들이 먼저 뽑아져야 하는 것이다. 3. 위와 같은 작업을 위해 괄호의 우선순위는 가장 낮아야 한다. (그래야 위에 다른 연산자를 쌓을 수 있다.) 이 때, ')'..