clock() 함수를 이용해 코드의 실행 시간을 측정해보자.


환경

  • C, C++


방법과 예제

사용법

  • clock(): time.h에 들어있는 함수로 프로그램에 의해 프로세서가 소비된 시간을 반환하는 함수입니다. 프로세서가 측정한 프로그램 실행시간이라 볼 수 있습니다.
  • clock_t: clock ticks의 자료를 담고 있는 자료형으로 clock()의 반환형입니다.
  • CLOCKS_PER_SEC: 초당 clock ticks의 수를 나타낸 매크로로 시스템에 따라 기본 값이 다르며 시간을 표시하기 위해 아래 예제처럼 사용합니다.
#include <stdio.h>
#include <time.h> // time.h 헤더 파일을 include 해줘야합니다.

int main(){

    clock_t start = clock(); // 시작 시간 저장

    // 필요한 코드들 작성

    clock_t end = clock(); // 코드가 끝난 시간 저장

    // 걸린 시간 출력
    // 단위: 초(second)
    // CLOCKS_PER_SEC로 나눠줘야 초단위로 나옵니다.
    printf("Time: %lf\n", (double)(end - start)/CLOCKS_PER_SEC);

    return 0;
}


예제

  • 이중 for문을 이용한 시간 측정
#include <stdio.h>
#include <time.h> // time.h 헤더 파일을 include 해줘야합니다.

#define ITERATION_TIME 100000

int main (){

    clock_t start = clock(); // 시작 시간 저장

    for(int i = 0; i < ITERATION_TIME; ++i){
        for(int j = 0; j < ITERATION_TIME; ++j)
            int do_something;
    }

    clock_t end = clock(); // 코드가 끝난 시간 저장

    // 걸린 시간 출력
    // 단위: 초(second)
    // CLOCKS_PER_SEC로 나눠줘야 초단위로 나옵니다.
    printf("Time: %lf\n",(double)(end - start)/CLOCKS_PER_SEC);

}
  • 결과
$ g++ practice_board.cpp -o practice_board
$ ./practice_board
Time: 18.825036


참고자료

Measure code running time by using clock() function in c or cpp.


Environment and Prerequisite

  • C, C++


Usage and Example

Usage

  • clock(): It is a function in time.h which returns the processor time consumed by the program. We can consider it as processor running time consumed by program
  • clock_t: Return type of clock() function. It involves data type of clock ticks.
  • CLOCKS_PER_SEC: It is a macro which represents clock ticks per second. Its value depends on system. Use this for human-readable time.
#include <stdio.h>
#include <time.h> // include time.h

int main(){

    clock_t start = clock(); // save start time

    // Code Here!!!

    clock_t end = clock(); // save end time

    // Print measured time
    // Unit: second
    // Dividing a count of clock ticks by this expression yields the number of seconds.
    printf("Time: %lf\n", (double)(end - start)/CLOCKS_PER_SEC);

    return 0;
}


Example

  • Measuring nested loop iteration time.
#include <stdio.h>
#include <time.h> // include time.h

#define ITERATION_TIME 100000

int main (){

    clock_t start = clock(); // save start time

    for(int i = 0; i < ITERATION_TIME; ++i){
        for(int j = 0; j < ITERATION_TIME; ++j)
            int do_something;
    }

    clock_t end = clock(); // save end time

    // Print measured time
    // Unit: second
    // Dividing a count of clock ticks by this expression yields the number of seconds.
    printf("Time: %lf\n",(double)(end - start)/CLOCKS_PER_SEC);

}
  • Result
$ g++ practice_board.cpp -o practice_board
$ ./practice_board
Time: 18.825036


Reference

누적 합(Prefix sum)을 이용해서 구간 합을 구해보자


환경 및 선수조건

  • C, C++


문제

문제 링크

  • 백준 11659번 문제
  • 문제 링크: https://www.acmicpc.net/problem/11659
  • 문제: 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.


접근법 및 풀이법

(방법1)

  • N개의 수를 배열에 입력받고 i부터 j까지의 합을 입력이 올 때마다 계산해서 반환
  • 시간복잡도: O(n^2)

(방법2)

  • Prefix sum을 구해두고 sum(i)(처음부터 i까지의 합) - sum(j-1)(처음부터 j-1까지의 합)을 통해서 반환
  • 시간복잡도: O(n)


누적합(Prefix Sum, Cumulative Sum)이란?

