알고리즘과 자료구조는 서로 다른 하나의 과목임에 불구하고 밀접한 연관이 있다.
자료구조를 공부하기전 알고리즘의 성능분석을 알아보고 자료구조를 사용할 때 어떤 알고리즘의 성능이 좋고 비용이 낮은지 살펴보자.
알고리즘의 성능분석에는 2가지 측면이 있다.
1. 시간 복잡도 : 속도에 해당하는 알고리즘의 수행시간 분석결과
2. 공간 복잡도 : 메모리 사용량에 대한 분석결과
일반적으로 알고리즘을 평가할 떄는 메모리의 사용량보다 실행속도에 초점을 둔다.
그렇다면 어떻게 속도를 측정할까?
알고리즘의 수행속도를 평가할 떄는 연산의 횟수와 처리해야 할 데이터의 수 n에 대한 연산횟수의 함수 T(n)을 구성한다.
함수를 잘 구성해 놓으면 데이터 수의 증가에 따른 연산횟수의 변화 정도를 파악함으로써 속도를 측정해 볼 수 있다.
알고리즘의 시간 복잡도를 계산하기 위해서는 코드에서 핵심이 되는 연산이 무엇인지 잘 판단해야한다. 그러나 쉬운 일은 아니다.
또한 알고리즘을 평가하는데 있어서 최선의 경우보다는 최악의 경우를 기준으로 성능을 평가한다. 그 이유는 어떠한 알고리즘이라도 최선의 경우만 나오기 힘들고 최악의 경우가 나올 확률도 배제할 수 없기 때문이다. 예측불가능 한 경우에는 최악의 경우를 선택하는 것이 계산하기도 편리하고 데이터의 수가 굉장이 많다면 최선보다는 최악을 선택하는 것이 최선과 최선의 성능 범주를 아우를 수 있다.
빅-오 표현법(Big-Oh Notation)
사실 데이터의 수 n과 그에 따른 시간 복잡도 함수 T(n)을 정확히 구하는 것은 쉽지않다. 이를 위해 어느정도의 오차는 무시하고 데이터 수의 증가에 따른 연산횟수의 증가 형태 또는 증가율의 상한선을 표현한 것이 빅-오 표현법이다.
C/C++
2013년 1월 30일 수요일
2013년 1월 14일 월요일
[C] (*ptr).xpos 와 ptr->xpos
구조체가 이렇게 정의되어 있다.
typedef struct point
{
int x;
int y;
}Point;
정의한 구조체를 이용하여 변수와 구조체를 가르킬수 있는 포인터를 만들자
Point p1;
Point *ptr = &p1;
그렇다면 여기서 구조체의 멤버변수의 초기화를 하자
첫 번째 방법
(*ptr).x = 10;
(*ptr).y = 20;
두 번째 방법
ptr->x = 10;
ptr->y = 20;
둘다 같다!!!
자료구조에서는 아래 두 번째 방법을 많이 사용함으로 잘 알고 있어야한다!
typedef struct point
{
int x;
int y;
}Point;
정의한 구조체를 이용하여 변수와 구조체를 가르킬수 있는 포인터를 만들자
Point p1;
Point *ptr = &p1;
그렇다면 여기서 구조체의 멤버변수의 초기화를 하자
첫 번째 방법
(*ptr).x = 10;
(*ptr).y = 20;
두 번째 방법
ptr->x = 10;
ptr->y = 20;
둘다 같다!!!
자료구조에서는 아래 두 번째 방법을 많이 사용함으로 잘 알고 있어야한다!
2013년 1월 6일 일요일
[C]에서 많이 사용되는 문자열 관련 함수
#include<stdio.h>
size_t strlen(const char* s);
인자로 전달된 문자열의 길이를 반환하는 함수(널문자 제외)
char* strcpy(char* dest, const char* src);
char* strncpy(char* dest, const char* src, size_t n);
문자열을 복사하는 함수(n은 n만큼의 문자 수만큼 복사를 진행을 의미, 널문자 제외)
char* strcat(char* dest, const char* src);
char* strncat(char* dest, const char* src, size_t n);
문자열을 덧붙이는 함수(n은 n만큼의 문자 수만큼 덧붙이라는 의미, 널문자 제외)
int strcmp(const char* s1, const char* s2);
int strncmp(const char* s1, const char* s2, size_t n);
문자열을 비교하는 함수(n은 n만큼의 문자 수만큼 비교하라는 의미, 널문자 제외)
int atoi(const char* str);
long atol(const char* str);
double atoi(const char* str);
문자열의 내용을 정수, 실수로 바꿔주는 함수
[C] 입출력 함수
#include<stdio.h>
int putchar(int c);
int fputc(int c, FILE* stream);
모니터로 하나의 문자를 출력.
fputc()함수를 이용하면 모니터 뿐만 아니라 파일에 문자 하나를 저장 할 수 있다.
int getchar();
int fgetc(FILE* stream);
키보드로부터 하나의 문자를 입력받는 함수이다.
위와 마찬가지로 fgetc();를 이용하면 파일로부터 문자 하나를 읽어 들일 수 있다.
문자 입출력에서 EOF란 end of file의 약자로서 파일의 끝을 나타내는 상수(-1)이다.
지금까지는 문자 하나를 입력하고 출력하는 함수였고
다음은 문자열 단위 입출력 함수를 알아보자.
#include<stdio.h>
int puts(const char* s);
int fputs(const char* s, FILE* stream);
모니터로 하나의 문자열을 출력하는 함수이다.
char* gets(char* s);
char* fgets(char*s, int n, FILE* stream);
문자열 입력 함수이다.
중요한 점은 gets()함수는 문자열 길이에 상관없이 메모리의 범위를 넘어서까지 읽어버리기 때문에 fgets()함수를 이용하는 것이 좋다.
n의 수에 따라 최대로 읽어 들이는 길이를 제한할 수 있는데 만약 n이 7이라면 6개의 문자로 이루어진 문자열에 널문자까지 포함하여 총 7문자를 읽어 들이는 것이 특징이다.(즉, 자동 널문자 추가)
[C] 버퍼
입력과 출력이 되기 전 항상 데이터 스트림에 버퍼, 즉 임시메모리가 존재하고 여기에 데이터가 임시적으로 담기게 된다.
모든 데이터는 이러한 버퍼를 통하여 데이터 스트림을 형성하는 것이다. 그렇다면 왜 버퍼가 존재할까? 그것은 일련의 데이터를 모아서 한꺼번에 출력이나 입력을 처리하는 것이 하나하나의 데이터를 처리하는 것보다 더 효율적이기 때문이다.
따라서 프로그램과 CPU자원을 효율적으로 사용할 수 있긴한데 이 버퍼 때문에 생기는 문제점도 적지 않다. 때문에 버퍼를 비워야하는 일이 생기기 마련이다.
그럴때 사용하는 함수는 fflush(stdout); 함수로서 출력버퍼의 내용을 비움과 동시에 모니터로 출력시켜버린다.
그렇다면 입력버퍼는 어떻게 비울것인가?
번거롭지만 함수를 하나 만들어 문자나 데이터를 하나하나 읽어서 비우는 것이 좋다.
fflush(stdin);함수를 사용하여 버퍼를 비울수 있는 컴파일이 존재하긴 하나 표준으로 제공하는 함수가 아니기 때문에 안전하지 않다.
따라서 다음과 같은 함수를 만들어 사용하면 된다.
void ClearLineFromReadBuffer(){
while(getchar() != '\n');
}
잘 알아두고 잘 써먹도록 하자!
피드 구독하기:
글 (Atom)