누적 합(prefix sum)

누적 합: index 0부터 n까지 탐색 -> index i일 때, 0부터 i까지의 총합 표현 방법 1. 시간복잡도가 O(N^2)인 방법 array=[1,2,3,4,5,6] n=len(array) prefixsum=[0]*n for i in range(n): for j in range(i+1): prefixsum[i]+=arrary[j] 2. 시간복잡도가 O(N)인 방법

• format_list_bulleted coding/baekjoon: cpp
• · 2024. 1. 12.

[CPP] 백준 17390 이건 꼭 풀어야 해!

길이 N짜리 수열 A A를 비내림차순 정렬 B 이걸 Q개 *비내림차순 (좌항)> n >> q; vector v(n+1); for (int i=1; i> v[i]; sort(v.begin(), v.end()); for (int i=1; i> l >> r; cout

• format_list_bulleted coding/baekjoon: cpp
• · 2024. 1. 8.

정렬 시간복잡도

시간 복잡도 한 번에 보기 (설명은 후술) 시간 빠르기는 다음과 같음 o(1) > o(logn) > o(n) > o(nlogn) > o(n^2) > o(2^n) > o(n!) sorting best average worst 버블 정렬 o(n^2) o(n^2) o(n^2) 선택 정렬 o(n^2) o(n^2) o(n^2) 퀵 정렬 o(nlogn) o(nlogn) o(n^2) 힙 정렬 o(nlogn) o(nlogn) o(nlogn) 병합 정렬 o(nlogn) o(nlogn) o(nlogn) 삽입 정렬 o(n) o(n^2) o(n^2) 쉘 정렬 o(n) o(n^2) 기수 정렬 o(n) o(n) o(n) 카운팅 정렬 o(n) o(n) o(n)

• format_list_bulleted coding/baekjoon: cpp
• · 2024. 1. 8.

[CPP] 백준 27866 문자와 문자열

#include #include using namespace std; int main() { string s; cin>>s; int i; cin>>i; i--; cout

• format_list_bulleted coding/baekjoon: cpp
• · 2024. 1. 8.

[CPP] 백준 2444 별 찍기 - 7

#include #include using namespace std; int main() { int N; cin>>N; string ar; int M=1; int Q=4; for(int s=0;s

• format_list_bulleted coding/baekjoon: cpp
• · 2024. 1. 6.

[CPP] 백준 3003 킹, 퀸, 룩, 비숍, 나이트, 폰

동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다. 체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검정색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다. 체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다. 동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오. #include using namespace std; int main() { int h[6]; cin>>h[0]>>h[1]>>h[2]>>h[3]>>h[4]>>h[5]; int w[6]]={1,1,2,2,2,8}; for(int t=0;t

• format_list_bulleted coding/baekjoon: cpp
• · 2024. 1. 6.