Study and Share IT

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 # def bfs(n, k): # global MAX_VAL # time = 0 # queue = deque() # queue.append((n,time)) # check[n] = True # while queue: # curr_p, curr_t = queue.popleft() # for d in [-1, +1, curr_p]: # next_p = curr_p + d # if not check[next_p] and 0<=next_p<=MAX_VAL: # if next_p == k: # print(curr_t+1) # return # queue.append((next_p, curr_t+1)) # check.append(next_p) from collections import deque MAX_VAL = 100000 check = [False] * (MAX_VAL + 1 ) dist = [ - 1 ] * (MAX_VAL + 1 ) n, k = map(int, input() . split()) check[n] = True dist[n] = 0 q = deque() q . append(n) while q: curr_p = q . popleft() for next_p in [curr_p - 1 , curr_p + 1 , 2 * curr_p]: if 0 <= n...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 from collections import deque direction = (( - 1 , 0 ), ( 1 , 0 ), ( 0 , - 1 ), ( 0 , 1 )) def bfs (q): global n, m while q: curr = q . popleft() for d in direction: next_y = curr[ 0 ] + d[ 0 ] next_x = curr[ 1 ] + d[ 1 ] if 0 <= next_y < n and 0 <= next_x < m and visit[next_y][next_x] == 0 : visit[next_y][next_x] = curr[ 2 ] + 1 q . append((next_y, next_x, curr[ 2 ] + 1 )) m, n = map(int, input() . split()) box = [list(map(int, input() . split())) for _ in range(n)] visit = box[:] queue = deque() for i in range(n): for j in range(m): if box[i][j] == 1 : queue . append((i, j, 1 )) bfs(queue) max_val = cnt_zero = 0 for v in visit: cn...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 direction = (( - 1 , 0 ), ( 1 , 0 ), ( 0 , - 1 ), ( 0 , 1 )) def sol (st_y, st_x): global w, h cnt = 0 for d in direction: next_y = st_y + d[ 0 ] next_x = st_x + d[ 1 ] if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w or MAP[next_y][next_x] == 0 : cnt += 1 return cnt while True: w, h = map(int, input() . split()) if (w, h) == ( 0 , 0 ): break MAP = [list(map(int, input() . split())) for _ in range(h)] answer = 0 for i in range(h): for j in range(w): if MAP[i][j] == 0 : continue answer += sol(i,j) print (answer) 아이디어는 단순하다. 모든 좌표를 순회하면서 주변이 땅으로 연결되지 않을때 cnt를 하나씩 증가시킨다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 direction = (( - 1 , 0 ), ( 1 , 0 ), ( 0 , - 1 ), ( 0 , 1 )) def bfs (y, x, num): global n check[y][x] = num queue = [(y,x)] cnt = 1 while queue: curr_y, curr_x = queue . pop( 0 ) for d in direction: next_y = curr_y + d[ 0 ] next_x = curr_x + d[ 1 ] if 0 <= next_y < n and 0 <= next_x < n: if MAP[next_y][next_x] == 1 and check[next_y][next_x] == 0 : check[next_y][next_x] = num queue . append((next_y, next_x)) cnt += 1 return cnt n = int(input()) MAP = [list(map(int, input())) for _ in range(n)] check = [[ 0 ] * n for _ in range(n)] number = 0 result = [] for i in range(n): for j in range(n): if not check[i][...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 def bfs (): global n, m, r, c, l, answer, time check[r][c] = True answer += 1 time += 1 queue = [(r, c, time)] while queue: curr = queue . pop( 0 ) curr_time = curr[ 2 ] if curr_time == l: break for diff in dic[MAP[curr[ 0 ]][curr[ 1 ]]]: new_y = curr[ 0 ] + diff[ 0 ] new_x = curr[ 1 ] + diff[ 1 ] new_time = curr[ 2 ] + 1 if 0 <= new_y < n and 0 <= new_x < m and MAP[new_y][new_x] != 0 : if isConnectable(curr[ 0 ], curr[ 1 ], new_y, new_x): if not check[new_y][new_x]: queue . append((new_y, new_x, new_time)) check[new_y][new_x] = True answer += 1 def ...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 from collections import Counter as ctr n, m = map(int, input() . split()) series = list(map(int, input() . split())) series = list(ctr(series) . items()) series . sort() n = len(series) nums, cnt = map(list, zip( * series)) answer = [ 0 ] * m result = [] # 중복불허, 중복된 N 수열[9,7,9,1] 에서 M 출력, 비내림차순 def recur6 (n, m, idx): if idx == m: print ( ' ' . join(map(str, answer))) return for i in range(n): if idx > 0 : if answer[idx - 1 ] <= nums[i]: answ...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 def GCD (a,b): if b == 0 : return a else : return GCD(b, a % b) def GCD2 (a,b,c): return GCD(GCD(a,b),c) def GCD3 (a,b,c,d): return GCD(GCD(GCD(a,b),c),d) #최소공배수 = (A*B) / GCD def LCM (a,b): return (a * b) / GCD(a,b) def LCM2 (a,b,c): return LCM(LCM(a,b),c) gcd = GCD( 24 , 36 ) gcd2 = GCD2( 24 , 36 , 42 ) gcd3 = GCD3( 24 , 36 , 42 , 6 ) print (gcd) # 12 print (gcd2) # 6 print (gcd3) # 6 lcm = LCM( 24 , 36 ) lcm2 = LCM2( 24 , 36 , 42 ) print (lcm) # 72 print (lcm2) # 504

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 c = 11 b = 2 c_v = 1 t = 0 brown = [b] answer = 0 loop = True while loop: if c == b: answer = t break else : c += c_v c_v += 1 t += 1 q = brown[:] while q: curr = q . pop( 0 ) brown . pop( 0 ) for i in [curr - 1 , curr + 1 , 2 * curr]: if i == c: answer = t loop = False q . clear() break elif i < c: brown . append(i) elif i > c: break if len(brown) == 0 : answer = - 1 break print (answer)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 a = [False, False] + [True] * n prime = [] for i in range(n + 1 ): if a[i]: prime . append(i) for j in range( 2 * i, n + 1 , i): a[j] = False def recur (r): global result, num stack . append(r) if len(stack) == 3 : sss = sorted(stack) if sum(sss) == num and sss not in result: result . append(sss) else : for i in lst: if len(stack) < 3 : # 중복을 허용하기 위한 조건문 삽입. 없으면 stack overflow recur(i) stack . pop() for t in range(int(input())): num = int(input()) for k in range(len(prime)): if prime[k] >= num: lst = prime[:k] break result = [] for j in lst: stack = [] r...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 def recur (idx): check[idx] = 1 tmp . append(n[idx]) if len(tmp) == 3 : a = sorted(tmp) if sum(a) not in result: result . append(sum(a)) else : for i in range( 7 ): if check[i] == 0 : recur(i) tmp . pop() check[i] = 0 # def subset(): # for i in range(1<<7): # tmp2 = 0 # cnt = 0 # for j in range(7): # if i & (1<<j): # tmp2 += n[j] # cnt += 1 # if tmp2 not in result and cnt == 3: # result.append(tmp2) for t in range(int(input())): n = list(map(int, input() . split())) result = [] for i in range(len(n)): tmp = [] check = [ 0 ] * 7 recur(i) # subset() res...

