leehyeon-dv 님의 블로그

🔑Table of Contents시간복잡도 알고리즘분석RAMO, Ω , Θ 표기최대 부분 배열단순한 O(n³) 알고리즘 O(nlogn) 분할정복법 알고리즘 O(n) 동적 계획법 알고리즘중복 계산을 제거한 O(n²) 알고리즘정렬과 탐색삽입정렬선택정렬거품정렬퀵정렬이진탐색선형리스트 순차매핑연결리스트 헤드노드를 가진 연결리스트 환형 연결리스트 이중 연결리스트 스택과 큐스택큐환형 큐연결리스트를 큐로 구현 리스트의 응용배열이용희박행렬 배열이용희박행렬 연결리스트 이용스트링 표현연산식트리용어정리재귀적정의트리표현 - 링크이용트리의 이진 트리 표현괄호를 이용한 트리표현이진트리이진트리의 재귀적 정의이진트리의 성질이진트리 표현 - 링크이용이진트리 표현 - 배열이용이진트리 순회수식트리중순위 순회후순위 순회와 전순위 순회..

🔑Table of Contents스택이란?📌스택이란? 삽입과 삭제 연산을 한 쪽 끝에서만 일어나도록 제한한 리스트스택에서 삽입과 삭제 연산이 일어나는 끝을 top이라하고, 삽입 연산과 삭제 연산을 각각 push, pop이라고 한다 LIFO : 스택에서 나중에 삽입된 원소가 먼저 삭제되는 성질시스템에서 함수 호출이 발생할 경우, 가장 최근에 호출된 곳으로 복귀하기 위해 스택에 복귀 주소를 저장해 둔다 📌스택의 구현1 - 배열#define MAX_STACK_SIZE 1000 // 스택의 최대 크기 정의// 스택에 저장될 요소의 구조체 정의typedef struct { int key; // 저장할 데이터 (다른 필드도 확장 가능) /* other fields here ..

🔑Table of Contents선형리스트 란?  선형리스트의 연산배열 - 선형리스트 표현1 📌선형리스트 란?     선형 리스트(혹은 리스트)는 자료가 순서를 가지고 나열된 자료구조     리스트의 원소 = 리스트를 이루고 있는 각각의 자료      n개의 원소 a₀, a₁, ... , aₙ₋₁로 이루어진 리스트는          ( a₀, a₁, ... , aₙ₋₁ )로 표기한다 📌선형리스트의 연산     리스트에서 수행하는 대표적인 연산리스트 길이는?리스트의 모든 원소를 하나씩 읽어라k번째 원소는 무엇인가k번째 원소를 다른 원소로 교체해라k번째 위치에 새로운 원소를 삽입하라, 연산을 수행한 후에는 기존의 k번째 원소가 k+1번째 원소가 된다 k번째 원소를 삭제해라. 기존의 k+1번째 원소가 k..

🔑Table of Contents정렬 및 탐색 알고리즘정렬- 재귀적 접근1  정렬- 재귀적 접근2 퀵 정렬 퀵 정렬 분석 퀵 정렬에 덧붙여..정리📌 정렬 및 탐색 알고리즘정렬삽입 정렬 → O(n²)선택 정렬  → O(n²)거품 정렬  → O(n²)퀵 정렬     → O(n²) O(n logn)합병 정렬  → O(n logn)힙 정렬      → O(n logn)이진 탐색 트리를 이용한 정렬  → O(n logn)탐색이진 탐색 → O(logn)선형 탐색 → O(n)📌 정렬- 재귀적 접근1     [ 8 21 33 6 7 10 40 87 66 42 50 ]    삽입 정렬   6  7 8 10 21 33 40 42 66 87   • 앞에서 부터 수를 정렬에 맞게 삽입 / n개 n번탐색 O(n²)    ..

🔑Table of Contents문제정의 알고리즘알고리즘1 - 기본아이디어알고리즘1 - 시간 복잡도 분석알고리즘2 - 기본 아이디어알고리즘2 - 시간 복잡도 분석순환 알고리즘 완성하기알고리즘3 - 분할정복법시간 T(n) 구하기알고리즘4 - 기본 아이디어알고리즘4 - 동적계획법 → O(n) 📌문제정의 길이 n인 배열 A[0], A[1], ... , A[n-1]이 입력으로 주어질때, i번째부터 j번째 까지 원소들로 이루어진 배열 A[j], ..., A[j]를 부분 배열이라고 하고 A[i,j]로 나타냄 → A[0]도 존재함 • 문제는 최대 부분 배열, 즉 부분 배열에 속한 원소들의 합이 최대가 되는 부분 배열을 찾는 것이다 이때, 길이가 0인 부분 배열도 허용하며, 이 부분배열의 원소들의 합은 0이라고 정..

🔑Table of Contents알고리즘 분석RAM시간복잡도공간복잡도O(빅오),Ω(오메가),Θ(세타)O,Ω,Θ 표기 연습 시간 복잡도 분류📌알고리즘 분석 주어진 문제에 대한 알고리즘을 설계한 후 다음을 분석한다 - 정확성 : 가능한 입력에 대해서 항상 옳은 답을 출력하는가?- 자원 : 얼마나 많은 자원을 사용하는가? ※ 가장 중요한 자원 = 알고리즘 실행시간, 알고리즘을 실행하는데 필요한 메모리 양 📌 RAM (Random Access Machine)명령어가 순차적으로 수행되는 보통의 컴퓨터에 기반을 두고 있음 1. 간단한 명령어를 가짐(사칙연산, 비교, 치환)2. 정수를 고정된 길이로 표현 (예 : 32비트) → 덧셈이면 크기 상관없이 다 똑같은 시간이 걸림(정수 보통 4바이트)3. 무한한 양의..