🔸 문제 접근 방식 다음 방식으로 문제를 접근하였다. 논문이 인용될 최대값을 H-index로 설정한 뒤 1씩 감소시켜가며 H-index 조건을 확인한다. 인용될 최대값은 len(citations) H-index는 두 조건을 만족한다. H-index 회 이상 인용된 논문의 수가 H-index 이상이다. H-index 회 이하 인용된 논문의 수가 H-index 이하이다. H-index 의 최대값을 선택한다. 📌 문제 풀이 정렬 문제이기는 하나, H-index가 될 target값을 기준으로 citations을 분리했다. target값보다 크거나 같은 논문은 bigList에 추가 target값보다 작거나 같은 논문은 smallList에 추가 그리고 2 조건을 만족하면 H-index 그룹인 resultList에 ..

🔸 문제 해결 방향 문자열 처리를 통해 풀어야한다. 문자열 비교가 어떻기 이루어지는지 숙지할 것 문자열 곱셈을 수행한 뒤 비교한 이유는? 문자열 비교 → 숫자 변환 → 문자열 변환 후 반환 숫자로 바꾸어 주지 않을 시 발생하는 문제는? 문제 접근 리스트 정렬 기능 이용하기 처음 시도는 리스트 정렬 기능을 이용했다. 정렬 시 기준이 되는 key 값을 문자열의 첫 번째 값으로 설정했다. 첫째자리수가 가장 클 경우 앞 쪽에 배치된다. ❌ 첫째 자리 수가 같은 경우 발생 5와 50은 어떻게 비교할까? → 정렬 시 2번째 기준을 문자열 길이로 설정한다. 둘째 자리 수가 같을 경우 문자열 길이가 짧은 쪽이 앞에 배치된다. ❌ 그럼 5, 56, 3의 경우는 어떨까? → 정렬 시 2번째 기준 56, 5, 3이 되어야 ..

🔸 만들 수 없는 금액 동전 n개가 주어졌을 때, 해당 동전들로 만들 수 없는 금액을 구하여라. 동전은 최대 1000개, 각 동전의 크기는 최대 1,000,000원이다. ex) 1,2,3, 7원 동전이 주어졌을 때, 1원 : 1 2원 : 1 3원 : 3 4원 : 1+3 5원 : 2+3 6원 : 1+2+3 7원 : 7 8원 : 1+7 9원 : 2+7 10원 : 3+7 11원 : 1+3+7 12원 : 2+3+7 13원 : 1+2+3+7 14원 : X 📌 초기 접근 방법 처음에 생각한 접근 방식은 어려웠다. 동전의 모든 조합을 구한다. 조합 별 최종 합을 구한다. 최종 합을 set에 담는다. 여기서 문제는 모든 조합을 구할 때 너무 많은 비용이 든다. Combination 연산 시에는 팩토리얼 단위로 연산하기..

🔸복잡도 코딩테스트를 준비하기 전, 시간 복잡도와 공간복잡도 이해하기 대부분의 코딩테스트 문제에는 제한 시간과 메모리가 존재합니다. 이를 바탕으로 적절한 시/공간 복잡도를 계산한 뒤 적절한 알고리즘을 사용할 필요성이 있습니다. 따라서 시간 복잡도와 공간복잡도에 대해 이번 기회에 정리하려고 합니다. 🔸시간복잡도 '제한시간'안에 알고리즘 문제를 해결하기 위해서는 시간복잡도를 이해해야 합니다. 일반적으로 O(N)과 같은 빅오 표기법을 기준으로 연산 횟수를 계산합니다. for 문으로 문제를 해결할 시 시간복잡도는 다음과 같습니다. 단일 for문: $O(N)$ 이중 for문: $O(N^2)$ 삼중 for문: $O(N^3)$ N값이 어떻게 주어지냐에 따라 시간복잡도를 계산해보겠습니다. N=500 N=500일 경우 ..