1 2 3 4 5 6 7 8 9 10 11 def getSubset (lst): n = len(lst) for i in range( 1 << n): # i: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111 for j in range(n): # j: 0001, 0010, 0100 t_f = i & ( 1 << j) if t_f: # t_f 가 0 이 아닌 경우에는 출력. print (lst[j], end = ' ' ) # 0, 1, 2 print () getSubset([ 0 , 1 , 2 ])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 # 1번) 기본 아이디어: N보다 작은 수로 나누어본다. # def getPrime1(num): # result = 'true' # for i in range(2,num): # if num % i == 0: # result = 'false' # break # return result # st = 1 # ed = 10**6 # prime = [] # for i in range(st+1, ed+1): # if getPrime1(i) == 'true': # prime.append(i) # print(' '.join(str(e) for e in prime)) # 2번) 에라토스테네스의 체 기본. N을 2부터 sqrt(N)까지 나누어본다. # def getPrime2(num): # result = 'true' # for i in range(2,int(num**0.5)+1): # if num % i == 0: # result = 'false' # break # return result # st = 1 # ed = 10**6 # prime = [] # for i in range(st+1, ed+1): # if getPrime2(i) == 'true': # prime.append(i) # print(' '.join(str(e) for e in prime)) # 3번) 에라토스테네스의...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 class DoubleLinkedList (): class Node (): def __init__ (self, data, prev = None, next = None): self . prev = prev self . data = data self . next = next def __init__ (self): self . head = self . Node( '머리' , None, None) self . tail = self . Node( '꼬리' , self . head, None) self . head . next = self . tail self . size = 0 def getSize (self): return self . size def isEmpty (self): return self . size == 0 def insertBefore (self, preNode, data): t = preNode . prev n = self . Node(data, t, preNode) preNode . prev = n t . next = n s...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 def recur (): global n if len(candidate) == n: l = candidate[:] result . append(l) else : for i in [ 0 , 1 ]: candidate . append(i) recur() candidate . pop() def sol (): global n, k, answer for i in range( 1 << n): tmp = 0 for j in range(n): if i & ( 1 << j): tmp += a[j] print (a[j], end = " " ) print () if tmp == k: answer += 1 def convert (): global n for i in result: tmp = [] for j in range(n): c = a[j] * i[j] tmp . append(c) aa . append(tmp) for t...