본문 바로가기
728x90

전체 글202

[C++ 자료구조] stack std ● 참고한 링크 더보기 https://blockdmask.tistory.com/100 ● 헤더 include ● 생성자 stack [Variable Name]; stack [Variable Name]; ===멤버 함수=== ● stack.empty( ) : 비어 있으면 true 반환 ● stack.size( ) : 원소 수를 반환 ● stack.push( element ) : 스택의 맨 위 element 원소 추가 ● stack.pop( ) : 스택의 맨 위 원소 삭제 ● stack.top( ) : 스택의 맨 위 원소 반환 2021. 7. 23.
[C++] 꿀팁 스킬 ● 헤더 #include // 알고리즘 문제 풀이에 필요한 헤더 모음 참고 : https://miniolife.tistory.com/11 ● 입출력 속도 향상 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // main문 시작에 위치 // 그러나 printf(), scanf(), put(), getchar() 와 같은 // C 스타일의 입출력을 쓰시면 안 됨 ● 정수, 실수 자료형 int a;// (-20억 ~ +20억) 정수 long long b;// (-19자리 ~ +19자리) 정수 double c;// (-15자리 ~ +15자리) 실수 // 기본 → int // int형 범위를 벗어나는 정수 → long long // 나눗셈을 하는데 소수점이 필요한 경우 .. 2021. 7. 23.
[자료구조] 07 그래프 ▶ 그래프 (Graph) 방향 그래프 무방향 그래프 완전 그래프 가중치 그래프 부분 그래프 ▶ 그래프 G의 정점 집합 V(G) = {A, B, C, D} 무방향 그래프 G의 간선 집합 E(G) = {(A, B), (A, C), (A, D)} 방향 그래프 G의 간선 집합 E(G) = {, , } ▶ 구현 방법 (2가지) : 인접 행렬 기반 그래프 (정방 행렬 활용) : 인접 리스트 기반 그래프 (연결 리스트 활용) ▶ 탐색 깊이 우선 탐색 (Depth First Search) (DFS) 너비 우선 탐색 (Breadth First Search) (BFS) ▶ 깊이 우선 탐색 (DFS) : 한 사람에게만 연락을 취한다. (PUSH 떠나는 노드) : 연락할 사람이 없으면, 자신에게 연락한 사람에게 이를 알린다... 2021. 3. 15.
[자료구조] 06 테이블 ▶ 테이블 (Table) : 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다. : 키가 존재하지 않는 '값'은 저장 불가 : 모든 키는 중복되지 않는다. : ex) 사전(단어-키, 설명-값) ▶ : 배열의 인덱스 값을 키 범위로 사용하기에 적당하지 않다. : 왜냐하면 매우 큰 배열이 필요하기 때문 : 이를 해결해주는 것이 '해쉬 함수' ▶ 해쉬 함수 (Hash Function) : 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할 : 좋은 해쉬 함수는 데이터가 메모리에 골고루 분포하여 충돌 활률이 낮다. ▶ 좋은 해쉬 함수 만드는 법 : 키의 특성에 의존되기 때문에 정답은 없다. : 키의 일부분 참조항여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬값 만들기 ▶ 해쉬 충돌 (Hash Collision.. 2021. 3. 15.
[자료구조] 05 정렬, 탐색 ▶ 정렬 (Sort) : 버블 정렬 (Bubble Sort) : 선택 정렬 (Selection Sort) : 삽입 정렬 (Insertion Sort) : 힙 정렬 (Heap Sort) : 병합 정렬 (Merge Sort) (분할(Divide) → 정복(Conquer) → 결합(Combine) 기반 구현) : 퀵 정렬 (Quick Sort) (분할(Divide) → 정복(Conquer) → 결합(Combine) 기반 구현) : 기수 정렬 (Radix Sort) ▶ 순차 탐색 (Linear Search) : 정렬 되지 않은 대상을 기반으로 하는 탐색 ▶ 이진 탐색 (Binary Search) : 정렬된 대상을 기반으로 하는 탐색 ▶ 보간 탐색 (Interpolation Search) : 데이터의 값과 그 데.. 2021. 3. 15.
[자료구조] 04 우선순위 큐, 힙 ▶ 우선순위 큐 (Priority Queue) : 산입 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. : ex) 응급상황 ▶ 배열 기반 우선순위 큐 (단점) : 데이터 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다. : 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다. ▶ 연결 리스트 기반 우선순위 큐 (단점) : 삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작해서 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다. ▶힙 (Heap)을 이용하는 우선순위 큐 구현 : 위와 같은 단점들로 인해 힙을 이용한다 ▶ 힙 (Heap) : '이진 트리'이되 '완전 이진 트리'이다.. 2021. 3. 15.
728x90

티스토리툴바