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 def check_pal (lst): global r if len(lst) <= 1 : r = True else : if lst[ 0 ] == lst[len(lst) - 1 ]: check_pal(lst[ 1 :len(lst) - 1 ]) else : r = False for _ in range( 10 ): test_case = int(input()) total = 100 arr = [list(input()) for _ in range(total)] max_val = 0 for row in arr: for i in range(total): for j in range(i,total + 1 ): r = False check_pal(row[i:j]) if r == True: if max_val < len(row[i:j]): max_val = len(row[i:j]) for col in zip( * arr): for i in range(total): for j in range(i,total + 1 ): r = False check_pal(col[i:j])

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 class Node (): def __init__ (self, data, link): self . data = data self . link = link # 첫 노드에 데이터 삽입하는 알고리즘 def addtoFirst (data): global Head Head = Node(data, Head) # 새로운 노드 생성 # 새로운 노드를 가운데에 삽입하는 알고리즘 def add (pre, data): if pre == None: print ( 'error' ) else : # None이 아닐때만 새 노드를 생성하고 pre . link = Node(data, pre . link) # 데이터 필드를 작성하고 pre 에 삽입하도록 주소 바꿈 # 마지막 노드로 데이터를 삽입하는 알고리즘 def addtoLast (data): global Head if Head == None: # 빈 리스트라면 Head = Node(data, None) # None으로 데이터필드를 채우고 링크를 연결 else : p = Head while p . link != None: # 마지막 노드를 찾을때까지 p = p . link p . link = Node(data, None) # 첫 번째 노드를 삭제하는 알고리즘 def deletetoFirst (): global Head if Head == None:

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 class position (): def __init__ (self, x, y, dist): self . x = x self . y = y self . dist = dist def dfs (x, y, dist = 1 ): global result visit[y][x] = True # print((x, y)) if (x, y) == end: result = 1 for i in range(len(direction)): next_y = y + direction[i][ 0 ] next_x = x + direction[i][ 1 ] if next_y >= 0 and next_y < n and next_x >= 0 and next_x < n: if maze[next_y][next_x] == 0 and visit[next_y][next_x] == False or maze[next_y][next_x] == 3 : dfs(next_x, next_y) def bfs (x, y, dist): global result queue . append(position(x, y, dist)) visit[y][x] = True while queue:

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 class Node (): def __init__ (self, node, cnt = None): self . node = node self . cnt = cnt def dfs (graph, node): global result visit . append(node) # print(node) 방문 노드 출령 if node == g: result = 1 for i in graph[node]: if i not in visit: dfs(graph, i) def bfs (graph, start, cnt): global result visit . append(start) queue = [Node(start, cnt)] while queue: current = queue . pop( 0 ) if current . node == g: result = current . cnt break for i in graph[current . node]: if i not in visit: new_cnt = current . cnt + 1 queue . append(Node(i, new_cnt)) visit . appen

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 class position (): def __init__ (self, x, y, dist): self . x = x self . y = y self . dist = dist def bfs (x, y, dist): global result queue . append(position(x, y, dist)) visit[y][x] = True while queue: current = queue . pop( 0 ) if current . x == end[ 0 ] and current . y == end[ 1 ]: result = current . dist - 2 break for i in range( 4 ): next_y = current . y + direction[i][ 0 ] next_x = current . x + direction[i][ 1 ] next_dist = current . dist + 1 if next_x >= 0 and next_y >= 0 and next_x < width and next_y < height: if visit[next_y][next_x] == False and maze[next_y][next_x] == 0 or

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 for t in range(int(input())): n, m = list(map(int, input() . split())) tmp = list(map(int, input() . split())) cheese = [] for i in range(m): cheese . append([i + 1 , tmp[i]]) # 피자 넘버를 기억하기 위해서 인덱스와 데이터값을 같이 저장 # 초기화 cQ = [] for i in range(n): cQ . append(cheese . pop( 0 )) idx = 0 while True: cQ[idx][ 1 ] = cQ[idx][ 1 ] // 2 if cQ[idx][ 1 ] == 0 : pizza_number = cQ[idx][ 0 ] if len(cheese) > 0 : cQ[idx] = cheese . pop( 0 ) idx = (idx + 1 ) % n if sum(i[ 1 ] for i in cQ) == 0 : break # 피자 치즈가 하나도 안남아있을 때 탈출 print ( "#{} {}" . format(t + 1 , pizza_number)) 5099. [파이썬 S/W 문제해결 기본] 6일차 - 피자 굽기 기본아이디어: 화덕을 확인하는게 1로 고정되어있지만, 알고리즘상에서는 idx가 계속 바뀌면서 확인하고 확인할 때마다 한바퀴 도는 것으로 생각해서 값이 절반으로 줄어든다.

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 def isEmpty (): return front == rear def isFull (): return (rear + 1 ) % len(cQ) == front def enQueue (item): global rear if isFull(): print ( "Queue is Full" ) else : rear = (rear + 1 ) % len(cQ) cQ[rear] = item def deQueue (): global front if isEmpty(): print ( "Queue is Empty" ) else : front = (front + 1 ) % len(cQ) return cQ[front] cQ_size = 4 cQ = [ 0 ] * cQ_size front = rear = 0 enQueue( 'A' ) # front 0 rear 1 [0, 'A', 0, 0] enQueue( 'B' ) # front 0 rear 2 [0, 'A', 'B', 0] print (deQueue()) # 'A' # front 1 rear 2 [0, 'A', 'B', 0] enQueue( 'C' ) # front 1 rear 3 [0, 'A', 'B', 'C'] enQueue( 'D' ) # front 1

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 def check (a, b, card): if card[a] is card[b]: return a if card[a] is 1 : if card[b] is 2 : return b else : return a elif card[a] is 2 : if card[b] is 3 : return b else : return a else : if card[b] is 1 : return b else : return a def rec (st, ed, card): if st is ed: return st l = rec(st, (st + ed) // 2 , card) r = rec((st + ed) // 2 + 1 , ed, card) return check(l, r, card) def main (): T = int(input()) for tc in range( 1 , T + 1 ): N = int(input()) card = list(map(int, input() . split())) print ( "#{} {}" . format(tc, rec( 0 , N - 1 , card) + 1 )) main() 4880. [파이썬 S/W 문제해결 기본] 5일차 - 토너

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 # BackTracking : Stack to store data, Recursion def nqueen (result, N): global count if len(result) == N: # 정답 배열(result)의 길이가 N과 같아지면 result 을 프린트한다. count += 1 print (count, result) return 0 candidate = list(range(N)) # 0 부터 N-1 까지로 구성된 후보군(cadidate) 배열을 만든다. for i in range(len(result)): # 처음엔 [i] 만큼만. 이후 점점 한개씩 늘어난다. # 제외할 것 제외하고 이후 24번 줄에서 후보군 체크 if result[i] in candidate: # 같은 열에 놓이는지 체크 candidate . remove(result[i]) # 같은 열에 놓이면 후보군에서 제외 distance = len(result) - i if result[i] + distance in candidate: # 같은 대각선 상에 놓이는지 체크 candidate . remove(result[i] + distance) # 같은 대각선 상에 놓이면 후보군에서 제외 if result[i] - distance in candidate: # 같

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 def backtrack (a, k, input, arr, result): global MAXCANDIDATES global min_value t = 0 c = [ 0 ] * MAXCANDIDATES if k == input: # write your code for i in range( 1 , k + 1 ): t += arr[i - 1 ][a[i] - 1 ] if t > min_value: break elif t <= min_value and i == k: min_value = t result . append(min_value) else : k += 1 ncandidates = construct_candidates(a,k,input,c) for i in range(ncandidates): a[k] = c[i] backtrack(a, k, input, arr, result) #후보군 구하는 함수 def construct_candidates (a, k, input, c): in_perm = [False] * NMAX for i in range( 1 ,k): in_perm[a[i]] = True ncandidates = 0 for

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 oper = [ '+' , '-' , '*' , '/' ] for t in range(int(input())): s = list(input() . split()) stack = list() for i in s: if i in oper: try : a = stack . pop( - 1 ) b = stack . pop( - 1 ) calc = eval(b + i + a) stack . append(str(calc)) except : print ( "#{} error" . format(t + 1 )) break else : if i == '.' : print ( "#{} {}" . format(t + 1 , stack[ 0 ])) else : stack . append(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 def backtrack (a, k, input): global MAXCANDIDATES c = [ 0 ] * MAXCANDIDATES if k == input: process_solution(a,k) #답이면 원하는 작업한다. else : k += 1 ncandidates = construct_candidates(a,k,input,c) for i in range(ncandidates): a[k] = c[i] backtrack(a, k, input) def process_solution (a, k): print ( "(" , end = "" ) for i in range(k + 1 ): if a[i]: print (i, end = " " ) print ( ")" ) #후보군 구하는 함수 def construct_candidates (a, k, input, c): c[ 0 ] = True c[ 1 ] = False return 2 #Main MAXCANDIDATES = 100 NMAX = 100 a = [ 0 ] * NMAX backtrack(a, 0 , 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 s = '(6+5*(2-8)/2)' stack = list() result = list() icp = { '(' : 3 , '+' : 1 , '-' : 1 , '*' : 2 , '/' : 2 } #??? isp = { '(' : 0 , '+' : 1 , '-' : 1 , '*' : 2 , '/' : 2 } for i in s: if i == '(' : stack . append(i) elif i in isp . keys(): #isp check if isp[i] > isp[stack[len(stack) - 1 ]]: stack . append(i) else : while True: c = stack . pop( - 1 ) result . append(c) if isp[i] > isp[stack[len(stack) - 1 ]]: stack . append(i) break elif i == ')' : while stack[len(stack) - 1 ] != '(' : c = stack . pop( - 1 ) result . append(c) stack

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 def dfs (graph, start): visited, stack = [], [start] while stack: vertex = stack . pop() if vertex not in visited: visited . append(vertex) stack += graph[vertex] - set(visited) return visited for t in range(int(input())): graph = dict() v, e = list(map(int, input() . split())) # Graph initialize for i in range(v): graph[str(i + 1 )] = set() # Links allocated by input value for _ in range(e): key, val = input() . split() graph[key] . add(val) s, g = input() . split() vtd = dfs(graph, s) if g in vtd: result = 1 else : result = 0 print ( "#{} {}" . format(t + 1 , result)) 참고문제: SW Expert Academy 4871번 문제

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 # 보이어 무어 알고리즘 for t in range(int(input())): pattern = input() text = input() pivot = len(pattern) - 1 skip_array = list(pattern) skip_array . reverse() result = 0 while result != 1 and pivot < len(text): if pattern[len(pattern) - 1 ] != text[pivot]: if text[pivot] in skip_array: nums = skip_array . index(text[pivot]) pivot += nums else : pivot += len(pattern) else : for i, j in zip(range(pivot, pivot - len(pattern), - 1 ), skip_array): if text[i] == j: result = 1 else : result = 0 pivot = i break print ( "#{} {}" . format(t + 1 , result)) 참고문제: SW Expert Academy 4864번 문제