본문 바로가기

전체 글

(76)
99클럽 코테 스터디 21일차 TIL 문제 설명풀이 과정 & 코드동적계획법을 매우 어렵게 생각하는 편이지만 오늘 같은 문제는 컴공에서도 자주 다루고 DP중에 가장 쉬운편임그리고 이 문제는 DP(bottom-up) 방식을 사용하면 쉽게 풀 수 있음생각해 봐야 할건 초기에 값 설정하는 부분만 할당하면 됨 def solution(n): answer = 0 dp = [0]*(n+1) dp[0], dp[1] = 0, 1 for i in range(2, n+1): dp[i] = (dp[i-2] + dp[i-1])%1234567 return dp[-1]
99클럽 코테 스터디 16일차 TIL 문제 설명풀이 과정 & 코드해당 문제는 word에 주어진 단어가 모음만을 사용해서 알파벳 순서로 몇번쨰에 위치하는지 찾는 문제임itertools에 product를 사용하면 쉽게 풀리는 문제임.만약 좀 더 좋은 풀이를 생각해본다면 길이가 5인 단어를 끝까지 만들기 전에 word를 찾아서 index를 return 하면 될것같은데 정렬이 되어 있지 않아서 이걸 해결할 방법까지는 크게 떠오르지 않는것 같음...def solution(word): from itertools import product answer = [] vowels = ['a', 'e', 'i', 'o', 'u'] for i in range(1, 6): answer += [''.join(perm) for perm..
99클럽 코테 스터디 11일차 TIL 문제 설명풀이 과정 & 코드먼저 어떤 리스트를 먼저 할지는 상관 없지만 반드시 순서는 지켜져야 함을 유의해야 함초기에는 words 라는 empty string을 만들고 cards와 일치하는 word를 ' '과 함께 추가하고 마지막에 goal과 words.split()이 같으면 'Yes'를 return하고 아니면 'No'를 리턴하게 했지만 for loop 안에서 일어나기 때문에 결과적으로 O(n^2)의 시간복잡도를 가져서 통과하는 코드여도 비효울적인 코드였음을 깨달음이후 words에 단어를 계속 추가하는 것 보다 index를 사용해서 해당하는 단어가 있으면 1씩 증가시키며 goal의 크기만큼 for loop을 돌고 나오면 'No'를 return하고 아니면 'Yes'를 return 하게 코드를 수정함def ..
99클럽 코테 스터디 10일차 TIL 문제 설명풀이 과정 & 코드heap을 사용해서 문제를 풀어야 하는걸 직감함. 하지만 python에서는 heapq가 최소만 구현됨따라서 최대값도 구현하기 위해서는 최소힙을 가지고 '-'를 붙혀 최대힙을 만들어야 함수가 들어올 때는 최소힙은 그냥 push하고 최대힙은 수를 음수로 뒤집어서 집어넣으면 항상 최대값이 제일 root에 있게 됨삭제할 때는 최대, 최소힙에서 수를 둘다 제거해야하는데 최소값을 제거하면 pop한 값을 최대힙에서도 remove를 통해 제거하고 heappop으로 제거한게 아니기 때문에 힙을 유지하지 못해서 heapify로 다시 힙 구조를 유지해야함. 최대값을 제거할 때도 마찬가지큐가 2개이기 떄문에 count변수를 사용해서 넣고 뺄때 증감을 통해 0이 되면 최소, 최대힙에 수가 비었음을 뜻..
99클럽 코테 스터디 9일차 TIL 문제 설명풀이 과정 & 코드해당 문제는 주어진 scoville안에 가장 작은 수가 K값 보다 작을 때 위 공식을 통해 새로운 scoville을 만드는 문제임주어진 K보다 모든 scoville지수가 높아야하고 섞은 횟수를 return 하면 되는 문제임리스트의 길이가 최대 1,000,000 이여서 2중 for loop을 하는 순간 시간초과가 남따라서 heap queue를 사용해서 풀어야 함초기에 heapq.heapify(scoville)을 해서 리스트의 앞단에는 항상 최소 값이 들어가게 만들고 이후 해당 값을 주어진 식을 통해 계산하고 다시 scoville에 추가하면 값의 크기에 따라 위치가 결정됨위 방법을 계속 진행하면 주어진 scoville 지수가 전부 K값이 될 수 있는지 없는지 알게됨추가로 K값 이상..
99클럽 코테 스터디 8일차 TIL 문제 설명풀이 과정 & 코드앞에서부터 완료가 되면 하나씩 꺼내서 완료 리스트에 담아 최종 답으로 return 하는 문제임하지만 앞에 progress가 마무리 되지 못하면 뒤가 마무리 되었다 하더라도 계속 완료가 되지 못함따라서 뒤와 상관없이 앞을 계속해서 speeds 리스트에 인덱스에 맞게 증가시키면서 값을 더하고 100 이상을 만족하면 꺼내고 다음걸 확인하는 식으로 코드를 구현하면 됨def solution(progresses, speeds): answer = [] done = [] progresses = progresses[::-1] speeds = speeds[::-1] while progresses: if progresses[-1] = 100: ..
99클럽 코테 스터디 4일차 TIL 문제 설명풀이 과정 & 코드이전에 역시나 풀어본 문제였음다 지우고 처음부터 다시 풀어봤는데 내 기억이 맞으면 처음 풀었을 때 낸 실수랑 똑같은 실수를 반복함ex) 주어진 예제가 'a b' 이면 'A B'를 return 해야 하는데 나의 경우에는 'A B'이런식으로 return해서 문제를 계속 틀림처음 주어진 문자열을 list에 담을때 그냥 split()말고 split(' ')으로 공백까지 리스트에 담아줘야 기존 공백들을 유지할 수 있음30분 잠깐 다른거를 했는데 그걸 제외해도 30분이나 걸림그래도 이전보다 더 깔끔한 코드를 작성한 것에 의의를 두는중...def solution(s): strings = list(s.split(' ')) ans = [] for i in range(len(st..
99클럽 코테 스터디 3일차 TIL 문제 설명풀이 과정 & 코드해당 문제는 파이썬의 sort() or sorted()를 사용하면 쉽게 해결할 수 있는 문제임처음에는 sort()하나를 생략해서 틀리게 나왔는데 문제를 제대로 다시 읽어보니 주어진 n으로 정리했는데 순서가 같다면 알파벳 순이다 라는 말이 있었음그래서 sort()를 하나 더 추가해서 알파벳순으로 정렬을 하고 이후에 lambda를 사용해서 n의 순서로 정렬을 하게 되면 문제를 쉽게 풀 수 있음def solution(strings, n): strings.sort() strings.sort(key=lambda x: x[n]) return strings