# 그리디 알고리즘이란?매 순간 가장 좋아 보이는 답을 선택해서특정 조건이 만족하는 경우 최적해를 보장하는 알고리즘이다 # 그리디 알고리즘의 특성아래의 두 가지 특성이 지켜져야그리디 알고리즘을 사용할 수 있다1. 탐욕적 선택 속성각 단계에서 가장 좋은 것을 선택한 것이다음 해를 구하는데 영향을 주지 않아야 한다 (독립적) 2. 최적 부분 구조문제의 최적 해결책이 하위 문제의 최적 해결책으로구성되는 경우를 의미한다예를 들어,현재 해(N의 해)를 구할 때, 이전 해(N-1의 해)로 해결 가능한 경우이다 # 예시 1 - 동전 거슬러주기문제 1) 해결)가장 적은 동전 개수로 거슬러 주기 위해서화폐가 큰 동전부터 최대한 활용하면 되지 않을까?이는 곧 정답으로 그리디 알고리즘을 사용하니 풀렸다 문제 2) 해결)문제..
#동적계획법이란?복잡한 문제를 단순한 하위 문제로 나눠서 접근하는 방법이고중복 계산을 줄이기 위해, 이전에 구한 해를 활용한다 #동적계획법을 써야 하는 문제의 기준동적계획법을 사용해야 하는지 판단하는 기준은아래의 두 조건을 모두 만족하면 동적계획법을 사용하면 된다1. 최적부분 구조 문제 (Optimal Substructure)2. 중복부분 문제 (Overlapping Subproblems) 최적부분 구조는문제의 최적 해결책이 하위 문제의 최적 해결책으로구성되는 경우를 의미한다예를 들어현재 해(N의 해)를 구할 때, 이전 해(N-1의 해)로 해결이 가능한 경우이다 중복부분 문제는동일한 하위 해가 여러 번 중복되어 계산되어 활용되는 경우를 의미한다예를 들어해를 구할 때마다 이전에 사용했던 해가 중복해서 사용..
# 정렬의 의미데이터를 특정 기준에 따라서 순서대로 배치하는 것을 의미한다ex. 오름차순(점점 값이 커지는), 내림차순(점점 값이 작아지는),... # 코테에서 정렬이 필요한 이유특정 알고리즘을 사용하려면정렬된 상태에서 사용해야 하는 경우가 있기에 필요하다ex. 이진탐색, 병합정렬의 병합,... # 삽입 정렬삽입 정렬은 오른쪽의 비정렬된 영역의 값들을 하나씩왼쪽의 정렬된 영역으로 이동시키면서 정렬을 하는 방법이다 기본적으로 오른쪽 영역의 하나의 값을왼쪽의 영역으로 올바른 위치에 정렬하기 위해서O(N)이 필요한데해당 동작을 N번 반복해야하니O(N^2)이 소요된다값이 이미 어느 정도 정렬이 되어있는 경우라면O(N)이 소요된다 # 머지 정렬병합 정렬은 2가지 과정을 거친다첫 번째, 리스트를 계속 반으로 나..
# 백트래킹 개념그래프를 완전(모두) 탐색하는 것이 아니라찾는 답일 가능성이 있는 경우에만 탐색하고찾는 답일 가능성이 없는 경우에는 재귀를 통해가장 최근에 방문했던 노드로 돌아가는 것이 핵심이다 # 백트래킹 과정쉬운 백트래킹 알고리즘은 그냥 풀어도 되지만난이도가 있을수록 아래의 단계를 거쳐 확실하게 구현해야 한다1) 상태 정의: 문제의 각 단계를 그래프의 상태로 정의2) 유망함수(IsPromising): 현재 상태가 유망한 지 여부를 확인3) 해결책 확인(IsSolution): 현재 상태가 문제의 답인지 여부를 확인4) 재귀 호출: DFS처럼 재귀를 이용해 유망한 상태로 이동 // 백트래킹을 하기위해서는 반드시 상태 정의를 해야한다// 유망성 판단 함수bool isPromising(int level, S..
# 그래프의 개념그래프의 핵심 개념은 아래와 같다노드: 정점간선: 두 정점이 연결된 선가중치: 거리와 같이 목적에 따라 간선에 가중치가 추가순환(cycle): 간선들에 따라 계속 반복되는 순환 형태 # 그래프의 구현1) 인접행렬행과 열의 인덱스로 노드의 값을 나타내고, 배열의 값은 간선의 가중치가 된다단점: 메모리 낭비 발생장점: 간선여부 확인이 O(1)사용 자료구조: 2차 array예시 코드:https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/adjacencyarray.cpp 2) 인접리스트특정 시작 노드를 기준으로 연결된 노드들을 리스트로 연결하는 방식이다장점: 필요한 그래프의 노드 개수만큼만 추..
#상호배타적 집합위의 왼쪽 그림처럼교집합이 없는 집합관계를 상호배타적 집합이라고 한다 #집합을 표현하는 방식집합을 표현할 때,집합에서 가장 작은 원소를 대표 원소로 설정하고현재 노드의 부모노드를 저장하는 array나 unordered_map을 통해 테이블을 만들면 된다 테이블에는 본인의 부모노드를 작성한다현재노드와 부모노드가 동일한 경우는 대표원소이다부모노드가 -1은 미존재 원소를 의미한다 #집합의 연산 - find특정 노드의 루트노드를 확인하는 연산이다특정 노드로부터, 루트노드가 나올 때까지 거슬러 올라가면 된다 그런데,find에서 내부 처리 방식은 2가지 종류가 있다1) 반환하고 거슬러올라가 방문한 노드의 부모노드도 다 바꾸는 방식2) 그냥 반환하고 끝내는 방식 예를 들어,위의 그림 집합 A에서 f..
# 트리의 개념트리는 노드와 간선으로 이루어진 계층적 자료구조로부모-자식 관계가 존재한다트리는 순환이 허용되지 않는다코테에서는 이진트리(자식 노드가 최대 2개인 트리)가 핵심이다 노드는 루트노드, 자식노드, 형제노드, 리프노드 등의 종류로 구분된다차수는 현재 노드를 기준으로 바로 아래에 있는 자식노드의 개수를 의미한다레벨은 0부터 시작하며, 하나의 줄을 의미한다높이는 현재 트리에서 최대 레벨을 의미한다 # 이진트리의 표현 (배열)이진트리를 배열로 표현할 수 있다루트노드 인덱스를 1로 선정하고왼쪽 자식노드는 부모노드 인덱스 * 2오른쪽 자식노드는 부모노드 인덱스 * 2 + 1와 같은 구성을 띤다 이처럼 위의 인덱스 공식만을 활용하기에 구현 난이도는 낮다하지만, 실제 사용되지 않는 빈 공간이 많다는 단점이..
# 배열 vs 해시위처럼 배열을 사용하면탐색을 하는데 O(N) + 접근을 하는데 O(1)이 걸린다 반면,위처럼 해시를 사용하면탐색 및 접근이 O(1)이 걸린다해시 자료구조의 내부 구성은 크게 해시 함수, 버킷, 해시테이블로 구성된다 # 해시함수란?임의의 키를 해시테이블의 인덱스로 변경해 주는 함수를 의미한다해시테이블의 크기가 N이라면, 해시함수는 0 ~ N-1 사이의 값을 가진다또한, 충돌을 최소화 할수록 좋은 해시함수이다 # 해시함수의 내부 방식대표적으로 나눗셈법, 곱셈법, 문자열 해싱이 있다- 나눗셈법키를 %소수를 하는 방식이다소수가 아닌 경우는 충돌이 많이 발생하기에 소수로 연산을 한다예를 들어, 소수가 아닌 2인 경우는짝수는 무조건 0이고 홀수는 무조건 1이니 충돌이 많이 발생한다는 사실을 알 수..
# 스택- 스택의 개념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 (문자열의 길이) ..