📌문제설명 📌문제풀이 소스코드 import sys class Queue: def __init__(self): self.queue = [] def push(self, x): self.queue.append(x) def pop(self): if len(self.queue) !=0: print(self.queue.pop(0)) else: print(-1) def size(self): print(len(self.queue)) def empty(self): if len(self.queue) == 0: print(1) else: print(0) def front(self): if len(self.queue) == 0: print(-1) else: print(self.queue[0]) def back(self): i..

📌문제설명 📌문제접근방식 핵심은 Valid한 PS임을 검증하는 것이다. 그래야 VPS와 VPS를 결합해도 VPS가 나오기 때문이다. 문자열 중 '(' 와 ')'를 스택을 이용해 검증했다. (가 나오면 스택에 넣고, )를 만나면 (를 꺼냈다. 단, 다음과 같은 경우 NO를 출력한다. 1. 스택에 (가 없는데 )를 만났다. 2. 검증이 끝난 후 스택에 (가 남아있다. 위 과정이 끝난 후 문제가 없으면 YES를 출력한다. 즉, '(' 와 ')' 의 개수가 같아야 하며 '('가 오기 전에 ')'가 오면 안된다. 📌문제풀이 import sys n = int(sys.stdin.readline().rstrip()) exlist = [sys.stdin.readline().rstrip() for x in range(n)..

📌문제설명 📌문제접근방식 정렬 문제였고, 기존에 풀었던 문제들처럼 기준을 2개로 설정하면 되는 문제였다. x 좌표 비교 후 같다면 y 좌표를 정렬했다. 📌문제풀이 소스코드 import sys n = int(input()) locations = [list(map(int,sys.stdin.readline().rstrip().split())) for x in range(n)] locations.sort(key = lambda location : (location[0], location[1])) for x in locations: print(x[0], x[1])

📌문제설명 📌문제풀이 소스코드 import sys class Deque: def __init__(self): self.deque = [] def push_front(self, x): self.deque.insert(0, x) def push_back(self, x): self.deque.append(x) def pop_front(self): if len(self.deque) == 0: print(-1) else: print(self.deque.pop(0)) def pop_back(self): if len(self.deque) == 0: print(-1) else: print(self.deque.pop()) def size(self): print(len(self.deque)) def empty(self):..

📌문제설명 📌문제접근방식 1차시도 3단계에 걸쳐 문제를 해결하려고 했다. 하지만 결과적으로 문제를 복잡하게 만들었다. 1. 입력받은 값을 정렬한다. 2. (입력받은 값, 개수)를 저장한 리스트를 생성한다. 3. 2번의 리스트에서 입력받은 값을 기준으로 이진탐색을 수행하고, 개수를 반환한다. 첫 시도는 이진 탐색을 사용했다. 이유는 숫자 카드 개수가 50만이었고, 숫자 카드의 범위가 -천만~+천만이었기 때문이다. 따라서 최악의 경우 50만 x 7log10을 계산하면 된다고 생각했다. 하지만 시간초과가 발생했다. 따라서 해쉬로 구현해야겠다는 생각이 들었다. 소스코드 import sys n = int(sys.stdin.readline().rstrip()) cards = list(map(int, sys.stdi..

📌문제 설명 📌문제접근방식 enumerate함수를 이용해 회원별 번호를 매긴 뒤 나이순으로 정렬하면 된다고 생각했다. 만약 나이가 같다면 매겨둔 회원 번호로 정렬을 실시한다. 따라서 정렬의 기준를 2개로 설정했다. 📌문제풀이 1차 시도 실패한 이유는 다른 곳에서 발생했다. 입력받을 때 나이가 문자로 입력되었다. [(['21', 'Junkyu'], 1), (['21', 'Dohyun'], 2), (['20', 'Sunyoung'], 3)] 따라서 '21'과 '20'을 숫자로 바꿔주니 문제 없이 통과했다. 비교할 때는 반드시 비교하는 대상의 타입이 무엇인지 확인해야겠다. 소스코드 import sys n = int(sys.stdin.readline().rstrip()) input_list = [sys.stdi..