교수님 저는 말하는 감자입니다.
교수님 저는 말하는 배터리입니다.
빅오 크기 비교:
1 < logn < n < nlogn < n^2 < n^3 < n^k < 2^n < n!
[예시1] int algorithm(int n){ int k = 0; while (n > 1){ n = n/2; k++; } return k; } [결과] O(logn) - [예시2] sub함수의 시간복잡도가 O(n)일때 for(i = 1; i < n; i *= 2) sub(); 의 시간복잡도는? [답] O(nlogn)
A. 스택
: LIFO (후입선출)
// 오류 처리 함수
inline void error(char *message){
printf("%s\n", message);
exit(1);
}bool isEmpty(){ return top == -1 }
bool isFull(){ return top == MAX_STACK_SIZE-1; }void push (int e){
if (isFull()) error("스택 포화 에러");
data[++top] = e;
}
int pop(){
if (isEmpty()) error("스택 공백 에러");
return data[top--];
int peek(){
if (isEmpty()) error("스택 공백 에러");
return data[top];[괄호검사 프로그램]
FILE *fp = fopen(filename, "r");
if(fp == NULL) error("Error!\n");
while ((ch = getc(fp)) != EOF{...}- 중위표기 수식 -> 후위표기 수식 변환
- 연산자(operator) 스택
- 후위표기 수식 -> 계산
- 피연산자(operand) 스택
[ungetc()]: 방금 읽은 문자를 입력 버퍼로 되돌려줌
else if (c >= '0' && c <= '9'){
ungetc (c, fp);
double val;
fscanf (fp, "%lf", &val);
st.push (val);
}[ INFIX TO POSTFIX ]
- 피연산자(숫자) 만나면 그대로 출력
- 연산자(op)를 만나면
: 입력op의 우선순위가 스택op의 우선순위보다- 같거나 낮으면 pop하고 출력하고 입력op 스택에 push
- 높으면 입력op를 push
- 왼쪽 괄호는 스택에 push
- 오른쪽 괄호는 스택에서 왼쪽 괄호 위에 쌓여있는 모든 연산자를 출력
int precedence (char op){
switch (op){
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
}
return -1;
}[미로 탐색]
bool isValidLoc (int r, int c){
if (r < 0||c < 0||r >= MAZE_SIZE||c >= MAZE_SIZE)
return 0;
else return map[r][c] == '0' || map[r][c] == 'x';B. 큐
: FIFO (선입선출)
- 선형 큐의 문제점: 삽입을 위해서는 O(n)의 시간이 걸림
- 원형큐: 공백/포화 상태 구별을 위해 한칸을 비워둔다
- 공백상태: front == rear
- 포화상태: front = (rear + 1) % M
void enqueue (int val){ // 큐에 삽입
if (isFull()) error("포화!\n");
else{
rear = (rear + 1) % MAX_QUEUE_SIZE;
data[rear] = val;
}
}
int dequeue (){ // 첫 항목을 큐에서 빼서 반환
if (isEmpty()) error("공백!\n");
else{
front = (front + 1) % MAX_QUEUE_SIZE;
return data[front];
}
}C. 덱
: 최근에 들어온 걸 우선순위를 주고 싶을 때
[원형덱]
class CircularDeque: Public CircularQueue{
public:
CircularDeque() {}
void addRear(int val){ enqueue(val); }
int deleteFront(){ return dequeue(); }
int getFront(){ return peek(); }
void display(){ // CQ의 display() 재정의
int maxi = (front < rear) ? rear: rear + MAX_Q_SIZE;
for(int i = front + 1; i <= maxi; i++)
printf("[%2d] ", data[i % MAX_Q_SIZE]);
}
int getRear(){
if (isEmpty()) error("공백!\n");
else return data[rear];
}
void addFront(int val){
if (isFull()) error("포화!\n");
else{
data[front] = val;
front = (front - 1 + MAX_Q_SIZE) % MAX_Q_SIZE;
}
}
int deleteRear(){
if (isEmpty()) error("공백!\n");
else{
int ret = data[rear];
rear = (rear -1 + MAX_Q_SIZE) % MAX_Q_SIZE;
return ret;
}
}
}D. 연결 리스트
- 포인터
- &: 변수의 주소 추출
- *: 포인터가 가리키는 곳의 내용 추출
[자기 참조 구조체]
typedef struct ListNote{
char data[10];
struct ListNode* link;
} Node;- 포인터는 NULL로 초기화하자! ( int* p = NULL; )
- 연결리스트의 삽입/삭제 시간복잡도: O(1)
- 내가 가리키는 노드의 바로 앞 노드를 알고자 한다면
- Singly: O(n)
- Doubly: O(1)
// 소멸자
~LinkedStack(){ while(!isEmpty()) delete pop();}E. 리스트
: 자료의 접근 위치 - 임의의 위치에서도 삽입/삭제 가능
: 배열로 - 삽입삭제시 오버헤드
: 연결리스트로 - 삽입/삭제 효율적.
a) 배열로 구현한 리스트
- 생성자에서 length = 0 설정
- 공백: length == 0;
- 포화: length == MAX_L_SIZE;
- a.k.a. 밑빠진독
: 배열이 꽉 찼는데 삽입 하고 싶으면 앞으로 n-1개 옮기고 n번째에 넣기 - O(n)
void insert( int post, int e ){
if (!isFull() && pos >= 0 && pos <= length){
for(int i = length; i > pos; i--)
data[i] = data[i-1];
data[pos] = e;
length++;
}
else error("포화 또는 삽입 위치 오류!");
}
-
void remove( int pos ){
if (!isEmpty() && 0 <= pos && pos < length){
for (int i = pos + 1; i < length; i++)
data[i - 1] = data[i];
length--;
}
else error("공백 또는 삭제 위치 오류!");
}
int getEntry( int pos ){ return data[pos]; }
-
bool find( int item ){
for (int i = 0; i < length; i++){
if( data[i] == item) return true;
return false;
void replace(int pos, int e){
data[pos] = e;
}
-
// 기출변형 1: item의 인덱스 찾아주는 함수
int where( int item ){
for ( int i = 0; i < length; i++ ){
if ( data[i] == item ) return i;
}
return -1;
}
-
// 기출변형 2: item을 찾아서 e로 바꿔주는 함수 // 수정 필요!!!
void findAndReplace( int item, int e){
for( int i = 0; i < length; i++ ){
if ( data[i] == item ) data[i] = e;
}
}
b) 연결리스트로 구현한 리스트
by 단순 연결 리스트
- 하나의 링크필드 이용
- 마지막 노드의 링크값은 NULL
[노드 클래스] 에서
-
#include<iostream>
class Node {
Node* link;
int data;
public:
Node(int val = 0) : data(val), link(NULL){} // 멤버를 초기화
Node* getLink() { return link; }
void setLink(Node* next) { link = next; }
void display() { printf("<%2d>", data); }
bool hasData(int val) { return data == val; }
void insertNext(Node* n) {
if (n != NULL) {
n -> link = link;
link = n;
}
}
Node* removeNext() {
Node* removed = link;
if (removed != NULL)
link = removed -> link;
return removed;
}
};
-
-
[연결리스트 클래스] 에서 // 수정 필요
-
void clear(){
while(!isEmpty())
delete remove(0);
}
-
Node* getEntry(int pos){
Node* n = &org;
for (int i = -1; i < pos; i++, n = n -> getLink())
// i = -1
if (n == NULL) break;
return n;
}
코딩천재