728x90

전체 글 93

2023.12.05.

HTML 삽입 미리보기할 수 없는 소스 올해 목표였던 BOJ(solve.ad) 플레티넘을 달성했다. 최근 들어 가장 기분이 좋은 날이었다. 많은(?) 알고리즘을 공부했지만 생각보다 DP의 웰논 유형이나 그리디 같은 기본적인 부분의 공백이 느껴졌다. 특히 기하 같은 건 손도 안 댔는데 , , 이제 전진은 잠시 멈추고 지나친 빈자리를 메꿔야겠다. 제10회 한양대학교 프로그래밍 경시대회(HCPC) Beginner Division Open Contest에 참가했다 아레나 S퍼포먼스와 함께 56위/211명 을 기록하며, 이전에 목표로 했던 하프솔브와 100위 이내는 달성했다. 하지만 대회가 끝난 후 업솔빙해보니 어렵게 생각해 풀지 못한 문제가 있다는 사실을 깨달았다. 스코어보드 보는 법도 알게 되었고, 아쉬운 점..

잡담 2023.12.06

첫 CP 후기

1. 난이도나 태그 없이 문제만 덩그러니 있으니 생각보다 어려웠다 . 특히 독해력이 부족한게 느껴졌다 . ( A번 5번 틀림 ,,) 2. 지금 생각해 보면 D번도 풀어볼 만했던 것 같은데 못 풀 것 같아서 설렁설렁한게 아쉽다. 어차피 페널티도 맞춰야 생기는 건데 3. 그래도 목표인 2솔은 넘겨서 좋았다 . 4. 다음주에 HCPC도 있는데 그땐 반절은 넘게 풀고 100위 안에 들어야겠다 . (현 150위/400) 5. 이제 1년동안 시간이 얼마 없을 텐데, 복학하고 까먹지 않으려면 공부하다가 종종 CP나 참여해야겠다, 끗 . CTF는 언제쯤..

잡담 2023.11.29

[BOJ/10090] Counting Inversions (C++)

개요 https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 알아두면 좋을 것 같은 유형 (P5) 본문 요약하면 순열에서 역전된 쌍의 개수를 찾는 문제이다. N이 ..

[BOJ/2042] 구간 합 구하기 (C++)

개요https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄www.acmicpc.net세그먼트 트리 기초 문제 (G1)풀이Range Sum Query를 처리하는 Segment Tree를 구현하면 된다.Ai의 범위가 약 ±2^63 이기 때문에 자료형 주의 ! 코드더보기#include using namespace std; using ll = long long; class segment_tree{ private: vector tr..

[C++/g++] PBDS(Policy Based Data Structure)

매일 상상만 하던 random access + O(logN) 삽입 삭제가 이미 있다니 . . (only g++) #include #include #include using namespace __gnu_pbds; using namespace std; #define ordered_set tree int main(){ ordered_set oSet; // idx 번째 iterator 반환 oSet.find_by_order(idx); // value의 idx를 반환 (value보다 작은 원소 개수를 반환) oSet.order_of_key(value); oSet.insert(v); oSet.erase(v); } 활용 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는..

[BOJ/3015] 오아시스 재결합 (C++)

개요 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net P5 자력솔 ! 본문 힌트 스택을 활용 같은 키가 연속으로 push되는 경우를 고려 풀이 더보기 스택 자료구조를 활용하여 입력을 받음과 동시에 top과 비교하여 처리 (선행 문제 : BOJ 2493번 탑) top이 더 클 경우 : result += (pop한 개수 + 1)개 후 push(키, 1(연속 1회를 의미)) top과 같을 경우 : result += (pop한 ..