본문 바로가기

Algorithm/BOJ133

[백준] 4195번 - 친구 네트워크 (파이썬) # 친구 네트워크 import sys input = sys.stdin.readline T = int(input()) def find_parent(x): global result if x != parent[x]: parent[x] = find_parent(parent[x]) return parent[x] def union(a, b): global result x = find_parent(arr[a]) y = find_parent(arr[b]) if x y: parent[x] = y num[y] += num[x] for _ in range(T): N = int(input()) arr = dict() n = 0 parent = [.. 2022. 1. 29.
[백준] 9935번 - 문자열 폭발 (파이썬) # 문자열 폭발 str = input().strip() bomb = list(input().strip()) result = [] for i in range(len(str)): result.append(str[i]) if result[-len(bomb):] == bomb: for _ in range(len(bomb)): result.pop() if result: print(*result, sep='') else: print('FRULA') 자료구조 (스택) 1. result에 문자열을 하나씩 넣는다 2. 만약 result의 뒤에서 bomb길이 만큼의 문자열이 bomb와 같으면 bomb의 길이만큼 pop을 해준다. 3. result가 빈 문자열이면 'FRULA'를 아니면 result를 출력 기존의 파이썬 문.. 2022. 1. 28.
[백준] 1918번 - 후위 표기식 (파이썬) # 후위 표기식 from collections import deque from re import L notAlpha = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0, ')': 0} alpha = deque() sign = [] def popAll(): while alpha: result.append(alpha.popleft()) x = sign.pop() while sign: temp = sign.pop() if x == ')' and temp == '(': break if temp == '(': sign.append(temp) break if notAlpha[x] 1 and sign[-1] != '(' and notAlpha[sign[-1]] 2022. 1. 28.
[백준] 2146번 - 다리 만들기 (파이썬) # 다리 만들기 from collections import deque import sys input = sys.stdin.readline MAX = sys.maxsize N = int(input()) arr = [] sea = [] for i in range(N): arr.append(list(map(int, input().split()))) for j in range(N): if arr[i][j] == 0: sea.append((i, j)) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] result = MAX def bfs(a, b): global result q = deque() q.append((a, b)) visited = [[0] * N for _ in range(N)] w.. 2022. 1. 28.
[백준] 1339번 - 단어 수학 (파이썬) # 단어 수학 from collections import deque N = int(input()) arr = [] for _ in range(N): arr.append(deque(list(input().strip()))) alpha = {} for i in range(N): j = 0 while True: if len(arr[i]) == 0: break if arr[i][j] in alpha: alpha[arr[i].popleft()] += 10**(len(arr[i])) else: alpha[arr[i].popleft()] = 10**(len(arr[i])-1) list = [] for i in alpha.values(): list.append(i) list.sort(reverse=True) resul.. 2022. 1. 27.
[백준] 12015번 - 가장 긴 증가하는 부분 수열 2 (파이썬) # 가장 긴 증가하는 부분 수열 2 import sys import bisect input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) result = [] result.append(arr[0]) for i in range(1, N): if arr[i] > result[-1]: result.append(arr[i]) else: index = bisect.bisect_left(result, arr[i]) result[index] = arr[i] print(len(result)) 이진탐색, bisect 1. 전체 리스트를 돌면서 - result의 마지막 원소보다 크면 append를 해준다 - 작으면 bisect_lef.. 2022. 1. 27.
[백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) # 가장 긴 증가하는 부분 수열 import sys N = int(input()) arr = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(1, N): for j in range(i): if arr[j] < arr[i]: dp[i] = max(dp[i], dp[j] + 1) print(max(dp)) DP, LIS알고리즘 1. 2중 for문을 이용해서 (j < i) - dp(현재까지의 가장 긴 증가하는 부분수열의 길이)를 업데이트 해나간다 - i 까지 이전의 dp를 이용해서 업데이트 해나가고 i를 하나씩 늘려가면서 다시 해나간다 2. dp의 값중 가장 큰 값을 출력 LIS(가장 긴 증가하는 부분 수열 알고리즘) 시간복잡도.. 2022. 1. 27.

티스토리툴바