대충공부한거적어두는블로그

힙 자료구조 - 완전 이진 트리 - min heap, max heap 존재함 (부모 자식 간의 대소 관계) - 삽입은 O(log n), 힙 빌드 시 O(n) C++로 구현 - 인덱스 접근 편하게 배열로 함 - insert, removeMin, siftdown(heapify) 함수 필요 int n = 0; int heap[1000000]; void swap(int i, int j) { int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } void insert(int x) { heap[n++] = x; int parent; for(int k=n-1; k>0; k=parent) { parent = (k-1)/2; if(heap[parent] 두 개의 시작 가능한 t..

Xpath - XML 문서의 특정 요소나 속성에 접근하기 위한 경로 - HTML 문서에서 특정 요소 찾기 쉽게 문법 제공 re 모듈 - 정규식 표현 import re p = re.compile("ca.e") # . 는 문자 하나를 의미 > care, cafe, case # ^ 는 문자열 시작 의미 > ^de : desk, destination # $ 는 문자열의 끝 의미 > se$ : case, base m = p.match("case") if m: print(m.group()) # case 출력됨, 주어진 문자열에 처음부터 일치하는지 확인하기에 caseless도 일치라고 봄 else: print("매칭되지 않음") requests vs. selenium - requests는 정적 웹페이지에 사용, 속도..

떨어지지 않은 주식 가격 #include #include #include using namespace std; vector solution(vector prices) { vector answer(prices.size()); stack s; // 가격 안떨어지는 한 계속 push됨 for(int i=0; i prices[i]) { // 가격 떨어진 거 answer[s.top().first] = i - s.top().first; s.pop(); } else break; } s.push(make_pair(i, prices[i])); } while(!s.empty()) { answer[s.top().first] = (prices.size()-1) - s.top().first; s.pop(); } return a..

sort()로 정렬하기 - sort(v.begin(), v.end()) 하면 오름차순 정렬, sort(v.rbegin(), v.rend()) 하면 내림차순 정렬 - sort(v.begin(), v.end(), compare) 해서 사용자 정의 비교함수 정의해도 됨, 리턴타입 bool인 함수 정의 bool compare(pair a, pair b) { if(a.second == b.second) { return a.first b.second; } max element 구하기 - max_element(start, end)를 이용하면 [start, end) 범위 중에 가장 큰 값의 iterator를 반환 - *max_element(start, end)를 ..

C++ 해시 - unordered_map STL 자료형 활용 - BST로 탐색하는 O(log n)의 map 과 달리 O(1)의 시간복잡도를 가짐 전화번호부 목록에서 접두어 여부 조사 #include #include #include using namespace std; bool solution(vector phone_book) { unordered_map hash_map; for(string phone : phone_book) { hash_map[phone] = 1; } for(int i=0; i

1. 자동차 대여 기록에서 장기/단기 대여 구분하기 SELECT HISTORY_ID, CAR_ID, DATE_FORMAT(START_DATE, "%Y-%m-%d") AS START_DATE, DATE_FORMAT(END_DATE, "%Y-%m-%d") AS END_DATE, IF(DATEDIFF(END_DATE, START_DATE) >= 29, "장기 대여", "단기 대여") AS RENT_TYPE FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY WHERE START_DATE BETWEEN '2022-09-01' AND '2022-09-30' ORDER BY HISTORY_ID DESC // 대여 시작일이 2022년 9월에 속하는 대여 기록에 대해서 대여 기간이 30일 이상이면 '..

1. 주문량이 많은 아이스크림들 조회하기 SELECT F.FLAVOR FROM FIRST_HALF F LEFT JOIN ( SELECT FLAVOR, SUM(TOTAL_ORDER) AS TOTAL_ORDER FROM JULY GROUP BY FLAVOR ) AS J ON F.FLAVOR = J.FLAVOR ORDER BY (F.TOTAL_ORDER+IFNULL(J.TOTAL_ORDER,0)) DESC LIMIT 3 // 7월 아이스크림 총 주문량과 상반기의 아이스크림 총 주문량을 더한 값이 큰 순서대로 상위 3개의 맛을 조회하는 SQL 문 - JULY 테이블에서는 FLAVOR 외래키에 대해 그룹화를 해주어야 하며 - 7월에 안팔렸지만 상반기에서는 팔린 맛이 있을 수 있기에 IFNULL 처리를 해주었음 2..

1. 즐겨찾기가 가장 많은 식당 정보 출력하기 SELECT R.FOOD_TYPE, R.REST_ID, R.REST_NAME, R.FAVORITES FROM REST_INFO R JOIN ( SELECT FOOD_TYPE, MAX(FAVORITES) AS FAVORITES FROM REST_INFO GROUP BY FOOD_TYPE ) AS F ON (R.FOOD_TYPE = F.FOOD_TYPE AND R.FAVORITES = F.FAVORITES) ORDER BY R.FOOD_TYPE DESC // 음식종류별로 즐겨찾기수가 가장 많은 식당의 음식 종류, ID, 식당 이름, 즐겨찾기수를 조회하는 SQL문 - GROUP BY를 통해 음식 종류별 MAX FAVORITES 수를 구할 수 있고, 이를 기반으로 ..

1. 가격이 제일 비싼 식품의 정보 출력하기 SELECT * FROM FOOD_PRODUCT ORDER BY PRICE DESC LIMIT 1 - 혹은 서브쿼리와 MAX()를 이용해 풀 수도 있다 SELECT * FROM FOOD_PRODUCT WHERE PRICE = (SELECT MAX(PRICE) FROM FOOD_PRODUCT) 2. 가장 비싼 상품 구하기 SELECT MAX(PRICE) AS MAX_PRICE FROM PRODUCT 3. 최댓값, 최솟값 구하기 SELECT MAX(DATETIME) AS 시간 FROM ANIMAL_INS // 혹은 MIN(DATETIME) 4. 동물 수 구하기 SELECT COUNT(*) AS count FROM ANIMAL_INS 5. 중복 제거하기 SELECT..

1. 평균 일일 대여 요금 구하기 SELECT ROUND(AVG(DAILY_FEE),0) as AVERAGE_FEE FROM CAR_RENTAL_COMPANY_CAR WHERE CAR_TYPE = 'SUV' - ROUND( 숫자|컬럼 등 , 자릿수 ) : 반올림하여 소숫점 아래 해당 자릿수까지 표 - AVG 함수 : 평균 구하기, 평균 구할 때 NULL 있다면 IFNULL(DAILY_FEE,0) 이런 식으로 넣어주어야 함 - 그룹별 평균 구하기 : SELECT job, AVG(sal) as avg_sal FROM emp GROUP BY job , 참고로 as는 컬럼명 지정 - 조건절 다양한 방법들 : WHERE CAR_TYPE IN ('SUV') , LIKE 'SUV' , REGEXP '^SUV$' 2...