알고리즘

문제 링크https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/  문제 설명 간단한 백트래킹 문제 문제 해결과정이번 문제는 어렵지는 않았고 테스트케이스도 전부 통과를 했지만 문제를 풀기위한 접근을 조금은 어색하게 한 부분이 있었기에 그 부분을 짚고 넘어가고자 한다. letters = [[],[],['a','b','c'],['d','e','f'],['g','h','i'],['j','k','l'],['m','n','o'],['p','q','r','s'],['t','u','v'],['w','x','y','z']]class Solution: def backtracking(arr,ans, digits,results): ..

골드5 문제이다.  코드dictionary = []puzzels = []flag = Truewhile True: s = input() if s == '#': break if s == '-': flag = False continue if flag: dictionary.append(s) else: puzzels.append(s)for puzzel in puzzels: candidates = [] for word in dictionary: puzzel_list = list(puzzel) flag = True for i in range(len(word)): if word[i] not in puzzel_list: flag = False ..

파이썬으로 푼 이유는 갑자기 알고리즘을 풀고 싶어서 풀다가 자바스크립트로 입출력하기 귀찮아서이다. n = int(input()) time = [] for _ in range(n): time.append(tuple(map(int, input().split()))) # print(time) time = sorted(time, key=lambda x: (x[0], x[1])) # print(time) cnt = 0 while len(time) > 0: start = time[0][0] end = time[0][1] del time[0] for i in range(len(time)): if time[i][0] >= end: start = time[i][0] end = time[i][1] del time[i] b..

💡 현재 레벨1에서 정답률 제일 낮은 문제 처음 시도했던 방법 function solution(bandage, health, attacks) { var answer = 0; let [prevAttackTime, prevDamage] = attacks[0]; attacks.shift(); dHealth = health; attacks.forEach(attack=>{ let [attackTime, damage] = attack; dHealth -= prevDamage; console.log(dHealth); if(attackTime - prevAttackTime >= bandage[0]){ dHealth += bandage[1] * (attackTime-prevAttackTime); dHealth += Ma..

https://www.codetree.ai/missions/2/problems/non-overlapping-two-rectangles?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이 문제의 어려움 완전탐색을 진행하면 된다고 생각했지만 서로 다른 직사각형이기 때문에 가장 먼저 떠오른 naive한 풀이법이 for의 depth가 매우 깊어지는 문제가 있었다. 이를 어떻게 해결하면 좋을지 한참을 고민했다.

https://www.codetree.ai/missions/2/problems/max-of-xor/submissions 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai n, m = map(int,input().split()) arr = list(map(int,input().split())) selected = [] ans = -1 def f(d): global ans if d == m: s = 0 for item in selected: s = s^item ans = max(ans,s) return for i in range(n): if arr[i] n..

https://www.codetree.ai/missions/2/problems/max-sum-of-numbers?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai n = int(input()) arr = [] for i in range(n): arr.append(list(map(int,input().split()))) visited = [False] * n ans = -1 def f(d,s): global ans if d == n: ans = max(s,ans) return for i ..

처음에는 완전 나이브 하게 코드를 짰었다. for i in range(n): for j in range(n): if i==j: continue if len(phone_book[i]) > len(phone_book[j]):continue if phone_book[i] == phone_book[j][0:len(phone_book[i])]: print(phone_book[i]) return False 하지만 시간복잡도가 O(N^2)이다 보니 효율성 테스트에서 떨어지는 문제가 발생했다. def solution(phone_book): n = len(phone_book) phone_book.sort() for i in range(1,n): if phone_book[i-1] in phone_book[i] return..