# 스택- 스택의 개념LIFO(Last In First Out)가장 최근에 들어온 원소가 가장 먼저 나오는 자료구조 - 스택을 언제 써야 하는가?가장 최근에 들어온 원소를 활용해야 하거나가장 최근에 들어온 원소 순서대로 활용해야 하는 경우에 스택을 써야 한다 - ADT?ADT(Abstract Data Type)는 추상 데이터 타입의 약어로세부 사항을 숨기고 사용자에게 필요한 기능만 명시한 것이다 - 스택의 ADT 참고 코드:https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/stack.cpp - 스택의 예시1) 함수 호출 2) 이전 페이지로 가기 3) 괄호 짝 맞추기해당 문제의 경우에닫힌 괄호를 가장 최근의 열린 괄호와 매칭하는 것이 핵심이다참고..
# 데이터 타입 크기아래의 표를 살펴보면,운영체제에 따라 데이터 타입 크기가 달라지는 것은 long과 pointer이다 # 동적 배열동적 배열은 정적 배열과 달리 런타임 중에배열의 개수를 설정할 수 있다또한, 동적 배열은 힙에 할당이 되기에 new로 생성하고반드시 delete를 해줘야 한다int size;cin >> size;int* dynamicAttary = new int[size];...delete[] dynamicArray;// 반드시 delete # 배열의 성능맨 뒤 삽입은 O(1)맨 앞 삽입은 O(N) # 문자열의 메서드- 초기화- replace (문자열 대체)- + operator (문자열 추가)- substr (부분 문자열 추출)- find (문자열 검색)- length (문자열의 길이) ..
# 알고리즘 정의수학과 컴퓨터과학에서 사용되는,문제 해결 방법을 정의한 '일련의 단계적 절차'이자어떠한 문제를 해결하기 위한 '동작들의 모임'이다.계산을 실행하기 위한 단계적 규칙과 절차를 의미하기도 한다.즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻한다.프로그램명령어의 집합을 의미하기도 한다.(출처: https://ko.wikipedia.org/wiki/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98) # 알고리즘 측정법알고리즘을 측정하는 방법은 총 2가지로 아래와 같다1. 절대시간 측정문제점:PC 환경이 모두 다르기에기준이 되는 PC 환경을 선정해서 일반화하기 어렵다따라서, 아래의 연산 횟수 측정을 사용한다 2. 연산 횟수 측정문제점:입력값에 따라 연산 횟수가 달라..
# 문제 푸는 방법유의사항최소 30분에서 1시간은 혼자 고민하면서 풀기문제를 포기하기 전 현재까지의 과정을 반드시 기록 0. 상수조건에 따른 접근 방법 생각1. 의사코드를 먼저 작성하고 구현하기그 이유는문제점과 예외를 발견하기 쉽고전체적인 큰 그림을 볼 수 있기 때문이다주의 사항은일반인도 이해 가능한 수준으로 매우 쉽게 작성해야 하고프로그래밍적 문법은 최소화해서 작성하는 것이 좋다2. 의사코드 테스트 케이스 확인 (예외 테스트 케이스 추가 확인 필수)3. 코드 작성4. 제출 전, 시간복잡도 분석하기 # 공부법답안 코드와 나의 코드를 비교하며,나의 문제점과 답안의 해결책을 정리한다그리고 답안에 사용된 알고리즘과 문제를 서로 연결해서 정리한다마지막으로, 깨달은 점을 정리한다 # 공부 주의사항아는 것만 공부하..
노드 기반 자료구조 노드 기반 자료구조는 배열의 정적 길이의 제약과중간 삽입/삭제 시간복잡도를 해결한 자료구조로 링크드리스트가 대표적이다하지만 링크드리스트도 탐색은 O(N)이 걸리기 때문에 이를 해결하기 위해1차원의 링크드리스트를 2차원 계층구조로 만든 것 트리 구조이다 트리(Tree) 노드 기반 계층구조를 가진 자료구조이다트리의 노드들은 위치에 따라 각각 부모와 자식 관계를 가지고 있다트리 관련 용어 - 루트 노드 (Root Node): 트리의 최상단 노드 - 리프 노드 (Leaf Node): 자식 정점이 없는 정점- 서브 트리 (Subtree): 특정 노드 기준으로 해당 노드의 후손 노드들 - 높이 (Height): 계층의 수- 레벨 (Level): 루트노드가 Level 0, 루트노드의 자식이 Lev..
스택과 큐는 이를 활용하는 코딩 테스트 문제가 주로 등장한다 스택(Stack) 기본적인 구조는 배열과 동일하다하지만 먼저 들어온 데이터가 나중에 나가는 구조를 가진다 스택 구현 코드더보기#define _CRT_SECURE_NO_WARNINGS#include #include enum{ FALSE = 0, TRUE = 1, MAXCOUNT = 1024};typedef struct Stack{ int Data[MAXCOUNT]; size_t Top;} Stack_t;void Push(Stack_t* InStack, int InData);int IsEmpty(Stack_t* InStack);int Pop(Stack_t* InStack);int main(void){ return 0..
배열, 가변 배열, 링크드리스트는 구현을 하는 과제에서 주로 등장한다 배열배열은 연속적인 메모리 공간에 요소들을 저장하기 때문에인덱스를 통해 상대적인 위치를 참조할 수 있다배열을 생성할 때 길이를 지정하고 길이의 변경은 불가능하다또한, 중간 삽입/삭제가 불가능하다 배열 구현 코드더보기#define _CRT_SECURE_NO_WARNINGS#include #include enum{ FALSE = 0, TRUE = 1, INVALID_INDEX = -1, MAX_COUNT = 101};typedef struct Array{ int Data[MAX_COUNT]; size_t Count;} Array_t;void Insert(Array_t* InArray, size_t InInd..
탐색 알고리즘(Search Algorithm) 자료구조 안에 저장되어 있는 특정 자료를 찾아오는 알고리즘이다대표적인 탐색 알고리즘으로는선형 탐색, 이진 탐색, 해시 기반 탐색이 있다선형 탐색(Linear Search) 자료구조의 모든 자료를 순서대로 훑어가며 특정 자료를 찾는 알고리즘이다예를 들어 반복문을 돌면서 순회하면서 찾는 경우를 의미한다 이진 탐색(Binary Search) 정렬되어 있는 자료구조에 절반씩 자료를 제거해 가며 원하는 자료를 찾는 알고리즘이다단계가 진행 될 때마다 탐색 범위가 절반씩 줄어들어서 이진 탐색이라고 부른다 선형탐색 vs. 정렬 후 이진탐색선형탐색과 이진탐색의 공간 복잡도는 같지만,시간 복잡도는 이진탐색이 O(N) 보다 빠를 수 있다따라서,탐색 빈도가 높다면, 정렬 후 이..
정렬 알고리즘자료구조로 저장된 자료들을 특정한 순서로 정렬하는 알고리즘이다정렬하기 위해서는 모든 데이터를 비교해야 한다최소 한 번씩은 모두 짚고 넘어가야 하다 보니정렬 알고리즘은 아무리 좋은 효율을 내더라도 O(N) 보다 느릴 수밖에 없다여러 가지 정렬 알고리즘이 많지만,효율은 낮지만 구현하기 쉬운 버블소트 (stable)효율이 좋지만 unstable한 퀵소트효율이 좋지만 stable한 머지소트가 대표적이다 정렬 알고리즘의 Stability정렬에서 stability(안정성)란 정렬 알고리즘이 동일한 키 값을 가진 원소들의 상대적인 순서를 유지하는 특성을 의미한다다시 말해, stability가 있는 정렬 알고리즘은동일한 값의 원소들이 정렬 전에 나열된 순서가 정렬 후에도 유지되고stablility가 없는..
자료구조(Data Structure) 자료(Data)를 저장하는 구조를 의미한다각 자료구조마다 장단점이 다르기 때문에 상황에 적절한 자료구조를 잘 선택하는 것이 중요하다자료구조의 종류 선형 자료구조와 비선형 자료구조로 구분된다선형 자료구조: 배열 / 가변배열 / 스택 / 큐 / 해시테이블 비선형 자료구조: 링크드 리스트 / 트리 / 그래프 / 힙 알고리즘(Algorithm) 특정 문제를 해결하는 증명된 방법이다모든 문제를 해결할 수 있는 알고리즘은 존재하지 않는다증명된 방법이기 때문에 굳이 해당 알고리즘 템플릿 코드를 이해하고, 암기하는 것이 중요하다 복잡도(Complexity) 알고리즘을 비교할 때, 시간과 공간을 비교하고시간 혹은 공간을 많이 사용할수록 복잡하다고 말한다복잡도에는 시간 복잡도와 공간..
