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

입국심사 - 입국심사를 기다리는 사람 수, 각 심사관의 심사 시간 배열이 주어질 때, 모든 사람이 심사를 받는데 걸리는 최소 시간 - 이진 탐색 문제, 결과론적인 접근 => t만큼의 시간이 지났을 때, 몇 명이 처리되었을까? - 이진 탐색을 통해 처리된 인원이 n 이상인 t를 구해나가면 됨 #include #include using namespace std; long long solution(int n, vector times) { long long answer = (long long)n * (*min_element(times.begin(), times.end())); long long l = 1, r = answer; while(l=n) { // 답의 후보가 될 수 있음 answer = min(answ..

체육복 - 체육복 도난당한 학생 리스트/여벌 체육복 가져온 학생 리스트 주어짐 - 인접한 번호의 학생에게 체육복을 빌릴 수 있음, 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수도 있음 set l(lost.begin(), lost.end()); set r(reserve.begin(), reserve.end()); // 중복 요소 제거 for(auto it=r.begin(); it!=r.end();) { if(l.find(*it) != l.end()) { l.erase(*it); it = r.erase(it); } else { it++; } } // erase로 iterator 값을 넘겨주면 삭제한 원소의 다음 원소를 가리키는 iterator를 반환함 // 이걸 이용해 set 중복 요소 제거 가능 ve..

최소직사각형 - 명함들의 가로 세로 길이가 주어지고, 모든 명함을 수납할 수 있는 가장 작은 지갑의 크기를 구하는 것 - 명함을 가로로/세로로 눕힐 수 있음! int solution(vector sizes) { int max_w = 0, max_h = 0, min_area = 0; for(vector size : sizes) { // 가로로 넣었을 때 int tmp_w1 = max(max_w, size[0]); int tmp_h1 = max(max_h, size[1]); // 세로로 넣었을 때 int tmp_w2 = max(max_w, size[1]); int tmp_h2 = max(max_h, size[0]); if(tmp_w1*tmp_h1 < tmp_w2*tmp_h2) { min_area = tmp_..

C++ 벡터 복사 vector solution(vector array, vector commands) { vector answer; vector temp; for(int i = 0; i < commands.size(); i++) { temp = array; - 이렇게 할당 연산자 = 을 사용하면 deep copy 된다 vector solution(vector array, vector commands) { vector answer; for(vector command : commands) { vector tmp(array.begin()+command[0]-1, array.begin()+command[1]); - 나는 이렇게 범위 생성자를 사용했다. 대신 종료 iterator는 마지막 원소 + 1로 주어야 함..

힙 자료구조 - 완전 이진 트리 - 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일 이상이면 '..