0과 1 사이

https://leetcode.com/problems/triangle/description/?envType=study-plan-v2&envId=top-interview-150Given a triangle array, return the minimum path sum from top to bottom.For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row. Example 1:Input: triangle = [[2],[3,4],[6,..

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-interview-150 Backtracking 문제라는데 한번도 백트래킹을 풀어본적이 없다.그래서 다음과 같이 d의 개수에 따라 반복문을 생성하는 아주 비효율적인 코드를 생각해냈는데통과가 되긴 했다. 시간복잡도 : digits의 길이가 n이라면, O(3^n)공간복잡도 : O(n*3^n)class Solution: def letterCombinations(self, digits: str) -> List[str]: telephone = {'2':['a','b','c'], '3..

AWS에 취업한 이후로 글을 전혀 못썼다.. 이직준비를 하고 있기 때문에, 코딩테스트를 풀 때마다 글을 작성해보려 한다. https://leetcode.com/problems/implement-trie-prefix-tree/description/?envType=study-plan-v2&envId=top-interview-150인터뷰에 자주 나오는 150문제를 카테고리별로 풀려고 하고 있다. 나는 Trie 자료구조에 대해 처음 들어보는데, 그래서인지 이 문제는 그냥 리스트로 풀면 되는거 아닌가..? 라는 생각에 그 방법으로 풀어보았다. ^^...매우 단순한 내 코드class Trie: def __init__(self): self.trie = [] def insert(self, wor..

https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr def solution(rows, columns, queries): answer = [] matrix = [[i+m*columns for i in range(1, columns+1)] for m in range(rows)] for q in queries: x1, y1, x2, y2 = q[0]-1, q[1]-1, q[2]-1, q[3]-1 tm..

https://programmers.co.kr/learn/courses/30/lessons/77484 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr def solution(lottos, win_nums): answer = [] count = 0 #맞힌 숫자 개수 count_0 = 0 #지워진 숫자 개수 #맞힌 개수 별 로또 순위 win = {0:6, 1:6, 2:5, 3:4, 4:3, 5:2, 6:1} for l in lottos: if l == 0: count..

https://programmers.co.kr/learn/courses/30/lessons/77487 한참 헤맸다.. 쉬운 것 같은데 GROUP BY 하면 모든 쿼리가 나오지 않고 묶여서 나오고, 그래서 COUNT OVER PARTITION BY를 했더니 윈도우 함수라 where이나 having 조건을 걸수가 없었다 알고보니 서브쿼리를 이용하는 문제였다 SELECT * FROM PLACES WHERE HOST_ID IN( SELECT HOST_ID FROM PLACES GROUP BY HOST_ID HAVING COUNT(HOST_ID) >= 2) ORDER BY ID

오랜만에 다이나믹 프로그래밍 엇! 답이 맞는줄 알았는데 잘보니 틀리다. won[i]는 i원을 만들 수 있는 코인의 최소 개수를 저장해야하는데, 아래의 경우... 최소 개수를 저장하지 않는다는 문제가 있다. 초기화할때 -1로 모두 저장해버려서 최소값을 저장하게 되면 그냥 -1이 저장되기 때문이다.. import sys n, m = map(int, sys.stdin.readline().rstrip().split()) coin = [] coin.sort() for _ in range(n): coin.append(int(sys.stdin.readline().rstrip())) won = [-1] * (m+1) for i in coin: if i

https://programmers.co.kr/learn/courses/30/lessons/92344 코딩테스트 연습 - 파괴되지 않은 건물 [[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6 programmers.co.kr 이 문제.. 구현은 간단한데 효율성 통과하기가 정말 어렵다. 남은 3문제중에 그나마 간단한 것 같아서 도전했으나 .. 한시간동안 고민해도 해결방법을 찾지 못함.. 정확도는 모두 통과했다. 그러고나서 효율성을 ..