supersumin 님의 tistory

Non-linear data structureData structure의 유형은 linear 구조와 non-linear 구조로 나뉜다. 두 구조의 차이는 데이터 간의 연결 방식과 접근 방식에 있다.linear 구조: 데이터가 일렬로 나열되어 있으며, 앞에서부터 차례대로 inedx를 통해 순서대로 접근한다. (배열, 스택, 큐)non-linear 구조: 구조가 나무처럼 가지가 뻗어나가거나, 도로처럼 서로 연결된 구조이다. 순차적인 접근이 아닌 연결 관계를 따라 탐색한다. (트리, 그래프)접근 방식이 복잡하더라도 non-linear 구조를 사용하는 이유는 현실 세계의 데이터와 관계가 비선형적이기 때문이다. 예를 들어, 도시와 도시 간의 도로망, 사람들 간의 친구 관계처럼 계층적인 관계를 표현할 때 non-l..

Queue란?Queue는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 구조이다.Queue의 구조데이터를 넣으면 rear 쪽으로 들어가고, 데이터를 꺼낼 때는 front 쪽에서 나온다. 하나가 들어가면 꼬리가 길어진다.Queue의 UsageQueue는 FIFO 특성 덕분에 요청을 순서대로 공정하게 처리해야 하는 상황에서 유용하게 사용된다.Task scheduling: 요청이 들어온 순서대로 처리해야 공정하고 예측 가능한 시스템이 된다.Networking: 라우터나 스위치 등은 패킷이 들어오는 순서대로 전송해야 하므로 순서 보장이 중요하다.Customer service: 고객의 요청을 접수한 순서대로 처리하는 것이 공정하다. Queue 구현: array 기반전역 변수 선언#define MAX_SIZ..

Stacks이란?Stack은 자료를 차곡차곡 쌓는 구조로 LIFO(Last In, First Out) 구조를 가진다. Linked list도 있는데 stack을 쓰는 이유는 함수 호출 순서를 저장할 때와 같이 LIFO 구조가 유리한 경우가 존재하기 때문이다.Stack의 usage(활용)Stack이 LIFO 구조를 따르기 때문에 가장 나중에 넣은 것을 먼저 꺼내야 하는 상황에서 유용하다.Undo operation (되돌리기 기능): 텍스트 편집기에서 Ctrl+Z와 같이 사용자가 수행한 작업을 stack에 저장해두고 되돌릴 때는 가장 최근 작업부터 순서대로 복원한다.Expression evaluation (수식 계산): 계산 중간값이나 연산자를 stack에 쌓아두고 적절한 시점에 pop하여 계산을 수행한다...

Signly linked listsBackgroundTypedeftypedef는 C/C++에서 사용자가 정의한 자료형에 새로운 이름을 부여하여 복잡한 자료형 이름을 선언할 때 간단하게 만드는 데 사용된다.struct Person { char name[50]; int age;};struct Person p1;struct를 직접 사용할 때는 struct Person이라고 매변 명시한 뒤 변수명 p1을 선언해야 한다.typedef struct { char name[50]; int age;} Person;Person p1;typedef를 통해 사용자 지정 struct 변수를 선언할 때 struct 키워드 없이 간단하게 사용할 수 있다. Dynamic memory allocationRAM에서..

