본문 바로가기

Algorithm245

[백준] 12738번 - 가장 긴 증가하는 부분 수열 3 (파이썬) # 가장 긴 증가하는 부분 수열 3 import sys import bisect input = sys.stdin.readline N = int(input()) arr = list(map(int, input().split())) result = [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_left를 이용하여 해당 인덱스의 .. 2022. 2. 7.
[백준] 11437번 - LCA (파이썬) # LCA import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def make_depth(node, dep): visited[node] = True depth[node] = dep for nnode in arr[node]: if not visited[nnode]: parent[nnode] = node make_depth(nnode, dep+1) def lca(x, y): if depth[x] > depth[y]: y, x = x, y while True: if depth[x] == depth[y]: break y = parent[y] for _ in range(depth[x]): if x == y: return x x = parent[x.. 2022. 2. 7.
[프로그래머스] - 자동완성 class Trie(): head = [0, dict()] def add(self, word): current = self.head current[0] += 1 for x in word: if x not in current[1]: current[1][x] = [0, dict()] current = current[1][x] current[0] += 1 def check(self, word): current = self.head result = 0 for x in word: if current[0] == 1: return result result += 1 current = current[1][x] return result def solution(words): answer = 0 T = Trie() for w.. 2022. 2. 7.
[프로그래머스] - 방금그곡 (파이썬) sound = {'A#': '1', 'C#': '2', 'D#': '3', 'F#': '4', 'G#': '5'} def solution(m, musicinfos): answer = '' result = [] m = m.replace('A#', sound['A#']) m = m.replace('C#', sound['C#']) m = m.replace('D#', sound['D#']) m = m.replace('F#', sound['F#']) m = m.replace('G#', sound['G#']) for music in musicinfos: title, time, melody = music_melody(m, music) if m in melody: result.append([title, time]) r.. 2022. 2. 6.
[프로그래머스] - 파일명 정렬 (파이썬) number = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'] def solution(files): arr = [['' for _ in range(3)] for _ in range(len(files))] for file in range(len(files)): do = False slice = 0 for x in range(len(files[file])): if files[file][x] in number: if not do: arr[file][0] = files[file][:x] slice = x do = True if x == len(files[file])-1: arr[file][1] = files[file][x:] if x == len(files[file].. 2022. 2. 6.
[프로그래머스] - 압축 (파이썬) alpha = {'A':1,'B':2,'C':3,'D':4,'E':5,'F':6,'G':7,'H':8, 'I':9,'J':10,'K':11,'L':12,'M':13,'N':14,'O':15,'P':16,'Q':17, 'R':18,'S':19,'T':20,'U':21,'V':22,'W':23,'X':24,'Y':25,'Z':26} def solution(msg): answer = [] left, right = 0, 1 start = 0 while right 2022. 2. 6.
[프로그래머스] - n진수 게임 (파이썬) alpha = {10: 'A', 11: 'B', 12: 'C', 13: 'D', 14: 'E', 15: 'F'} def solution(n, t, m, p): all = '' count = 0 needs = p for _ in range(t-1): needs += m while True: if len(all) > needs: break all_temp = '' temp = count while True: k = temp % n if k in alpha: k = alpha[k] all_temp = str(k) + all_temp if temp // n != 0: temp = temp // n else: break all += all_temp count += 1 answer = '' for i in rang.. 2022. 2. 6.

티스토리툴바