목록Algorithms (64)
def solution(lines): S, E = [], [] total_lines = 0 for line in lines: total_lines += 1 d, s, t = line.split(' ') t = float(t[:-1]) hh, mm, ss = s.split(':') seconds = float(hh) * 3600 + float(mm) * 60 + float(ss) E.append(seconds + 1) S.append(seconds - t + 0.001) S.sort() cur_traffic = 0 max_traffic = 0 cnt_E = 0 cnt_S = 0 while ((cnt_E < total_lines) and (cnt_S < total_lines)):..
# 규칙 찾기 # 시간 초과... def solution(n): if n == 1: return 1 elif n == 2: return 2 dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3,n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n] % 1000000007 # 나머지 연산 과정을 for문 안에서 미리 처리하니까 효율성 통과 def solution(n): if n == 1: return 1 elif n == 2: return 2 dp = [0]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3,n+1): dp[i] = (dp[i-1] + dp[i-2]) % 1000000007 return dp[n] %..
Kruskal 알고리즘 탐욕적인 방법을 이용해서 그래프의 모든 정점을 최소 비용으로 연결하는 방법 처음 시작하는 노드로 부터 하나의 간선을 선택해 간다. # 최소 비용으로 모든 섬 통행 # A -> B -> C # 오류 def solution(n, costs): total = 0 island = set() roots = [] costs = sorted(costs, key=lambda x: -x[2]) # 경로 리스트 while len(island) < n: r1, r2, c = costs.pop() if r1 in island and r2 in island: continue island.add(r1) island.add(r2) roots.append((r1,r2,c)) return total # 방문 리..
from collections import defaultdict def solution(n, results): answer = 0 win, lose = defaultdict(set), defaultdict(set) for result in results: # 키 = 패자 / 값 = 승자 lose[result[1]].add(result[0]) # 키 = 승자 / 값 = 패자 win[result[0]].add(result[1]) for i in range(1, n+1): for winner in lose[i]: # win[i]: 승자 i가 이긴 패자 추가 win[winner].update(win[i]) for loser in win[i]: # lose[i]: 패자 i가 진 승자 추가 lose[loser].u..
# 홀수만 가능 # 시간 초과오류 def solution(s): answer = 0 n = len(s) if n == 1: return 1 # 가장 긴 길이부터 시작 s_len = n while s_len > 1: if n-s_len == 0: v = s[:s_len] if palindrome_check(v): return s_len else: for i in range(n-s_len): v = s[i:s_len+i] if palindrome_check(v): return s_len s_len -= 1 return 1 def palindrome_check(v): mid = (len(v)//2) # 짝수 길이 if len(v)%2 == 0: if v[0:mid] == v[-1:mid-1:-1]: retur..
# 첫 접근 # +, -, * , // # 이전 경우의 수에 대해서만 다음 과정을 반복함... # 오답 def solution(N, number): answer = 1 dp = [[5]] while answer number: continue else: temp.append(v//N) temp.append(int(str(v)+str(N))) answer += 1 if number in temp: return answer dp.append(temp) return -1 def solution(N, number): dp = [0, {N}] if N == number: return 1 for i in range(2, 9): case_set = {int(str(N)*i)} for j in range(1, i//2+..