삼성전자 알고리즘/자료구조 알고리즘 (16) 썸네일형 리스트형 15. 꼭 알아야 하는 유형 1. 링크드리스트 동적할당을 정적할당으로 구현 --메인 밖에서 선언 typedef struct _node { int x; struct _node *next = nullptr; }NODE; NODE arr[1000 * 1000 + 10];//문제에서 나올 수 있는 모든 노드의 수(배열을 할당할 주소값으로 사용) int cnt = 0; --메모리 할당 NODE *newNode = &arr[cnt++]; --메모리 해제 cnt = 0; 2. 링크드리스트를 활용하여 만든 해시테이블(설정) const int MAX = 1 x = x; //Case 1 : 무작정 맨 앞에 연결 하는 방법 newNode->next = cur->next;//맨 앞에 노드 연결 cur->next = newNode;//해시연결해주기 //C.. BFS / DFS DFS : 1) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 2) 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 3) 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다 (완전탐색) 특징 : 1)자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다. 2)어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다 시간 복잡도: DFS는 그래프 (정점의 수 : N, 간선의 수 : E)의 모든 간선을 조회한다. -인접 리스트로 표현된 그래프 : O(N+E) -인접 행렬로 표현된 그래프 : O(N^2) 출처 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.. 분수 계산 분수의 크기를 비교 할 때 ex) a/b와 c/d의 크기를 구할 때 로 나타낼 수 있다. b*d의 부호는 양수이므로 분자 a*d - b*c가 양수인지 0인지 음수인지만 판단하면 된다. 컴퓨터에서 정수처리가 가능하다면 실수 처리를 피하는 것이 좋다. 실수 연산의 결과는 완전히 신뢰할 수 없기 때문이다. 12. 배열 Array 고정 배열(fixed array) vs 동적 배열 (dynamic array) 출처 : https://boycoding.tistory.com/194 배열의 모든 요소를 0으로 초기화 하는 방법 : int arr[5] = {}; int brr[5] = {0}; 인덱스의 명칭 : enum의 사용 #include using namespace std; enum StudentNames { Kim, //0 Lee, //1 Park, //2 Choi, //3 MAX_STUDENTS //4 }; int main(){ int scores[MAX_STUDENTS]; scores[Kim] = 100; cout 11. B트리 / B+트리 / B*트리 출처 : https://m.blog.naver.com/eng_jisikin/220889188747 1. B트리 사용 이유 : 검색에 유용하기 때문에 사용 2. Balanced Tree의 종류 : AVL 트리, 2-3 트리, 2-3-4 트리, Red-Black 트리, B 트리 3. 한 노드에 최대 들어갈 수 있는 데이터 수를 차수라 하고 비트리의 늘어날 수 있는 다리를 Order 라고 함. (Order는 데이터 수 +1 개) 4. 예제 : 5. M=짝수일 때, 홀수일 때 알고리즘이 다름 10. 트리 세그먼트 트리 : 인덱스 구간의 합을 노드에 저장. 리프 노드에는 각 데이터가 저장되어 있음. #include #define NUM_DATA 5 #define MAX_TREE (1 9. 스택 링크드 리스트를 활용하여 스택 구현하기 : 링크드 리스트를 이용하면 배열로 구현할 때 보다 메모리 제약에서 자유로움. typedef struct _node { int data; struct _node* prev; }Node; 우선 데이터와 이전 노드를 가리킬 포인터를 구조체 변수로 갖는 Node 변수를 만든다. typedef struct _stack { Node* top; int size = 0; }Stack; Stack 구조체는 pop()과 push()가 실행될 때 사용할 top 포인터와 스택의 길이를 나타내는 사이즈 변수를 갖는다. 메인에서 스택을 선언한다. int main() { Stack st; //스택 생성 push(&st, 1) push(&st, 2) push(&st, 3) pop(&st); .. 8. 정렬 1. 버블 정렬 : 정렬 성능은 안좋지만 O(n^2) 빠르고 쉽게 구현 가능. 정렬이 중요한 문제가 아니라면 버블 정렬도 나쁘지 않음. #define SWAP(a,b) {int t; t= b; b=a; a=t;} int arr[5] = { 1,5,3,2,4 }; void bubble_sort(int arr_size) { for (int fixed_p = arr_size -1; fixed_p > 0; fixed_p--) { for (int bubble_p = 0; bubble_p arr[bubble_p+1]) {//5,3 일때 3,5로 바꿔줘야함 SWAP(arr[bubble_p], arr[bubble_p+1]); } } } }.. 이전 1 2 다음
