알고리즘

2. Naive 알고리즘 (고지식한 탐색 알고리즘)

Reference: - 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 고지식한 탐색 알고리즘 (Naive Search or Brute Force Search Algorithm) : 본문의 앞에서부터 끝까지 차근차근 탐색하는 알고리즘 본문 : 'ABCABACDC' 패턴 : 'BA' => 이 알고리즘은 이름 그대로 요령 부리지 않고 우직하게 일하는 일꾼처럼 동작한다 본문 길이 : N 패턴 길이 : M 패턴을 찾기 위해 최악의 경우 N x M 번의 비교를 수행 => 굉장히... 느림 일치하는 경우 해당 경우의 끝나는 값에 1을 표기한다 1의 갯수..

2. 점근 표기법

점근(차츰 점, 가깔울 근) 표기법 => 알고리즘의 수행시간을 대략적으로 나타내는 방법 ex) 데이터를 정렬하는데 필요한 작업 횟수 : (n^2 + 5n ) vs ( 27n ) => 데이터의 크기가 커지면 커질수록 최고차 항을 제외한 나머지 항의 영향은 거의 없다 => 때문에 점금 표기법에서는 알고리즘의 성능을 최고차 항으로만 '대략적으로' 표시한다 대표적인 점근 표기법 3가지 O(Big O) 표기법 Ω (Big Omega) 표기법 Θ (Big Theta) 표기법 O(Big O) 표기법 최악의 경우 알고리즘 수행 시간 즉, 아무리 열악한 조건이라도 (입력이 아무리 크더라도) O 표기법으로 표현된 성능 수준에서 알고리즘이 종료된다는 의미 가장 많이 사용하는 알고리즘 성능 표기법 사용방법 대문자 O를 쓰고 ..

1. 알고리즘 성능 측정 기준과 수행 시간

알고리즘 성능 측정 기준 정확성 : 정확하게 동작하는가? => 알고리즘이 입력값에 대해 정해진 절차를 수행하여 결과적으로 정확한 출력을 제공하는가를 가리키는 기준 작업량 : 얼마나 적은 연산을 수행하는가? => 요구되는 기능을 수행하기 위해 알고리즘이 수행해야 하는 작업의 양이 얼마나 되는가를 가리키는 기준 ex) 버블 정렬에서 정렬을 수행하기 위해 비교 연산을 몇 번 수행하는가? 라는 질문에서 '비교횟수' 메모리 사용량 : 얼마나 적은 메모리를 사용하는가? => 말 그대로 해당 알고리즘이 작업을 수행할 때 사용해야 하는 메모리의 양 단순성 : 얼마나 단순한가? => 알고리즘을 짤 때는 보기쉽고 단순해야 한다 최적성 : 더 이상 개선할 여지가 없을 만큼 최적화가 되어있는가? => 최적화를 거친 알고리즘들..

1. 탐색

Reference: - 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 1. 탐색이란? 무언가를 찾는다 컴퓨터 세계에서의 무언가 = 데이터 즉, 데이터를 찾는다 순차 탐색 가장 간단한 탐색 알고리즘 이진 탐색 놀라운 성능을 보여주는 탐색 알고리즘이지만 모든 자료구조에서 사용할 수 있는 것은 아님 각 요소가 메모리에 순차적으로 적재되어 있어 그 주소를 바로 계산할 수 있는 배열에서나 사용이 가능 이진 탐색 트리 데이터의 크기가 동적으로 변경되는 경우에도 이진 탐색과 동일한 성능으로 탐색을 가능하게 하는 자료구조 레드 블랙 트리 이진 탐색 트리를 한층 더 개선한 것 2. 정렬되지 않은 배열에서의 탐색 - 순차 탐색 (Sequen..

알고리즘이란

알고리즘 : 어떤 문제를 풀기 위한 단계적 절차 ex) 정렬, 탐색, 해싱 등 알고리즘을 설계 : 문제 풀이 절차를 설계한다는 의미 알고리즘을 구현 : 프로그래밍 언어를 이용해서 문제 풀이 절차를 실제로 동작하는 코드로 작성한다는 의미 알고리즘을 공부한다는 것 : 어떤 문제를 분석해서 컴퓨터가 알아들을 수 있는 형태로 해법을 설계하고 구현하는 과정을 익힌다는 의미 알고리즘을 이해한다는 것 : 알고리즘 동작에 소요되는 메모리(공간)와 프로세싱 파워(시간)를 깊이 이해하고, 자원을 효율적으로 활용하면서도 고성능의 코드를 작성하는 방법을 익힐 수 있음 알고리즘을 공부해야 하는 이유 : 어떤 문제를 해결할 때 가장 적절한 API를 선택하는 데에 도움이 됨 ex) 메모리 효율과 탐색 속도 중 어느 요소를 더 중요..

2. 이진 트리

2. 이진 트리의 소개 - 이진 트리의 정의 이진 트리 (binary tree) : 이진트리의 서브 트리들은 모두 이진트리여야 함 => 트리 중에서 가장 많이 쓰이는 트리 이진 트리의 정의 공집합이거나 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의 이진 트리와 일반 트리의 차이점 이진 트리의 모든 노드는 차수가 2이하, 즉 자식 노드의 개수가 2이하지만 일반 트리는 자식 노드의 개수에 제한이 x 일반 트리와는 달리 이진 트리는 노드를 하나도 갖지 않을 수도 있다 서브 트리간에 순서가 존재한다 (왼쪽 서브트리와 오른쪽 서브트리를 구별) - 이진 트리의 성질 n개의 노드를 가진 이진트리는 정확하게 n-1의 간선을 가짐 => 이진트리에서의 노드는 루트를 제외하면 정확하게 하나..

1. 트리

Reference : - C언어로 쉽게 풀어쓴 자료구조 [개정3판] / 천인국, 공용해, 하상호 / 생능출판사 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://velog.io/tags/datastructure 1. 트리의 개념 선형 자료 구조 : 리스트, 스택, 큐 계층적인 자료구조 = 비선형 자료구조 : 트리 트리란? : 구조가 트리처럼 생겨서 이름이 트리 ㅋㅋ ex) 결정 트리 : 인간의 의사 결정 구조를 표현한 한 가지 방법 - 트리의 용어들 노드 : 트리의 구성 요소 루트 노드 (root) : 가장 높은 곳에 있는 노드 서브 트리 (sub tree) : 나머지 노드 간선 (edge) : 루트와 서브트리를 연결하는 선 노드의 종류 : 부모 노드, 자식 노드, 형제 노드,..

3. 연결 리스트로 구현된 리스트

연결 리스트 (linked list) 연결된 표현 (linked representation) : 동적으로 크기가 변할 수 있고 삭제나 삽입 시에 데이터를 이동할 필요가 없는 표현 => 포인터를 사용하여 데이터를 연결함 => 리스트 뿐만 아니라 다른 자료구조 (트리, 그래프, 스택, 큐)등을 구현한는데도 많이 사용됨 연결 리스트 : 물리적으로 흩어져 있는 자료들을 서로 연결하여 하나로 묶는 방법 => 상자를 연결하는 줄은 포인터(pointer)로 구현됨 장점 중간에 삽입(삭제)하는 문제가 쉽게 해결됨 데이터를 저장할 공간이 필요할 때마다 동적으로 공간을 만들엇 쉽게 추가할 수 있음 단점 배열로 구현한 리스트에 비하여 상대적으로 구현하기 어려워서 오류가 나기 쉬움 데이터뿐만 아니라 포인터도 저장해야 하므로 ..