전체 글
-
[프로그래머스] 전화번호 목록 # HashAlgorithm 2024. 9. 8. 01:19
문제 링크1. 문제 설명전화번호를 담은 배열 phone_book이 파라미터로 주어질 때, 전화번호부에 적힌 전화번호 중 한 번호가 다른 번호의 접두어인 경우가 있으면 False를, 그렇지 않으면 True를 반환한다. 2. 제한 사항1 1 같은 전화번호가 중복해서 들어있지 않음 3. 입출력 예 4. 첫 번째 풀이(시간 초과) - Python 냅다 for문 두 번 돌려버렸다. 이중 중첩 반복문을 순회하면서 현재 전화번호가 비교 대상 전화번호와 다르고, 자신의 전화번호가 비교 대상 전화번호로 시작하는지 판단한다. 리스트를 동시에 두 번 조회하므로 시간복잡도 O(n^2)이다. 그리고 현재 전화번호가 비교 대상 전화번호와 다른지 판단해야한다는 의미는 자기 자신과의 비교를 불필요하게 수행하고 있다는 의미이다..
-
99클럽(3기) - 코테스터디 9일차 TIL # DPAlgorithm 2024. 8. 13. 00:22
프로그래머스 - 피보나치 수1. 문제 설명n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하는 함수 solution을 완성하라. 2. 제한 사항2 3. 입출력 예 4. 첫 번째 풀이(런타임 에러) - Python런타임 에러가 발생했다. 재귀를 사용했기 때문에 n이 100,000에 가까운 숫자일 경우 스택 오버플로우가 발생했을 것이다. 1) 메모이제이션과 피보나치 수 계산을 위한 F 클래스 생성초기화 함수 __init__에서 F(0) = 0, F(1) = 1로 메모이제이션을 위한 딕셔너리를 초기화한다. 피보나치 수열을 계산하기 위한 함수 fibo에서는 self.memo에 있는 키인지 먼저 확인 후 없으면 피보나치 수를 재귀적으로 계산한다. 이 때, n이 충분히 커졌을 경우 발생 가능한 오..
-
99클럽(3기) - 코테스터디 6일차 TIL # 이분탐색Algorithm 2024. 8. 4. 16:03
프로그래머스 - 18016. 숫자 카드 21. 문제 설명 정수 M개의 수에 대해서 각각 상근이가 가지고 있는 숫자 카드 N개에 포함되어 있으면 포함 개수를, 아니면 0을 공백으로 구분해 출력한다. 어제 문제는 상근이가 가지고 있는 숫자 카드 N개에 M개의 수 중에 하나라도 포함되어 있으면 1을 반환했다면, 오늘 문제는 포함 개수를 구해야 한다. 첫째 줄에 상근이 가지고 있는 숫자 카드 개수 N개가 주어지고, 둘째 줄에 상근이가 가지고 있는 숫자 카드에 적힌 정수들이 공백을 두고 주어지고, 셋째 줄에 정수 M이 주어지고, 넷째 줄에는 공백을 두고 M개의 정수가 주어진다. 2. 제한 사항1 1 10,000,000 3. 입출력 예 4. 첫 번째 풀이 (시간초과)ns.count(val)의 시간복잡도가 O..
-
99클럽(3기) - 코테스터디 5일차 TIL # 이분탐색Algorithm 2024. 8. 4. 14:38
프로그래머스 - 10815. 숫자 카드1. 문제 설명 정수 M개의 수에 대해서 각각 상근이가 가지고 있는 숫자 카드 N개에 포함되어 있으면 1, 아니면 0을 공백으로 구분해 출력한다. 첫째 줄에 상근이 가지고 있는 숫자 카드 개수 N개가 주어지고, 둘째 줄에 상근이가 가지고 있는 숫자 카드에 적힌 정수들이 공백을 두고 주어지고, 셋째 줄에 정수 M이 주어지고, 넷째 줄에는 공백을 두고 M개의 정수가 주어진다. 2. 제한 사항1 1 10,000,000 3. 입출력 예 4. 첫 번째 풀이 - Python1) 4줄의 입력을 처리한다. 4줄에 걸쳐 정수 N, N개의 숫자들, 정수 M, M개의 숫자들을 입력받는다. ns 생성에 O(N), ms 생성에 O(M)의 시간복잡도가 소요된다. 2) N개의 숫자들(..
-
99클럽(3기) - 코테스터디 4일차 TIL # 정렬Algorithm 2024. 8. 3. 10:55
프로그래머스 - H-Index1. 문제 설명어떤 과학자가 발표한 논문 n편이 인용된 횟수를 담은 배열(citations)이 주어진다. 논문 n편 중 h번 이상 인용된 논문이 h편 이상 인용되고, 나머지 논문이 h편 이하 인용되었다면 h의 최댓값을 H-Index라고 하며, H-Index를 구해서 반환해야 한다. 2. 제한 사항1 0 3. 입출력 예 4. 첫 번째 풀이 - Python 'h번 이상 인용된 논문이 h편 이상 인용되었는지 판단하는 기준'을 설정하는 것이 핵심이었다. 이 말 자체를 이해하고 어떻게 문제 풀이에 적용할까 고민하는 시간이 제일 많이 소요된 것 같다. h의 최대값을 구해야하기 때문에 citations를 내림차순으로 정렬해서 가장 많이 인용된 논문부터 몇 편의 논문에 인용되었는지 ..
-
99클럽(3기) - 코테스터디 3일차 TIL # 정렬Algorithm 2024. 8. 1. 22:56
프로그래머스 - 카드 뭉치1. 문제 설명문자열로 이루어진 배열 cards1, cards2와 원하는 단어 배열 goal이 파라미터로 주어질 때, cards1과 cards2에 적힌 단어들로 goal을 만들 수 있다면 "Yes", 만들 수 없다면 "No"를 반환해야 한다. 2. 제한 사항1 1 cards1과 cards2에는 서로 다른 단어만 존재함 2 1 goal의 원소는 cards1과 cards2의원소들로만 구성됨 cards1, cards2, goal의 문자열들은 모두 알파벳 소문자로만 구성됨 3. 입출력 예 4. 나의 풀이1) cards1과 cards2의 인덱스를 추적하기 위한 변수 할당cards1의 인덱스를 추적할 idx1, cards2의 인덱스를 추적할 idx2를 각각 0으로 초기화한다. 2) g..
-
99클럽(2기) - 코테스터디 29일차 TIL # Greedy # StringAlgorithm 2024. 6. 28. 20:44
LeetCode - 2864. Maximum Odd Binary NumberYou are given a binary string s that contains at least one '1'.You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.Return a string representing the maximum odd binary number that can be created from the given combination.Note that the resulting string can..
-
99클럽(2기) - 코테스터디 28일차 TIL # Priority Queue # Max HeapAlgorithm 2024. 6. 27. 22:48
LeetCode - 1337. The K Weakest Rows in a MatrixYou are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.A row i is weaker than a row j if one of the following is true:The number of soldiers in row i is less than the number..