//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 자료구조 15강 스택: 삽입과 삭제가 한쪽 끝에서 이루어지는 리스트의 일종 삽입과 삭제가 일어나는 쪽을 스택의 top이라고 부름 LIFO: 가장 나중에 들어간 애가 가장 먼저 나옴 스택이 지원하는 연산 push: 스택에 새로운 원소를 삽입하는 연산 pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환 peek: 스택의 top에 있는 원소를 제거하지 않고 값만 반환 → 스택은 변화 없음 is_empty: 스택이 비었는지 검사 배열을 이용한 스택의 구현 //int를 Item으로 부르겠다: 코드의 재사용성을 높이기 위해 typedef int Item; //*Stack이 가리키고 있는 장소에 있는 데이터의 타입이 st..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 미로 찾기 - 스택 2차원 NxN 배열 입구는(0, 0), 출구는 (N-1, N-1) 다음을 반복 현재 위치에 방문했다는 표시를 해서 무한 루프를 방지 현재 위치가 출구라면 종료 현재 위치에서 일정한 규칙으로 다음 위치로 이동 북→동→남→서 순서로 이동 아직 안 가본 위치이고 && 벽이 아니고 && 미로의 외부가 아니면 이동 만약 북, 동, 남, 서 어디로도 이동하지 못했다면 현재 위치에 도달하기 직전 위치로 이동한다. 만약 돌아갈 위치가 없다면 원래 길이 없는 미로 어떻게 돌아갈 것?? ⇒ 스택을 사용해서 현재 위치를 스택에 push하고 다음 위치로 이동 → 스택의 top에는 항상 직전 위치가 저장 이동할 수 ..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 후기 표기식으로 변환 - 괄호 있는 경우 여는 괄호는 무조건 스택에 push ~ 이때 스택 내의 어떤 연산자도 pop X 어떤 연산자를 스택에 push 할 때 스택의 top에 여는 괄호가 있으면 아무도 pop하지 않고 그냥 push 닫는 괄호가 나오면 스택에서 여는 괄호가 나올 때 까지 pop 해서 출력 ~ 닫는 괄호는 스택에 push X 2. 괄호가 있는 후기 표기식으로의 변환 코드 // infix_to_postfix.c #include #include "stackADT.h" struct stack_type{ Item *contents; //배열 int top; //스택의 top을 가리키는 변수 int size..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. infix expression → post expression 중위(infix) 표기식은 연산자들 간의 우선순위도 고려해야 한다. 후위(postfix) 표기식은 피연산자는 스택에 push, 연산자가 나오면 pop 7 - 4 * 3 * 1 + 5 = 7 4 3 * 1 * - 5 + = 0 중위 표기식 보다 간단하다. 그래서 중위 표기식 입력 → 후기 표기식으로 변환 후기 표기식에서는 (중위 표기식과 다르게) 괄호가 없다. 연산자는 등장하는 순서대로 계산 중위, 후위 모두 피연산자의 순서는 보존 후위는 중위에 비해 연산자가 뒤로 이동 2. 후위 표기식으로 변환 - 괄호 없는 경우 중위 표기식을 처음부터 순서대로 읽으..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 후위 표기식(postfix expression) 중위 표기식: 연산자가 피연산자의 사이에 들어감, 일반적으로 사용하는 수식의 표기법 4 x ( 7 + 2 ) = 36 후위 표기식:연산자가 피연산자 뒤에 나옴 4 7 2 + x = 36 연산자가 나오면(+) 연산자 바로 앞의 두 피연산자(7, 2)를 계산하고 → 4 9 x : 연산자가 나오면(x) 연산자 바로 앞의 두 피연산자(4, 9)를 계산 = 36 2. 후위 표기식 계산 방법 모든 피연산자는 양의 정수라고 가정 모든 연산자와 피연산자 사이에는 공백 문자가 있다고 가정 (1) 정수형 빈 스택을 생성 (2) while(토큰이 남아있을 때) (3) 다음 토큰으로 이..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 문제점 만약 스택이 동시에 2개 이상 필요하다면? ⇒ 하나의 함수로 문제를 해결하기 위해서는 push(), pop() 등의 함수가 매개변수로 stack을 받아야 한다. Stack s1 = create(); Stack s2 = create(); push(s1, 12); push(s2, 9); 2. stackADT.h // stackADT.h #ifndef STACKADT_H #define STACKADT_H #include #include //re-definition, 별명을 만들어 줌, int를 Item이라고 부르겠다. typedef int Item; typedef struct stack_type *Stack; ..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 배열을 이용한 스택의 구현 //stack.c #define MAX_CAPACITY 100 int is_full(); //문자들을 저장하는 스택 //스택에 저장되는 데이터의 타입을 문자(char)라고 가정 char stack[MAX_CAPACITY]; //스택의 top을 표시하는 변수 ~ 스택의 어디까지 데이터가 차 있다를 표시 int top = -1; //-1은 실제 스택 데이터의 위치를 반영 //새로운 데이터를 추가 함수 void push(char ch){ if(is_full()) //스택이 가득차면 push할 수 없다. return; top++; stack[top]=ch; //만약 int top=0;으로 시작..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 1. 스택(Stack) 스택은 일종의 리스트 일반 리스트: 아무 곳에서나 삽입/삭제 가능 스택: 삽입과 삭제가 한 쪽 끝에서만 이루어짐 삽입과 삭제가 일어나는 쪽을 스택의 top 이라고 부름 LIFO(Last-In, First-Out): 가장 나중에 들어간 애가 가장 먼저 나옴 2. 스택이 지원하는 연산 push: 스택에 새로운 원소를 삽입하는 연산 pop: 스택의 top에 있는 원소를 스택에서 제거하고 반환 peek: 스택의 top에 있는 원소를 제거하지 않고 반환 → 스택은 변화 없음 is_empty: 스택이 비었는지 검사 3. 스택 응용: 괄호 검사 문제 입력 수식의 괄호가 올바른지 검사 [a + b * { c ..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 자료구조 11강 배열 연결 리스트 노드(데이터 필드 + 링크 필드)들이 링크로 연결되어 있는 자료구조 첫 번째 노드를 저장하는 head 노드, 마지막 노드의 링크 필드는 NULL ~ 연결 리스트의 끝 표시 노드 typedef struct node{ char *data; //연결 리스트에 저장할 데이터 타입 지정 struct node * next; //다음 노드의 주소를 저장할 필드, 자기 참조형 구조체 }Node; Node *head = NULL; //연결 리스트의 첫 번째 노드의 주소를 저장할 포인터 자기 참조형 구조체: 자신과 동일한 구조체에 대한 포인터를 멤버로 가진다. struct node *next: stru..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 0. 실행 예 Data file name? - 프로그램을 실행하면 어떤 데이터 파일을 load 할지 물어본다. 입력 없이 Enter를 치면 데이터 파일로부터 데이터를 읽지 않고 프로그램을 실행 status - 저장된 모든 노래의 번호, 가수, 제목, 파일의 경로명을 출력 노래의 번호는 입력 순서대로 번호 할당 출력 시 가수 이름 알파벳 순으로 출력 동일한 가수 이름이면 노래 제목으로 알파벳 순으로 출력 add - 가수 이름, 제목, 파일명으로 추가 파일명은 지정하지 않아도 된다. search - 가수 이름과 노래 제목으로 검색 제목 없이 가수 이름만 검색해도 된다. play 4 - 4번 노래를 play remove 6..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 0. 실행 예 Data file name? - 프로그램을 실행하면 어떤 데이터 파일을 load 할지 물어본다. 입력 없이 Enter를 치면 데이터 파일로부터 데이터를 읽지 않고 프로그램을 실행 status - 저장된 모든 노래의 번호, 가수, 제목, 파일의 경로명을 출력 노래의 번호는 입력 순서 대로 번호 할당 출력 시 가수 이름 알파벳 순으로 출력 동일한 가수 이름이면 노래 제목으로 알파벳 순으로 출력 add - 가수 이름, 제목, 파일명으로 추가 파일명은 지정하지 않아도 된다. search - 가수 이름과 노래 제목으로 검색 제목 없이 가수 이름만 검색해도 된다. play 4 - 4번 노래를 play remove ..

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎 0. 실행 예 Data file name? - 프로그램을 실행하면 어떤 데이터 파일을 load 할지 물어본다. 입력 없이 Enter를 치면 데이터 파일로부터 데이터를 읽지 않고 프로그램을 실행 status - 저장된 모든 노래의 번호, 가수, 제목, 파일의 경로명을 출력 노래의 번호는 입력 순서 대로 번호 할당 출력 시 가수 이름 알파벳 순으로 출력 동일한 가수 이름이면 노래 제목으로 알파벳 순으로 출력 add - 가수 이름, 제목, 파일명으로 추가 파일명은 지정하지 않아도 된다. search - 가수 이름과 노래 제목으로 검색 제목 없이 가수 이름만 검색해도 된다. play 4 - 4번 노래를 play remove ..