코딩테스트

동적 계획법⇒ 복잡한 문제를 단순한 하위 문제로 나눠서 접근하는 방법⇒ 중복 계산을 줄이기 위해, 이전에 구한 해를 활용 이전의 해를 활용해야 효율적인 문제의 조건최적 부분 구조문제의 최적 해결책이 하위 문제의 최적 해결책으로부터 구성되는 경우중복 부분 문제동일한 하위 문제가 여러번 계산 됨 예시 1 : 팩토리얼 예시 2 : 피보나치 수 동적 계획법 적용하는 법 예시 1 : 계단 오르기 ⇒N개의 계단이 존재하고, 한번에 1개 혹은 2개의 계단을 오를 수 있음. 계단을 오르는 방법의 총 수는? 1. 예제 입력으로 출력을 만드는 과정을 직접 손으로 작성2. 과정을 일반화. 이때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인한다.3. 2번의 과정에서 이전해를 구하는 과정이 ..

코테에서 정렬은 언제 필요한가? 대표적인 정렬 알고리즘 삽입 정렬 왼쪽 : 정렬된 영역 / 오른쪽 : 비 정렬된 영역정렬된 영역이 점점 확장되어 비 정렬된 영역이 사라짐비 정렬된 영역의 맨 앞의 원소를 정렬된 영역의 적절한 곳에 추가용도: 작은 데이터 셋에서 효율적이며, 이미 부분적으로 정렬된 배열에서 높은 성능을 보입니다.삽입정렬 과정 1. 첫 번째 원소를 정렬된 부분으로 간주합니다. 2. 다음 원소를 정렬된 부분과 비교하여, 올바른 위치에 삽입합니다. 3. 모든 원소가 정렬된 부분에 삽입될 때까지 2의 과정을 반복합니다.   삽입 정렬의 최고 / 최악 케이스 최선의 경우: O(n) - 이미 정렬된 배열의 경우평균의 경우: O(n^2) - 일반적인 경우최악의 경우: O(n^2) - 역순으로 정렬된 ..

그래프의 개념 및 종류 =⇒ 노드와 간선을 이용한 비선형 자료구조목적에 따라 간선의 가중치나 방향이 있을 수 있음그래프의 구현인접 행렬#include using namespace std;// 인접 행렬의 노드 개수 (고정)const int numNodes = 2; // 인접 행렬 배열int adjMatrix[numNodes][numNodes];/*최악의 경우 1 -> 2 -> 100 일때 100*100의 배열을 만들어야함*///그래프 초기화void initializeMatrix() { for (int i = 0; i 여기서 V는 노드의 개수입니다.- 간선이 존재하는지 확인하는 작업은 O(1)의 시간 복잡도를 가집니다.- 모든 간선을 탐색하는 작업은 O(V^2)의 시간 복잡도를 가집니다.최종적인 인접..

상호 배타적 집합 ⇒ 교집합이 없는 집합 관계 집합 표현하기고려사항1. 특정집합 원소들이 하나의 집합의 원소라는 것을 알 수 있어야함     ex) a={1,2,3}일때 각 원소가 집합 a에 속한다는 걸 알아야함 2. 각 집합 간 다른 집합이라는 것을 알 수 있어야함     ex) a={1,2,3} b= {4,5,6} 두 집합이 다른 집합이라는걸 알아야함 3. 특정 원소가 어느 집합에 속하는지 알아야함     ex) a={1,2,3} b= {4,5,6} 원소 5가 집합 b에 속하는걸 확인 가능해야함 4. 두개의 집합을 하나로 합칠 수 있어야 함 ⇒ 각 집합의 대표원소(루트노드) 를 만들면 해결!  집합의 연산집합의 연산 find⇒특정 노드의 루트노드를 확인하는 연산특정 노드로 부터, 루트노드가 나올때 까..

트리 개념⇒ 노드와 간선으로 이루어진 계층적 자료구조. (부모- 자식 관계)⇒ 순환을 허용하지 않음.⇒ 코테에서는 이진트리(자식 노드가 최대 2개인 트리)만 알면 됨. 이진 트리 표현하기1. 배열루트 노트 인덱스 = 1왼쪽 자식 노드는 부모노드 인덱스 *2오른쪽 자식 노드는 부모노드 인덱스 * 2 +12. 인접 리스트⇒각 리스트의 인덱스는 부모 노드⇒자식 노드는 부모 노드에 해당되는 인덱스에 추가 이진 트리 순회1. 전위순회 (부모 → 왼쪽 자식 → 오른쪽 자식) #include using namespace std;// 트리를 배열로 나타내기 위해서, 배열의 인덱스를 사용하는 후위 순회 함수 정의void postorderTraversal(int tree[], int index, int size) { ..

해시 개념- 배열을 가지고 연락처를 구현할 때 미우 비효율적 (O(N))- 해시 함수를 이용하여 연락처를 구현하면 훨씬 효율적 (O(1))해시 함수란?  ⇒임의의 키를 해시 테이블의 인덱스로 변경해주는 함수    해시 테이블의 크기가 N이라면 해시함수는 0~(N-1)사이 값을 반환 해야함. 충돌 : 서로 다른 키를 해시함수에 넣었을 때 , 동일한 인덱스를 반환하는것. ⇒ 따라서 이 충돌을 최소화 할수록 좋은 해시함수  나눗셈법 ⇒ 입력값을 테이블의 크기로 나누고 나머지를 테이블의 주소로 사용. 주소 = 입력값 %테이블의 크기. 일반적으로 나눗셈법으로 구현된 해시 함수고 테이블 내 공간을 효율적으로 사용하기 위해서는 테이블의 크기를 소수로 정하는 것이 좋다고 알려짐.  해시 충돌 ⇒ 서로 다른키에 대해 ..