바킹독의 실전 알고리즘 : 시공간 복잡도, 정수 자료형, 실수 자료형

22 Jan 2026 • Self-study

시간복잡도와 공간복잡도

컴퓨터는 1초에 대략 3-5억개 정도의 연산을 처리할 수 있다. 연산이 단순 연산인지, 나눗셈, 곱셈, 함수 호출 같은 복잡한 연산인지에 따라 약간의 차이는 있을 수 있다.

int func1(int arr[], int n){
    int cnt =0;
    for(int i=0;i<n;i++){
        if(arr[i]%5==0) cnt++;
    }

    return cnt;
}

위와 같은 코드가 있다. 여기서의 연산 횟수를 확인해보자

int func1(int arr[], int n){
    int cnt =0; //1번 
    for(int i=0;i<n;i++){ // 초기값 0 설정으로 1번
        if(arr[i]%5==0) cnt++; // 5의 나머지 구하기로 1번, 0이랑 맞는지 1번, cnt 증가 1번 
        //i 증가 1번, i가 n보다 작은지 확인 1번 
    }

    return cnt; //1번 
}

1+1+5n+1= 5n+3

문제

최선의 경우 1초 (바로 정답) 최악의 경우 n초 (가장 나중이 정답) 평균은 중간에 있을 때 n/2

문제

최선의 경우 1초

최악의 경우는.. n명이 있는데 가운데에 질의해서 왼쪽, 오른쪽으로 방향을 나누고 또 가운데에 질의해서.. 숫자를 대입해보면 더 쉬움 16명일 때면 8명으로 나누고 4명으로 나누고 2명으로 나누면 1명이 걸러질 것 -> 총 4명 log₂N

빅오표기법은 대표항만 남겨두는 방법이다.

내 풀이가 빅오로 몇이고
제한시간 내에 통과할 수 있는지

n이 500인데 O(2ⁿ) 풀이를 했다면 시간 내에 불가하다.

#include <bits/stdc++.h>

using namespace std;

int N;
cin>>N;
int sum=0;

for(int i=1;i<=N;i++){
    if(i%3==0 || i%5==0)
        sum+=i;
}

위 코드는 O(n)이다. 이걸 O(1)로 줄일 수 있다고 한다. 흠.. 3,5,6,9,10.. N=3, sum=3 N=4, sum=3 N=5, sum=8 N=6, sum=14 N=7, sum=14 N=8, sum=14 N=9, sum=23 N=10, sum=33

#include <bits/stdc++.h>
using namespace std;

int N; 
cin>>N;

//3 
int n= (N-(N%3))/3;
int p=n/2(2*3+(n-1)*3)

//5
int m,q=0;
if (N>=5){
    m=(N-(N%5))/5;
    q=m/2(2*5+(m-1)*5);
}

//15
int x,o=0;
if (N>=15){
    x=(N-(N%15))/15;
    o=x/2(2*15+(x-1)*15);
}

int sum=p+q-o;
return sum;

제출한 답

#include <iostream>

using namespace std;

// 1부터 n까지 k의 배수의 합을 구하는 함수
long long sumMultiples(int n, int k) {
    int count = n / k; // 배수의 개수 (ex: 10까지 3의 배수 개수 = 3개)
    
    // 공식: k * (1 + 2 + ... + count) = k * count * (count + 1) / 2
    // long long 형변환을 통해 큰 수 계산 시 오버플로우 방지
    return (long long)k * count * (count + 1) / 2;
}

int main() {
    int N;
    if (!(cin >> N)) return 0;

    // 포함-배제의 원리 적용
    long long ans = sumMultiples(N, 3) + sumMultiples(N, 5) - sumMultiples(N, 15);

    cout << ans << endl;
    return 0;
}

코드 리뷰

integer division 조심 : 알고리즘에서 곱셈을 먼저하고 나중에 나눗셈 진행하기
오버플로우 방지를 위해 long long 선언
포함-배제의 원리 적용

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ 집합 문제처럼 풀기
코드 사용성 높이기

long long ans = sumMultiples(N, 3) + sumMultiples(N, 5) - sumMultiples(N, 15);

#include <bits/stdc++.h>

using namespace std;

int func2(int arr[],int N){

}

int input;
int arr[1001]={0,};
cin >> input;

for(int i=0;i<input;i++){
    cin>>arr[i];
}

return func2(arr,input);

공간 복잡도

코테에서는 거의 시간복잡도가 까다롭기 때문에 중요한 내용은 아니라고 생각하지만 일단 보자.

512MB는 약간 1.2억개의 int 선언이 가능하다.

jekyll 블로그에서 SSTI 웹해킹 문제 writeup 작성하기

21 Jan 2026 • +

tistory2git으로 백업 다 하고 openai가 파일명이나.. 적당히 살펴봐야 할 것들이 있는데 SSTI 라이트업이 진짜 코드로 인식되어서 렌더링된 사이트에서도 안 뜨고 자꾸 terminal에 liquid warning이라고 뜨는 문제 발생.. jekyll이 사용하는 liquid 템플릿 엔진이 {{ }} {% %} 같은 걸 인식한다.

방법 1. {% raw %} 사용

{% raw %}
    ```py
    payload = "{{ ''.__class__.__mro__[1].__subclasses__() }}"
    ```
{% endraw %}

방법 2. html encoding

{ → &#123;
} → &#125;
% → &#37;

이건 좀 귀찮;

방법 3. md config에 추가

---
layout: post
title: "-"
render_with_liquid: false
---

이런 식으로 render_with_liquid을 false로 설정하는 방법도 있다. post가 순수 마크다운일 경우에만 사용하자.

git 관련 case

21 Jan 2026 • +

A,B를 모두 커밋했는데 깃헙에는 A까지만 푸시하고 싶을 때

현재 상태

A -> 여기가 내 로컬 commit 
---
B -> A보다 먼저 commit 
---
C -> github와 동기화된 commit 

이런 상태일 때 B만 push 하고 싶을 때

방법 1. commit ID 사용해서 push

git push origin <복사한_커밋_해시>:<브랜치명>

이러면 커밋해시만 푸시 가능하다.

방법 2. reset

git reset --soft HEAD^

Head에 있는 커밋을 staging 상태로 되돌리는 명령어이다. --soft 대신 --hard도 가능하다. 대신 작업 내용이 완전히 삭제되니까 앵간하면 쓰지말자. HEAD^는 바로 이전 커밋을 뜻한다.

Barking 04

20 Jan 2026

Barking 03

20 Jan 2026