Time complexity알고리즘의 연산량이 얼마나 걸리는지에 대한 척도를 나타낸다.Complexity 계산 방법Complexity를 계산할 때는 input size(입력 크기)가 매우 큰 경우을 가정한다.차수가 가장 큰 것만 중요하며 나머지 항들은 무시한다.Condfficient(계수)나 더해지는 상수는 무시한다.Notation 종류Big-O natation: Upper bound(worst case)최악의 경우의 알고리즘 성능을 나타낸다. time complexity의 상한을 보장한다.Big-Ω notation: Lower bound(best case)최선의 경우의 알고리즘 성능을 나타낸다. time complexity의 하한을 보장한다.Big-θ notation: Tight bound(best&w..

ListsArray와 List의 차이Array: RAM에서 연속적인 address에 저장된다. 크기가 고정적이며 프로그램 실행 전에 미리 할당해야 하는 경우가 많다.List: 각 요소(Node)가 다른 memory에 위치하며 각 요소는 pointer로 연결된다. 크기를 유동적으로 조절 가능하며 삽입 및 삭제 작업이 자유롭다.List의 node 구성Node는 Linked List와 같은 자료 구조에서 사용되는 각 element를 의미한다.Node는 value와 pointer로 구성된다.Structers (구조체)user가 정의한 data type이다.sizeof(Structure)는 구조체 내 멤버들의 크기의 합이 아니다그 이유는structure를 선언할 때 compiler에 의해 Alignment Rul..

Constant(상수) 란?C언어에서 상수란 일반적으로 변경할 수 없는 값이다. Literal Constant(일반 상수)숫자와 문자같이 고정된 값이다.Ex codeint x = 30; // x는 30이라는 value를 가지는 int type 변수const int y = 12; // y는 12라는 value를 가지는 int type 변수이며, 이는 바꿀 수 없다.y = 15; // Error 발생 포인터 상수 (Pointer Constant) vs. 상수 포인터 (Constant Pointer) Pointer Constant(포인터 상수, int *const ptr)Pointer 자체가 Constant로 pointer로 가리키는 주소를 변경할 수 없다는 뜻이다.Constant Point(상수 포인터, ..

Array란?Array는 memory에 연속적으로 저장되는 elements의 집합으로, index와 element의 pair로 구성된다.Example codeint array[6]; // create: array 선언은 data type과 sizearray[1] = 100; // set: array 한 element에 값을 저장int value = array[1]; // get: array에서 값을 가져오기 Array의 index 접근 방식은 pointer 연산과 동일하게 동작(+ sizeof)Array는 memory에 연속적으로 저장된 elements의 집합이다. Array는 어떻게 여러 element에 접근할 수 있을까? Array의 이름은 첫 번째 element의 address를 의미하며,..

Recursion의 기본 구조Recursion은 함수가 자기 자신을 호출하는 구조이며 호출에 필요한 메모리는 stack에 저장되기 때문에 메모리 관리에 유의해야 한다. 함수가 너무 많이 호출되면 Stack Overflow가 발생할 수 있다.  Recursion의 두 가지 핵심 요소 Call Myself: 자기 자신을 호출하는 부분 Terminate Condition: 종료 조건 Recursion 예시Factorial calculationfactorail은 점점 수를 낮추며 곱하는 것이므로 받은 n값에 대해 자기 자신을 곱해주는 함수를 호출하여 곱해준다.그러다 n=0인 경우는 1도 반환해준다. 이는 terminate condition이다.#include using namespace std;// define..

malloc과 calloc과 같은 동적 메모리 할당을 사용하는 이유는 프로그램 실행 중에 변화하는 변수나 데이터의 크기를 유연하게 관리할 수 있기 때문이다. 또한 한정된 메모리를 유동적으로 할당하고 해제할 수 있기 때문이다. 이를 자세히 알아보자.1. 코드 실행 중 메모리가 변화?코드 실행 중 메모리 크기가 변동하는 경우는 프로그램을 짜는 도중에 변수의 크기를 정할 수 없다. 예를 들어 배열의 크기가 사용자가 제시한 크기만큼 실시간으로 할당받아야 한다면 프로그램을 짜는 도중에는 배열의 크기를 정할 수 없다. 그렇기 때문에 사용자에 입력에 따라 변수의 데이터 크기를 다르게 받을 방법 중 하나가 동적할당인 것이다.malloc을 사용해 동적할당을 수행한 모습이다. 이를 통해 사용자가 원하는 크기만큼 유연하게 ..