누적 합(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.

[PY] 백준 10988 팰린드롬인지 확인하기

n=input() a=list(n) m=list(reversed(a)) ans=1 for i in range(len(a)): if a[i]!=m[i]: ans=0 break print(ans)

• format_list_bulleted coding/baekjoon: python
• · 2024. 1. 10.

[PY] 백준 3020 개똥벌레

n,h=map(int,input().split()) a=[0]*(h+1) b=[0]*(h+1) min=n count=0 for i in range(n): if i%2==0: a[int(input())]+=1 else: b[int(input())]+=1 for i in range(h-1,0,-1): a[i]+=a[i+1] b[i]+=b[i+1] for i in range(1, h+1): if min>(a[i]+b[h-i+1]): min=a[i]+b[h-i+1] count=1 elif min == (a[i]+b[h-i+1]): count+=1 print(min,count)

• format_list_bulleted coding/baekjoon: python
• · 2024. 1. 10.

[PY] 백준에서 파이썬 입력 받기

보호되어 있는 글입니다.

• format_list_bulleted coding/+
• · 2024. 1. 10.

[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.