23/04/06

backjoon_1260.py

'''
백준 1260. bfs, dfs 
'''
from collections import defaultdict
# 양방향 그래프 만들기
n, m, v = map(int, input().split())
graph = defaultdict(list)
for i in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)


def bfs():
    q = [v]
    visit = []
    while q:
        node = q.pop(0)
        if node not in visit:
            print(node, end = " ")
        graph[node].sort()
        for i in graph[node]:
            if i not in visit:
                q.append(i)
        visit.append(node)

visit2 = []
def dfs(graph, node):
    global visit2
    visit2.append(node)
    print(node, end = " ")
    graph[node].sort()
    for i in graph[node]:
        if i not in visit2:
            dfs(graph, i)

dfs(graph, v)
print()
bfs()

backjoon_2606.py

'''
백준 2606번 Union Find 문제
'''
# make graph
n = int(input())
m = int(input())
graph = []
for i in range(m):
    n1, n2 = map(int, input().split())
    graph.append((n1, n2))
    

# union find
parent = [i for i in range(n+1)]
rank = [1] * (n+1)
def find(s1):
    res = s1
    while res != parent[res]:
        parent[res] = parent[parent[res]]
        res = parent[res]
    return res

def union(n1, n2):
    p1, p2 = find(n1), find(n2)

    if p1 == p2:
        return 0
    if rank[p2] > rank[p1]:
        parent[p1] = p2
        rank[p2] += rank[p1]
    else:
        parent[p2] = p1
        rank[p1] += rank[p2]
    return 1
for n1, n2 in graph:
    union(n1, n2)

print(rank[find(1)] - 1)

combinationSum.py

def combinationSum(self, c: List[int], target: int) -> List[List[int]]:
    '''
    Leetcode 39. Combination Sum
    dfs로 목표값을 만들 수 있는 경우의 수 구하기
    '''
    res = []

    def dfs(i, cur, total):
        # target을 만들면 res에 추가하고 리턴
        if total == target:
            res.append(cur.copy())
            return
        # target을 못 만들면 리턴
        if i >= len(c) or total > target:
            return
        # 초과하기 전까지 추가하고 깊이 우선탐색
        cur.append(c[i])
        dfs(i, cur, total + c[i])
        # 한개 꺼내고 높이 한칸 높여서 다시 깊이 우선탐색
        k = cur.pop()
        dfs(i + 1, cur, total)
    dfs(0, [], 0)

    return res

dailyTemperatures.py

def dailyTemperatures(T) -> List[int]:
    '''
    Leetcode 739. Daily Temperatures
    stack
    '''
    stack = [] # 온도, 인덱스
    res = [0 for _ in range(len(T))]

    for i, t in enumerate(T):
        # 스택의 맨 위의 값보다 작아질 때 까지 pop
        while stack and t > stack[-1][0]:
            t2, i2 = stack.pop()
            res[i2] = (i - i2) 

        stack.append([t, i])
    return res

evalRPN.py

def evalRPN(tokens) -> int:
    '''
    Leetcode 150. Evaluate Reverse Polish Notation
    stack을 활용한 사칙연산문제
    '''
    stack = []
    for c in tokens:
        if c == '+':
            stack.append(stack.pop() + stack.pop())
        elif c == '-':
            a, b = stack.pop(), stack.pop()
            stack.append(b-a)
        elif c == '*':
            stack.append(stack.pop() * stack.pop())
        elif c == '/':
            a, b = stack.pop(), stack.pop()
            stack.append(int(b/a))
        else:
            stack.append(int(c))
    return stack[-1]

evalRPN(["2","1","+","3","*"])

generateParen.py

def generateParen(n):
    '''
    Leetcode 22. Generate Parentheses
    stack, backtracking을 활용하여 쌍의 개수 가 주어지면 만들 수 있는 괄호의 경우의 수 반환
    '''
    stack = []
    res = []

    def backtrack(openN, closedN):
        print(f'backtrack({openN}, {closedN}) {stack}')
        if openN == closedN == n:
            res.append("".join(stack))
            return
        if openN < n:
            stack.append("(")
            backtrack(openN + 1, closedN)
            stack.pop()
        if closedN < openN:
            stack.append(")")
            backtrack(openN, closedN + 1)
            stack.pop()
    backtrack(0, 0)
    return res
    
print(generateParen(3))

isValidParen.py

def isValidParen(s):
    '''
    Leetcode 20. Valid Parentheses
    stack을 활용하여 올바른 괄호 찾는 문
    '''
    stack = []
    closeToOpen = {")":"(", "]":"[", "}":"{"}
    for c in s:
        if c in closeToOpen:
            if stack and stack[-1] == closeToOpen[c]:
                stack.pop()
            else:
                return False
        else:
            stack.append(c)
    return True if len(stack) == 0 else False

isValidParen("()[]{}")

longestCommonSubsequence.py

def longestCommonSubsequence(text1, text2) -> int:
    '''
    Leetcode 1143. Longest Common Subsequence
    DP를 활용한 문제/ len(text1)+1 개의 열과 len(text2) + 2 개의 행을 가진 표를 그려 경우의 수를 셈
    '''
    n, m = len(text1), len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[j-1] == text2[i-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[-1][-1]

subsets.py

def subsets(nums):
    '''
    Leetcode 78. Subsets
    backtracking으로 배열이 주어지면 만들수 있는 조합 반환
    '''
    res = []
    subset = []

    def dfs(i):
        # 빠져나옴
        if i >= len(nums):
            res.append(subset.copy())
            return
        # 추가할때
        subset.append(nums[i])
        dfs(i+1)

        # 추가안할때
        subset.pop()
        dfs(i+1)
    dfs(0)

    return res
print(dfs([1, 2, 3]) # [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

uniquePaths.py

def uniquePaths(m, n) -> int:
    '''
    Leetcode 62. Unique Paths
    DP를 활용한 문제 표를 그려서 뒤에서 부터 경우의 수를 더해줌 아래와 오른쪽의 경우의 수를 더함
    '''
    row = [1] * n
    for i in range(m-1):
        nRow = [1] * n
        for j in range(n-2, -1, -1):
            nRow[j] = nRow[j+1] + row[j]
        row = nRow
    return row[0]