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

가장 먼 노드 - 1번 노드로부터 가장 멀리 떨어진 노드 개수 구하기 - 최장경로를 가지는 노드 개수를 구하는 문제이므로 BFS로 접근했다 (동일 거리의 노드들을 순서대로 접근) - maxDist를 저장해두고 (현재까지) 최장거리의 노드 개수들을 저장해둠 #include #include using namespace std; vector graph[20001]; bool visited[20001]; int solution(int n, vector edge) { for(auto e : edge) { graph[e[0]].push_back(e[1]); graph[e[1]].push_back(e[0]); } int maxDist = 0, maxNum = 0; queue q; visited[1] = true; q..

타겟 넘버 - 주어진 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 구하기 (숫자의 순서 유지) int answer = 0; void dfs(vector& numbers, int idx, int target, int val) { if(idx == numbers.size()) { if(val == target) answer++; return; } dfs(numbers, idx+1, target, val+numbers[idx]); dfs(numbers, idx+1, target, val-numbers[idx]); } int solution(vector numbers, int target) { dfs(numbers, 0, target, 0); return answer; } // 재귀함수 이용하여 d..

signal: floating point exception (core dumped) 원인 => 0으로 나누기 시도할 때!! N으로 표현 - 특정 수와 사칙연산으로 표현할 수 있는 방법 중 사용횟수의 최솟값 구하기 - 서브 문제(더 적은 갯수의 N으로 구한 수)를 재사용해서 계산할 수 있음 (DP) set numbers[9]; void initialize(int N, int idx) { int t = 0; for(int i=0; i

입국심사 - 입국심사를 기다리는 사람 수, 각 심사관의 심사 시간 배열이 주어질 때, 모든 사람이 심사를 받는데 걸리는 최소 시간 - 이진 탐색 문제, 결과론적인 접근 => 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..

떨어지지 않은 주식 가격 #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)를 ..