StackStack이란?LIFO: Last In First Outtop(top of pointer)를 활용하여 구현되며, stack이 비어있다면 top의 값은 -1로 되어있다후입 선출로 값을 뒤집어야 하는 상황에서 사용한다재귀 함수, 명령을 내렸다 취소(ctrl z, ctrl y), 함수나 클래스의 스택 프레임, 지역변수 등에서 사용할 수 있다스택프레임: 함수를 스택 영역에 차례대로 저장되는 함수의 호출 정보콜스택: 함수를 콜하면서 생긴 스택Caller: 함수 A에서 생성된 스택프레임Callee: 함수 B에서 생성된 스택프레임스택 프레임을 살펴보면 호출한 함수인 B의 return될 주소-> 파라미터 값 a, Jump뛸 주소 B순으로 Callee에 스택 프레임이 만들어지고, Jump뛸 주소를 꺼내 Jump..

Dangling Pointer허상 포인터란?해제된 메모리 영역을 가리키고 있는 포인터 생기는 경우메모리 해제 후, 메모리 접근포인터 캐시팅시 실패한 경우초기화를 안한 경우NULL vs nullptrNULL0번지 주소를 가르킴nullptr가르키는 공간 차체가 존재하지 않음autoauto 키워드란?타입 추론 기능컴파일 타임에 타입을 추론함타입을 추론할 수 있도록 초기화가 반드시 필요하며, 포인터일 경우 nullptr을 사용해야 함위험성함수등에서 자료형이 확정이 된다면 사용해도 괜찮지만 그렇지 않은 경우 문제가 생길 수 있음이곳저곳 auto 사용시 다른 헤더가 참조하지 않은 경우 auto가 들어가면 컴파일 순서에 따라 원치않는 자료형으로 차입이 추론되서 문제가 생길 수 있음(병렬 컴파일) 이중 연결 리스트이중..

연결리스트연결리스트란?노드라고 불리는 개체들이 포인터를 사용해 서로 연결된 자료구조배열과 다르게 연속된 메모리 공간을 사용하지 않으며, 동적으로 크기 조절 가능종류단일 연결리스트한 방향으로 연결된 연결리스트각 노드는 다음 노드를 가르키지만, 이전 노드를 가르키는 포인터 없음마지막 노드의 next 가 nullptr삽입/삭제의 시간 복잡도는 O(1)(앞)/O(N)(중간)검색, 접근의 시간 복잡도는 O(N)이중 연결리스트양방향으로 연결된 리스트각 노드는 next와 prev를 가짐삽입/삭제의 시간 복잡도는 O(1)검색, 접근의 시간 복잡도 O(N)장점앞뒤로 이동이 가능해 탐색 속도가 빠름노드 삭제시, 앞 뒤 노드를 몰라도 가능단점prev 포인터를 유지해야해 메모리 사용량 증가삽입/삭제시 포인터를 2개씩 조작해야..

inline 함수 inline 함수란?컴파일러가 호출된 위치에 해당 함수의 코드를 직접 삽입하도록 요청하는 함수함수 호출 오버헤드를 줄이고 성능을 향상시키는 데 사용 가능컴파일러가 처리함사용하는 곳 속도를 극대화해야하는 임베디드, 게임, OS등에선 사용특징함수 호출 오버헤드 감소일반적인 함수 호출은 스택에 매개변수 푸쉬, 호출 후 반환inline은 이런 과정 없이 함수의 코드 그대로 삽입되므로 오버헤드 감소컴파일러가 강제하지 않음키워드를 사용한다해서 반드시 인라인 확장이 되는것이 아님컴파일러는 함수의 크기, 최적화 전략을 고려해 인라인 확장 수행 결정헤더파일에서 정의될 수 있음헤더파일에서 정의해 여러번 포함되더라도 중복 정의 오류 발생하지 않음단점바이너리 코드 증가(Code Bloat)호출되는 곳마다 코..

