# Computer Science/알고리즘, 자료구조
그래프 간단 정리
그래프 EX) SNS 사용자와 사용자의 친구관계, 지하철 노선도 노드와 간선으로 이루어진 관련 용어 정점 (vertax) : 노드 간선 (edge) : 노드를 연결하는 선, 노드 간의 관계 인접 정점 : 하나의 간선에 의해 직접 연결된 정점 정점의 차수 : 정점에 연결되어 있는 간선의 갯수 구현 배열 : 인접행렬 (불필요한 공간 많이 차지) 연결리스트 : 인접리스트 ( 전체 정점을 표현한 후 각 노드별로 연결된 정점을 표현) 분류 [방향성에 따른 분류] 1. 방향 그래프 (A to B : ) 2. 무방향 그래프 ( A to B : (A, B) ) [연결에 따른 분류] 1. 연결 그래프 : 모든 정점 간의 경로가 존재하는 그래프 2. 비연결 그래프 : 무방향 그래프에서 특점 정점쌍 사이에 경로가 존재하지 ..
트리 간단 정리
트리 트리는 그래프의 한 종류로 무방향, 연결 비순환 그래프이다. 계층적인 구조 사이클이 없다. 노드가 N개인 트리는 N-1개의 간선을 가진다. 임의의 두 노드 간의 경로가 유일하다. 관련 용어 - 노드 - 루트 - 서브트리 - 차수 : 각 노드의 자식의 갯수 - 리프노드 : 자식없는 노드 - 레벨 (층을 나타내는 index) : 루트노드부터 0레벨 내려갈수록 1++ - 높이 :트리의 최대 레벨, (중간노드의 높이는 해당 노드가 루트노드가 되는 서브트리의 높이) 트리의 종류 이진트리 모든 노드의 차수가 2 이하인 트리 (모든 노드가 최대 2개의 자식 노드를 가짐) 이진트리의 모양에 따른 분류 포화 이진 트리(Full Binary Tree) : 레벨의 노드가 꽉 차 있는 트리 (높이가 h일 때 노드의 개수..
[PS] 그리디 알고리즘
그리디 알고리즘 현재 상황에서 가장 좋은 것만 고르기 ✨현재 상황만을 고려하고 나중에 미칠 영향에 대해서는 고려하지 않는다. ✨ 기준에 따라 좋은 것을 선택하므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 등 기준을 제시한다. ✨ 정렬 알고리즘과 짝을 이룬다. 거스름돈을 생각한다. 해법 그리디 알고리즘으로 해법을 찾았을 때, 그 해법이 정당한지 검토해야 한다. 10000, 5000, 1000, 100, 50, 10 의 거스름돈의 경우 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다. 알고리즘 유형 유추 문제 유형을 파악하기 어렵다. 탐욕적인 해결법이 존재한다. 그래도 해결 방법을 못 찾겠다면 다이나믹 프로그래밍이나 그래프 알고리즘을 의심한..
[알고리즘] Selection Sort 선택 정렬
선택 정렬 가장 작은 수를 찾으면서 정렬 ( 왼쪽부터 작은 수가 정렬됨) 123456789101112131415161718192021222324252627282930313233343536#include using namespace std; int main(void){ //1 15 5 3 9 7 6 4 2 10 8 1 11 11 12 int nums[] = {1, 15, 5, 3, 9, 7, 6, 4, 2, 10, 8, 1, 11, 11, 12}; int arrSize = sizeof(nums)/sizeof(nums[0]); for(int i = 0 ; i
[알고리즘] Bubble Sort, 버블 정렬
양 옆의 수를 바꿔주면서 진행하는 정렬 가장 오른쪽에 큰 수가 정렬되면서 진행 O(n^2) 123456789101112131415161718192021222324252627282930313233343536373839#include using namespace std; int time = 0; int main(void){ int nums[] = {1, 15, 5, 3, 9, 7, 6, 4, 2, 10, 8, 1, 11, 11, 12}; int arrSize = sizeof(nums)/sizeof(nums[0]); for(int i = 0 ; i