le récit de ellie

코딩 테스트>> 데이터의 개수가 1,000만개를 넘어가거나 탐색 범위의 크기가 1,000억 이상일 경우 등 입력 데이터가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있다. 이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다. readline() import sys # 하나의 문자열 데이터 입력받기 input_data = sys.stdin.readline().rstrip() # 입력받은 문자열 그대로 출력 print(input_data) rstrip() : 입력의 맨 마지막 공백 문자를 제거해준다. Ref. 이것이 취업을 위한 코딩 테스트다 with 파이썬

📁 이진 탐색 (Binary Search) 💡 순차 탐색 (Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 ✔️ 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 ✔️ 찾으려는 데이터와 "중간점" 위치에 있는 데이터를 반복적으로 비교하는 방법 중간점이 실수일 때는 소수점 이하를 버린다. ✔️ 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다. ✔️ 시간 복잡도 : O(logN) → 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다. 💡 코딩테스트 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심해보..

heapq 힙(Heap) 기능을 제공하기 위한 라이브러리이다. 파이썬의 힙은 최소 힙(Min Heap)으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 뺴는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다. (보통 최소 힙 자료구조의 최상단 원소 : 가장 작은 원소) heapq.heappush( ) : 힙에서 원소를 삽입할 때 heapq.heappop( ) : 힙에서 원소를 꺼낼 때 항상 가장 작은 원소를 꺼내게 된다. 예) 힙 정렬(Heap Sort)을 heapq로 구현하는 경우 import heapq def heapsort(iterable): h = [] result = [] # 모든 원소를 차례대로 힙에 삽입 for value in iterable: heapq.heappus..

📁 파이썬의 정렬 라이브러리 ✔️ 병합 정렬(merge sort)을 기반으로 만들어졌으며, 퀵 정렬보다는 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징을 가진다. 📁 sort() 와 sorted() ✔️ iterable 객체를 정렬해주는 파이썬의 내장함수(built-in function) ✔️ reverse 속성 : False - 오름차순 / True - 내림차순 ✔️ 오름 차순 : 숫자의 크기가 커진다. ex. 1, 2, 3, 4 array = [9, 1, 8, 5, 4] array.sort() array Out[4]: [1, 4, 5, 8, 9] array = [9, 1, 8, 5, 4] sorted(array) Out[6]: [1, 4, 5, 8, 9] # 리스트에 반영되어..

📁 정렬 (Sorting) ✔️ 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 ✔️ 이진 탐색(Binary Search)의 전처리 과정이 되기도 한다. 📁 파이썬의 정렬 라이브러리 ✔️ 병합 정렬(merge sort)을 기반으로 만들어졌으며, 퀵 정렬보다는 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징을 가진다. 📌 [Python] 튜플을 원소로 하는 리스트 정렬 (tistory.com) 📁 Comparisons Sorting Algorithm (비교 방식 정렬 알고리즘) 📄 버블 정렬 (Bubble Sort) ✔️ in-place sort로 인접한 두 개의 데이터를 비교해가면서 정렬을 진행한다. ✔️ 가장 큰 값을 배열의 맨 끝으로 이동시키기때문에 정렬하고자 하는 원소의 ..

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 📁 DFS (Depth First Search) : 깊이 우선 탐색 / 스택 + 재귀 ✔️ 최대한 멀리 있는 노드를 우선으로 탐색, 깊은 부분을 우선적으로 탐색 stack = [0, 1, 3, 4, 2, 5, 6] 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 재귀함수는 수학의 점화식을 그대로 소스코드로 옮긴 형태..

루시와 엘라 찾기 코딩테스트 연습 - 루시와 엘라 찾기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 루시와 엘라 찾기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 동물 보호소에 들어온 동물 중 이름이 Lucy, Ella, Pickle, Rogan, Sabrina, Mitty인 동물의 아이디와 이름, 성별 및 중성화 여부를 조회하는 SQL 문을 작성해주세요. SELECT ANIMAL_ID, NAME, SEX_..

없어진 기록 찾기 코딩테스트 연습 - 없어진 기록 찾기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 없어진 기록 찾기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 천재지변으로 인해 일부 데이터가 유실되었습니다. 입양을 간 기록은 있는데, 보호소에 들어온 기록이 없는 동물의 ID와 이름을 ID 순으로 조회하는 SQL문을 작성해주세요. SELECT B.ANIMAL_ID, B.NAME FROM ANIMAL_INS..

이름이 없는 동물의 아이디 코딩테스트 연습 - 이름이 없는 동물의 아이디 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 이름이 없는 동물의 아이디 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 동물 보호소에 들어온 동물 중, 이름이 없는 채로 들어온 동물의 ID를 조회하는 SQL 문을 작성해주세요. 단, ID는 오름차순 정렬되어야 합니다. SELECT ANIMAL_ID FROM ANIMAL_INS WHERE N..

고양이와 개는 몇마리 있을까 코딩테스트 연습 - 고양이와 개는 몇 마리 있을까 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 고양이와 개는 몇 마리 있을까 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 동물 보호소에 들어온 동물 중 고양이와 개가 각각 몇 마리인지 조회하는 SQL문을 작성해주세요. 이때 고양이를 개보다 먼저 조회해주세요. SELECT ANIMAL_TYPE, COUNT(*) count FROM A..