선형 자료구조선형 자료구조란?데이터가 순차적으로 나열되어있는 형태종류배열스택큐연결 리스트Deque비선형 자료구조비선형 자료구조란?데이터가 순차적으로 나열되어 있지 않은 형태종류트리그래프힙Trie포인터포인터란?자기가 가지고 있는 값을 가리켜 그 공간을 사용하도록 하는 것포인터 메모리 32비트 체계에선 램을 4기가까지만 사용 가능한데 2^32를 계산했을때 대략 4.2기가 정도만나오고, 포인터가 가리킬 수있는 양이 32 비트로 충분하기 때문에 4바이트를 크기로 사용함하지만 컴퓨터가 발전하면서 비트 체계가 64로 넘어가면서 8바이트로 바뀜 32비트 : 4바이트64비트 : 8바이트Bitbit0아니면 1 한가지 상태를 가질 수 있는 단위byet8bit = 1byte0~255까지 총 256가지의 숫자 값을 표현할 수..

- 정의- 그래프에서 최단 거리를 구하는 알고리즘- 특징- 모든 노드간 최단 경로 탐색을 한다- 음수 가중치 Edge가 있어도 수행이 가능하다- 동적 계획법의 원리를 이용해 알고리즘에 접근한읻- 시간 복잡도는 O(V^3)로 노드의 갯수가 많아질수록 매우 느리다- 따라서 노드의 갯수가 적은 문제에 적합(?)- 핵심 이론- A노드에서 B노드까지 최단 경로를 구했다 가정했을 때, 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다- - ex) 최단 경로가 파란색 선으로 되어있을 때 1~4까지 가는 최단 경로는 1->3->4로 최단경로가 1->2->4처럼 다른 방법으로 가는것이 될 수 없다점화식 D\[S\]\[E\] = Math.min(D\[S\]\[E\], D\[S\]\[..

정의최단거리를 구하는 알고리즘특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다음수 갖우치가 에지에 있어도 수행할 수 있다전체 그래프에서 음수 사이클 존재여부를 판단할 수 있다시간 복잡도는 O(VE)핵심 이론에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 하기에지를 중심으로 동작하므로 에지 리스트로 구현한다출발 노드는 0, 나머지는 무한대로 초기화 해준모든 에지를 확인해 정답 리스트 업데이트하기업데이트 반복 회수는 노드 개수 -1로 노드 개수가 N개이고 음수 사이클이 없을 경우 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수가 N-1이기 때문이다모든 에지 E =(s,e,w)에서 다음 조건을 만족하면 업데이트를 실행한다D[s] != INF && D[e] > D[s] + w..

정의그래프에서 최단거리를 구하는 알고리즘특징출발 노드와 모든 노드간의 최단 거리를 탐색한다에지는 모두 양수이다시간 복잡도는 O(ElogV)이다(V:노드 수, E:에지 수)핵심이론그래프를 인접 리스트로 구현해 줄것인데, 그래프의 연결을 표현하기 위해 리스트에 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 만들어준다(시간복잡도 측면, N의 크기가 클것에 대비하여 인접 행렬보다 인접 리스트가 유리하다) 최단거리 배열을 반들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화하는데, 이때 무한은 적당히 큰 값으로 사용하면 된다최단거리 배열에서 현재 값이 가장 작은 노드를 고르는데 값이 0인 출발 노드에서 시작한다선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트 한다처음에 저장해 둔 ..

정의 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 항상 유일한 값으로 정렬되지 않는다 시간 복잡도는 O(V+E)이다 (노드수 V, 에지 수 E) 핵심 이론 진입차수는 자기 자신을 가르키는 에지의 갯수로, 그래프를 인접 리스트로 구현한 뒤, 실시간으로 진입 차수 배열을 초기화해준다 진입 차수가 0인 노드를 선택 후 정렬 배열에 저장한 뒤, 인접리스트에 연결된 값의 진입 차수를 1씩 빼준다 선택한 노드를 제외한 노드 중 진입 차수가 0인 노드를 다시 선택해준 뒤 위의 작업을 반복해준다 이때 2,3번 노드의 값이 둘다 0이므로 어떤것이 먼저 배열에 들어가도 상관이 없으므로 항상 유일 값으로 정렬되지 않는것을 볼 수 있다 모든 배열이 정렬되면 위와같은 결과를 볼 수 있다