SWEA - D4~D6(1)

• Algorithm 문제 풀이 (Tree)
• SWEA-노드의 합

class BinaryTree:
    def __init__(self, n):
        self.n = n
        self.node_list = [0] *(n+1)
    def insert(self, num1, num2):
        self.node_list[num1] = num2
    def leaf(self, node):
        if node * 2 > n:
            self.sum += self.node_list[node]
        else:
            self.leaf(node * 2)
            if node * 2 != n:
                self.leaf(node * 2 + 1)
    def result(self, l):
        self.sum = 0
        self.leaf(l)
        return self.sum

for t in range(int(input())):
    n, m, l = map(int, input().split())
    bin_tree = BinaryTree(n)
    for i in range(m):
        num1, num2 = map(int, input().split())
        bin_tree.insert(num1, num2)
    print(f"#{t+1} {bin_tree.result(l)}")

• subtree

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, cnt):
        self.node_list = [None]
        for i in range(e+1):
            self.node_list.append(Node(i))

    def insert(self, node, data):
        if self.node_list[node].left == None:
            self.node_list[node].left = self.node_list[data]
        else:
            self.node_list[node].right = self.node_list[data]

    def count(self, node):
        self.cnt += 1
        if node.left != None:
            self.count(node.left)
        elif node.right != None:
            self.count(node.right)
    def result(self, num):
        self.cnt = 0
        self.count(self.node_list[num])
        return self.cnt

for t in range(int(input())):
    e, n = map(int, input().split())
    numbers = list(map(int, input().split()))
    bin_tree = BinaryTree(e)
    for i in range(e):
        bin_tree.insert(numbers[2*i], numbers[2*i+1])
    print(f"#{t+1} {bin_tree.result(n)}")

• SWEA. 5185 [파이썬 S/W 문제해결 구현] 1일차 - 이진수

for t in range(int(input())):
    n, num = map(str, input().split())
    print(f'#{t+1}',end=" ")
    for a in num:
        b = '0x'+ a.lower()
        hex_num = int(a, 16) # 16진수를 10진수로
        print("{0:b}".format(hex_num).zfill(4), end="") # 10진수를 2진수로 바꾸면서 (4자리씩)
    print()

• [파이썬 S/W 문제해결 구현] 1일차 - 이진수2

for t in range(int(input())):
    n = float(input())
    result = ''
    cnt = 0
    while True:
        a = n * 2
        result += str(int(a))
        n = a - int(a)
        cnt += 1
        if n == 0.0:
            break
        if cnt > 13:
            break
    if cnt > 13:
        print(f"#{t+1} overflow")
    else:
        print(f"#{t+1} {result}")

• SWEA 문제 풀이

# 최소합
dx, dy = [0,1], [1,0]
def dfs(x,y):
    global min_num, result
    visit[x][y] = 1
    if  result < min_num:
        return
    if x == n-1 and y == n-1:
        result = min_num
        return
    for i in range(2):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
            min_num += a[nx][ny]
            dfs(nx,ny)
            visit[nx][ny] = 0
            min_num -= a[nx][ny]


for t in range(int(input())):
    n = int(input())
    a = [list(map(int, input().split()))for _ in range(n)]
    visit = [[0 for _ in range(n)]for _ in range(n)]
    min_num = a[0][0]
    result = 10000000
    dfs(0,0)
    print(f"#{t+1} {result}")

# 전자카트
def sol(a,b,c):
    if b == n-1:
        c += arr[a][0]
        result.append(c)
    else:
        for i in range(1,n):
            if not visit[i]:
                c += arr[a][i]
                visit[i]=1
                sol(i,b+1,c)
                visit[i]=0
                c -= arr[a][i]


for t in range(int(input())):
    n = int(input())
    arr = [list(map(int, input().split()))for _ in range(n)]
    visit = [0]*n
    result = []
    sol(0,0,0)
    print(f"#{t+1} {min(result)}")

# 컨테이너 운반
for t in range(int(input())):
    n,m = map(int, input().split())
    weight = list(map(int, input().split()))
    truck = list(map(int, input().split()))
    result = 0
    for i in range(m):
        a = 0
        for j in weight:
            if truck[i] >= j >= a:
                a = j
        if a != 0:
            weight.remove(a)
        result += a
    print(f"#{t+1} {result}")

