연결 리스트(linked list) ; 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조 단일 연결 리스트 ; 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킴 노드 구조체 struct list{// 연결 리스트의 노드 구조체 int *score; // 데이터를 저장할 멤버 struct list *link; // 다음 노드의 주소를 저장할 포인터 }; - list 포인터형 link에는 list구조체로 만든 다른 노드의 메모리 주소 저장 연결리스트의 생성과 사용 예시 #include struct list{ char *name[10]; int *score; struct list *link; }; struct list *..
배열 ; 같은 타입의 변수들로 이루어진 유한 집합 - 가장 기본적인 자료구조로, 논리적 저장 순서와 물리적 저장 순서가 일치 - 삽입과 삭제 시 시간 복잡도 o(N) - 배열 요소(배열을 구성하는 각각의 값), 인덱스(위치를 가리키는 숫자)로 구성 더보기 1차원 배열 int main() { int arr[3] ={10,20,30}; for(int i=0;i
오늘 알아볼 알고리즘은 바로 정렬 알고리즘인데요 ! 정렬 알고리즘에는 삽입 정렬, 버블 정렬, 선택 정렬, 퀵 정렬 등 많은 알고리즘들이 있지만 그 중 하나의 구현 방법만 익혀두면 유용하게 쓸 수 있습니다! 선택 정렬 ; 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 - 1번째부터 끝까지 훑어서 가장 작은 게 1번째, 2번째부터 끝까지 훑어서 가장 작은 게 2번째,.. 반복 - 장 ; 알고리즘이 단순함 / 교환이 버블 정렬에 비해 적게 일어나 많은 교환이 일어나는 자료상태에서 효율적 - 단 ; 시간 복잡도가 O(n^2)로 비효율적 버블 정렬 ; 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 - 1번째와 2번째 원소..
자료구조 ; 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장 - 데이터 값의 모임, 데이터 간의 관계, 데이터에 적용할 수 있는 함수나 명령을 의미 - 신중히 선택한 자료ㅏ구조는 보다 효율적인 알고리즘을 사용할 수 있게 함 배열 ; 가장 일반적인 구조. 메모리 상에 같은 타입의 자료를 연속적으로 저장 #include using namespace std; int main(){ int array={1,2,3}; cout
알고리즘이란? ; 제한된 공간과 시간 안에서 데이터를 어떻게 처리할 것인지를 정해놓은 로직 알고리즘 공부 방향 - 어떤 자료구조를 이용하여 알고리즘을 작성하는 것이 좋을 지 - 작은 공간 + 빠른 시간안에 효율적으로 처리하는 것이 목표 - 인풋 사이즈 커질수록 Big O가 어떻게 변화하는지 - 자동완성, 복붙 사용 최소화할 것 - 충분한 고민 & 문제에 대한 이해/풀이 아이디어, 어려웠던 점 및 해결책 생각할 것 알고리즘의 종류 재귀 피보나치 수열 int Fibo(int n){ if(n==1 or n==2) return 1; else return Fibo(n-1)+Fibo(n-2); } 최대공약수(GCD) int gcd(int a,int b){ if(a%b==0) return b; return gcd(b..
백트래킹(Back Tracking) ; 모든 경우의 수를 전부 고려하는 알고리즘 - 상태공간을 트리로 나타낼 수 있을 때 적합(트리 탐색 알고리즘) ▶ DFS(Depth-First Search) ; 깊이 우선 탐색 ; 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 - 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색 - 스택(stack) 혹은 재귀함수를 통해 구현 - 모든 경로를 방문해야 할 경우 사용에 적합 ▶ BFS(Breadth-First Search) ; 너비 우선 탐색 ; 최대한 넓게(근접한 것부터) 이동한 후, 더 이상 갈 수 없을 때 아래로 이동 - 루트 노드 혹은 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법 - 시작 정점으로부터..
그리디(Greedy) 알고리즘(=탐욕 알고리즘) ; 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법 - 최적해를 구하는 데에 사용되는 근사적인 방법 - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달 1. 활동 선택 문제 ; 한 강의실에서 여러 개의 수업을 하려고 할 때 한 번에 가장 많은 수업을 할 수 있는 경우를 고르는 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net
이번에 알아볼 알고리즘은 트리인데요! 트리는 방향성이 있는 '그래프'입니다. 트리는 방향성이 있기에 하나의 루트 노드가 존재합니다. 트리 순회(임의의 한 정점에서 시작하여 모든 정점을 한 번씩 방문)에는 DFS,BFS 중 Pre-,In-Post-Order 등이 있습니다. 트리의 예시로는 이진 트리, 이진 탐색 트리, 균형 트리, 이진합 등이 있습니다. 트리(Tree) 용어 1. 루트 노드 ; 부모가 없는 노드 2. 단말 노드(=말단 노드, 잎 노드) ; 자식 노드가 없는 노드 3. 내부 노드 ; 단말 노드가 아닌 노드 4. 간선(=link,branch) ; 노드를 연결하는 선 5. 형제 ; 같은 부모를 가지는 노드 6. 노드의 크기 ; 자신을 포함한 모든 자손 노드의 개수 7. 노드의 깊이(레벨) ; 루..