정의

  • 누적합(Cumulative Sum) 또는 부분합(Prefix Sum): x0, x1 … xN까지 수가 있을 때 y0=x0, y1=x0+x1 … yN=x0+x1+…+xN처럼 해당 N까지의 합을 의미합니다.
y0 = x0
y1 = x0 + x1
y2 = x0 + x1 + x2
...
yN = x0 + x1 + ... + xN

누적합의 성질

  • 특정 위치 i부터 j까지의 합은 아래의 공식으로 나타낼 수 있습니다.
S[j] - S[i-1] = a[i] + a[i+1] + ... + a[j-1] + a[j]


풀이

방법1 - O(n^2)

  • 매번 요청이 올때마다 합을 구합니다.
#include <cstdio>

#define MAX_N 100001
#define MAX_M 100001

using namespace std;

int value[MAX_N];

int main(){

    int N, M;

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; ++i){
        scanf("%d", &value[i]);
    }

    while(M--){
        int from, to;
        scanf("%d %d", &from, &to);

        int sum = 0;

        for(int i = from; i <= to; ++i){
            sum += value[i];
        }
        printf("%d\n", sum);
    }

    return 0;
}

방법2 - O(n)

  • 매번 요청이 올때마다 미리 구해놓은 sum배열을 이용해 값을 바로 반환합니다.
#include <cstdio>

#define MAX_N 100001
#define MAX_M 100001

using namespace std;

int value[MAX_N];
int sum[MAX_N];

int main(){

    int N, M;

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; ++i){
        scanf("%d", &value[i]);
        sum[i] = sum[i-1] + value[i];
    }

    while(M--){
        int from, to;
        scanf("%d %d", &from, &to);
        printf("%d\n", sum[to] - sum[from - 1] );
    }


    return 0;
}


참고자료

Find interval sum by using prefix or cumulative sum


Environment and Prerequisite

  • C, C++


Problem


Apporach and Solution

(Method1)

  • Save N numbers in array and find sum from i to j every time.
  • Time Complexity: O(n^2)

(Method2)

  • Find sum from i to j by using prefix sum.
  • sum(i)(sum of first to i) - sum(j-1)(sum of first to j-1)
  • Time Complexity: O(n)


Prefix Sum(Cumulative Sum)?

Definition

  • Cumulative Sum or Prefix Sum: prefix sum or cumulative sum is a second sequence of numbers y0, y1, y2, …, the sums of prefixes (running totals) of the input sequence:
y0 = x0
y1 = x0 + x1
y2 = x0 + x1 + x2
...
yN = x0 + x1 + ... + xN

Characteristic of prefix sum

  • Interval sum from i to j can be represented as below
S[j] - S[i-1] = a[i] + a[i+1] + ... + a[j-1] + a[j]


Solutions

Method1 - O(n^2)

  • Find sum every time when there is a query.
#include <cstdio>

#define MAX_N 100001
#define MAX_M 100001

using namespace std;

int value[MAX_N];

int main(){

    int N, M;

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; ++i){
        scanf("%d", &value[i]);
    }

    while(M--){
        int from, to;
        scanf("%d %d", &from, &to);

        int sum = 0;

        for(int i = from; i <= to; ++i){
            sum += value[i];
        }
        printf("%d\n", sum);
    }

    return 0;
}

Method2 - O(n)

  • Find sum by using prefix sum(already exist in sum array)
#include <cstdio>

#define MAX_N 100001
#define MAX_M 100001

using namespace std;

int value[MAX_N];
int sum[MAX_N];

int main(){

    int N, M;

    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; ++i){
        scanf("%d", &value[i]);
        sum[i] = sum[i-1] + value[i];
    }

    while(M--){
        int from, to;
        scanf("%d %d", &from, &to);
        printf("%d\n", sum[to] - sum[from - 1] );
    }


    return 0;
}


Reference

쉘 스크립트에서 파일이나 명령어의 결과를 while문에서 한줄 한줄 받아서 처리해보자.


환경

  • Linux 기반 시스템
  • Bash shell(/bin/bash)


방법 예제

명령어 결과를 한줄씩 처리

  • Pipeline을 이용
ls ./Test | while read line
do
	echo $line
done
ls /tmp | while read line
do
	echo $line
done


파일을 한줄씩 읽어서 처리하기

  • Redirection을 이용
while read line
do
    echo $line
done < test.txt
  • Pipeline을 이용
cat test.txt | while read line
do
    echo $line
done


참고자료