# 화물 도크
for t in range(int(input())):
    n = int(input())
    a = [list(map(int, input().split()))for _ in range(n)]
    for i in range(n):
        for j in range(i, n):
            if a[i][1] > a[j][1]:
                a[i], a[j] = a[j], a[i]
    result = [a[0]]
    visit = [0]*n
    visit[0] = 1
    while True:
        for i in range(n):
            if result[-1][-1] > a[i][0]:
                visit[i] = 1
        if not 0 in visit:
            break
        idx = 0
        max_value = 100000000
        for i in range(n):
            if visit[i] == 0 and result[-1][-1] <= a[i][0] and a[i][1] < max_value:
                idx = i
                max_value = a[i][0]
        result.append(a[idx])
    print(f"#{t+1} {len(result)}")

# 베이비진
for t in range(int(input())):
    a = list(map(int, input().split()))
    cnt = 0
    flag = False
    for i in range(6, 13, 2):
        result = []
        for j in range(2):
            deck = [a[k]for k in range(j, i, 2)]
            cnt_list = [0]*12
            for m in range(len(deck)):
                cnt_list[deck[m]] += 1
            n = 0
            tri = Run = 0
            while n < 10:
                if cnt_list[n] >= 3:
                    cnt_list[n] -= 3
                    tri += 1
                    continue
                if cnt_list[n] >= 1 and cnt_list[n+1] >= 1 and cnt_list[n+2] >= 1:
                    cnt_list[n] -= 1
                    cnt_list[n+1] -= 1
                    cnt_list[n+2] -= 1
                    Run += 1
                    continue
                n += 1
            cnt += 1

            if tri > 0 or Run > 0:
                result.append(1)
            else:
                result.append(0)

        if result[0] < result[1]:
            flag = True
            print(f"#{t+1} 2")
            break
        elif result[0] > result[1] or ((result[0] == 1 and result[1] == 1) or (result[0] == 2 and result[1] == 2)):
            flag = True
            print(f"#{t+1} 1")
            break
    if flag:
        continue
    else:
        print(f"#{t+1} 0")

1. 병합정렬
2. def m_sort(a): if len(a) <= 1: return a center = len(a) // 2 right = m_sort(a[center:]) left = m_sort(a[:center]) return merge(left, right) def merge(left,right): global cnt n_right = len(right) n_left = len(left) i = 0 i_right = 0 i_left = 0 result = [0] * (n_right+n_left) if left[-1] > right[-1]: cnt += 1 while i_right != n_right and i_left != n_left: if right[i_right] >= left[i_left]: result[i] += left[i_left] i += 1 i_left += 1 else: result[i] += right[i_right] i += 1 i_right += 1 if i_left != n_left: while i_left != n_left: result[i] += left[i_left] i += 1 i_left += 1 if i_right != n_right: while i_right != n_right: result[i] += right[i_right] i += 1 i_right += 1 return result for t in range(int(input())): n = int(input()) a = list(map(int, input().split())) cnt = 0 result_ = m_sort(a) print(f"#{t+1} {result_[n//2]} {cnt}")
3. 퀵 정렬

주석 처리 된 방법을 사용하면 10개중 9개 맞고 런타임에러

1.  
2. # def quick_sort(a): # if len(a) <= 1: # return a # pivot = a[len(a)//2] # left, right, equal =[],[],[] # for i in a: # if i < pivot: # left.append(i) # elif i > pivot: # right.append(i) # else: # equal.append(i) # return quick_sort(left) + equal + quick_sort(right) def quick_sort(a, l, r): if l < r: p = partition(a, l, r) quick_sort(a, l, p - 1) quick_sort(a, p + 1, r) def partition(a, l, r): pivot = (l + r) // 2 while l < r : while(a[l] < a[pivot] and l < r): l += 1 while(a[r] >= a[pivot] and l < r): r -= 1 if l < r: if l == pivot: pivot = r a[l], a[r] = a[r], a[l] A[pivot], a[r] = a[r], a[pivot] return r for t in range(int(input())): n = int(input()) a = list(map(int, input().split())) quick_sort(a, 0, n-1) print(f"#{t+1} {a[n//2]}")
3. 이진 탐색
4. for t in range(int(input())): n, m = map(int, input().split()) arr1 = sorted(list(map(int, input().split()))) arr2 = list(map(int, input().split())) cnt = 0 for i in arr2: a = 0 b = n-1 check = 0 while a <= b: c = (a+b)//2 if i >= arr1[c]: if i == arr1[c]: cnt+=1 break a = c + 1 if check == 1: break check = 1 elif i < arr1[c]: b = c - 1 if check == 2: break check = 2 print(f"#{t+1} {cnt}")