그냥 개발공부 블로그

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.1.탐욕 알고리즘 1)정의- 최적의 값을 구해야 하는 상황에서 사용되는 방법으로 ‘현재에서 최적이라고 생각되는 것을 선택’ 해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 알고리즘.- 이때, 항상 최적의 값을 보장하는 것을 목표로 두지 않고 최적의 값에서 ‘근사한 값’을 목표로 한다. 2)탐욕 알고리즘 과정 2.허프만 코딩1)고정 및 가변 길이 코드 -고정 길이 코드는 코드의 길이가 똑같은 값을 갖는 코드 체계 아스키 코드가 대표적. -가변 길이 코드는 코드의 길이가 다른 값을 가지는 코드 저장 공간을 절약을 위해서 사용된다.2)접두어 코드(Prefix Code) -접두어란 ..

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.1.동적 계획법 1)정의 -어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어졌을 때 각 단계에 있는 부분 문제의답을 기반으로 전체 문제의 답을 구하는 방법.-부분 문제의 답을 구하는 과정에서 별도의 테이블을 생성하고 부분문제를 다시 접하게 될 시테이블에 꺼내서 활용한다. 2)과정 2.최장 공통 부분 수열(LCS: Longest Common Subsequence) 1)개요 및 정의 -부분 수열(Subsequence)이란 수열에서 일부 요소를 제거 한 것을 뜻한다. -최장 공통 부분 수열은 두 문자열이 공통으로 가지는 부분 수열 중 길이가 가장 긴 수열을 뜻한다.2)길이 구하는 점..

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다. .분할정복 알고리즘 1)정의 -분할 정복이란 크고 방대한 문제를 풀기 용이하게  조금씩 나누고 풀이한 다음 다시 합쳐 해결하는 알고리즘. 2.병합 정렬(Merge Sort) 1)정의  -분할정복 알고리즘을 기반으로 둔 정렬 알고리즘. 2)작동 방식 -분할 및 병합 과정 -정렬 과정3.거듭 제곱 계산(Exponentiation) 1)개요 -거듭 제곱은 같은 수나 식을 거듭 곱하는 일 -거듭제곱은 같은 수의 반복이기에 한번 계산한 값이 있다면 그대로 수식에 적용 시킬 수 있다.  -수학에서 식을 치환하여 쉽게 볼 수 있게 만드는 것은 분할정복과 같다. -C는 거듭제곱할 수 n 거듭제..

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다. 1.고지식한 탐색(Brute-Force Search) 1)정의 -문자열에서 찾고자 하는 패턴을 앞에서부터 검색하는 알고리즘. -단순하지만 패턴을 찾기 위해 문자열 길이 x 패턴 길이만큼 검색량이 생길 수 있다. 2.카프-라빈 알고리즘 1)정의 -문자열 탐색에서 해시함수를 사용하는 알고리즘 -패턴의 해시값과 문자열의 해시값을 비교하는 방식. -문자열 길이가 m일 때 해시 값을 구하는 함수. -만약 이전 해시함수 값을 알고 있다면 아래와 같이 변형이 가능하다. 3.KMP 알고리즘 1)정의 -문자열에서 찾을려는 패턴과 문자열을 비교하면서 생기는 정보를 바탕으로 검색 효율을 높이는 알고..

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다. 1.최소 신장 트리(Minimum Spanning Tree) 1)정의 -그래프의 간선에는 가중치(weight)라는 정점과 정점의 관계를 나타내는 속성 가중치는 거리,비용 등 다양하게 표현 가능하다. -신장트리는 기존 그래프의 모든 정점을 포함하고 순환 구조 없이 연결한 트리를 뜻한다. -최소 신장 트리는 신장 트리 중 가중치 합이 가장 최소인 최소 신장 트리를 뜻한다. 2.프림 알고리즘(Prim Algorithm) 1)정의 -그래프의 임의의 정점을 하나 선택하고 정점과 인접한 정점들 중 가중치가 적은 간선으로 연결된 정점을 선택하여 최소 신장 트리를 만드는 알고리즘. -정점이 추..

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.  1.위상정렬(Topological Sort) 1)정의 -그래프에서 위상이란 정점과 정점의 관계 속에서 가지는 위치를 뜻한다. -간선은 정점과 정점 사이의 관계를 나타내고 정점의 입장에서 간선은 들어가는 간선인 진입간선(Incoming Edge), 나오는 간선인 진출간선(Outgoing Edge)으로 나눌 수 있다. -간선을 통해 정점들 간의 누가 진출(앞)/진입(뒤)하는 관계에서 정점들 간의 위치를 나타낸다.   -위상 정렬은 간선들의 진출/진입의 방향이 한 방향이 되도록 정렬하는 알고리즘을 말한다.2)과정 3)깊이 우선 탐색을 이용한 위상 정렬 4)우선 깊이 탐색 코드

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다. 1.깊이 우선 탐색(DFS: Depth First Search) 1)정의 -그래프에서 가장 깊은 부분을 우선적으로 탐색하는 알고리즘 -하나의 정점에서 시작하여 한 방향으로 갈 수 있을 때까지 가다가 길이 끝나면 가장 가까운   갈림길로 되돌아와 다른 방향을 다시 탐색하는 방식. 2)과정2.너비 우선 탐색(BFS : Breadth First Search) 1)정의 -그래프에서 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 탐색하는 알고리즘 2)과정3.그래프 순회기법 구현 1)함수 구현-깊이 우선 탐색-너비 우선 탐색-테스트

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다. 1.인접 리스트 그래프 구현1)데이터 노드 구현  2)원형 함수 선언 3)함수 구현-그래프 생성 및 삭제 함수-정점 생성 및 삭제 함수-간선 생성 및 삭제 함수-그래프 정점 및 간선 추가함수-테스트

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.1.그래프(Graph) 1)정의 -정점 및 혹은 노드와 그들을 연결하는 간선으로 이루어진 자료구조. -간선으로 연결된 두 정점을 가리켜 서로 인접한 이웃관계라고 한다.-간선은 정점들 간의 경로(Path) 및 관계(Relation) 등 여러가지로 표현된다.-간선은 정점과 정점으로 된 방향이 존재할 수 있고 방향이 존재하는 그래프를 방향성 그래프(Directed Graph) 존재하지 않은 그래프를 무방향성 그래프(Undirected Graph). 2.그래프의 표현 방법1)개요 -그래프는 정점과 간선의 결합으로 여러가지 형태로 표현될 수 있다. 대표적으로 행렬과리스트이다. 2)인접 행렬..

아래의 상기 내용은 "이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.  1.개방 주소법(Open Addressing) 1)정의 -해시테이블에 충돌이 일어나도 해시함수로 만들어진 주소 이외에 다른 주소를 사용하여 충돌을 해결하는 알고리즘  2.선형탐사(Linear Probing) 1)정의 -개방 주소법 중 하나로 해시함수로 얻어낸 주소에 이미 다른 데이터가 입력 경우 현재 주소에서 일정 거리의 주소로 이동하는 방식.    3.제곱탐사(Quadratic Probing) 1)정의 -개방 주소법 중 하나로 해시함수로 얻어낸 주소에 이미 다른 데이터가 입력 경우 현재 주소에서 탐사 횟수에  제곱된 거리의 주소로 이동하는 방식. 4.이중 해싱(Double H..