자료구조10 정렬 정렬과 레코드- 순서가 없는 사무들을 순서대로 나열하는 작업으로 오름차순, 내림차순이 있다- 정렬시켜야 할 대상을 레코드라 칭함- 필드라는 보다 작은 단위로 구성- key는 자료 정렬하는데 사용되는 기준이 되는 특정 값이다.- 레코드를 키의 순서로 재배열 하는 작업 정렬 실행방법- 비교식 정렬 : 비교할 각 키값을 한 번에 2개 비교 후 교환함으로써 정렬- 분배식 정렬 : 키 값을 기준으로 하여 자료를 여러개 부분집합으로 분해, 각 부분집합을 정렬함으로써 전체를 정렬 정렬 장소- 내부정렬 : 컴퓨터 메모리 내부에서 정렬- 외부정렬 : 메모리의 외부인 보조 기억장치에서 정렬 내부정렬에서 비교식과 분배식- 정렬할 자료를 메인 메모리에 올려서 정렬, 정렬 속도가 빠르지만 정렬할 수 있는 자료의 양이 메인 메모.. 2024. 8. 14. 문자열 검색 문자열 검색이란?- 어떤 문자열 안에 다른 문자열이 포함되어있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것을 칭함- 검색되는 쪽의 문자열을 텍스트(text), 찾아내는 문자열을 패턴(patton)이라 칭함- 문자열 검색 알고리즘에서 가장 기초적이고 단순한 방법은 브루트 포스법으로 선형 검색을 단순하게 확장한 알고리즘- 단점으로는 이미 검사한 위치를 기억하지 못하므로 브푸트 포스법은 효율이 좋지 않음, 즉 일치하지 않는 문자를 만나면 다시 패턴의 첫 문자부터 검색 수행 KMP법이란?- 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴의 이동을 되도록이면 크게 하는 알고리즘- 몇 번째 문자부터 검사를 다시 시작할지 패턴을 이동할 때마다 계산한다면 좋은 .. 2024. 8. 2. 재귀 알고리즘 재귀란?- 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우- 재귀적 정의를 효과적으로 사용하면 프로그램을 간결하고 효율성 좋게 작성이 가능- 재귀의 대표적 예시 : 팩토리얼- 아래 사진은 함수 동작 과정을 그림으로 표현한 사진이다. 직접재귀와 간접재귀- 자신과 똑같은 함수를 호출하는 방식을 직접재귀- a() 함수가 b() 함수를 호출하고 b() 함수가 다시 a()함수를 호출하는 구조, 즉 다른 함수를 통해 자신과 똑같은 함수 호출- 유클리드 호제법이란 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이며 여기서 호제법이라는 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다.- 파이썬에서는 최대 공약수를 구하는 표준라이브러리 math 모듈에.. 2024. 8. 2. 그래프 그래프란?- 연결되어 있는 객체 간의 관계를 표현하는 자료구조- 객체를 나태내는 정점 또는 노드와 객체를 연결하는 간선 또는 링크의 집합- 정점(vertax) : 여러가지 특성을 가질 수 있는 객체- 간선(edge) : 정점들 간의 관계를 의미-G = (V,E)로 표시, V는 그래프에 있는 정점들의 집합이며 E는 정점을 연결하는 간선들의 집합이다. 그래프의 종류- 무방향 그래프( undirected graph ) : 두 정점을 연결하는 간선에 방향이 없는 그래프로 간선을 통해서 양방향 이동이 가능하다. 정점 A와 정점 B를 연결하는 간선을 (A,B)로 표현하고 (A,B) = (B,A)이다.- 방향 그래프( directed graph ) : 간선에 방향이 있는 그래프로 간선을 통해서 한쪽 방향으로만 갈 수.. 2024. 7. 27. 트리 트리란?- 원소들 간에 계층적인 관계를 나타내는 계층형 자료구조- 원소들 간에 1:n 관계를 가지는 비선형 자료구조(순서가 존재)- 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양 구조- 가계도, 컴퓨터 폴더구조, 탐색과 힙의 결정트리에 사용- N-링크/ 자식-형제 표현법 트리용어- 노드(node) : 트리의 구성요소- 간선(edge) : 노드를 연결하는 선 (부모 - 자식)- 루트(root) : 부모가 없는 노드, 최상위 노드- 서브트리(subtree) : 하나의 노드와 자손들로 이루어짐(루트를 제외한 나머지 노드들)- 단말노드(terminal node) : 자식이 없는 노드- 비단말노드(nonterminal node) : 자식이 있는 노드- 조상노드(ancesor node) : 간선을 따라 루.. 2024. 7. 26. 자료구조 - 연결리스트 연결리스트란?- 데이터가 순서대로 나열되고 각 데이터가 연결되어있는 구조, 자료의 논리적인 순서와 물리적인 순서 불일치- 각 원소에 저장되어 있는 다음 원소의 주소에 의해 순서가 연결되는 방식- 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음- 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현해 크기 변경이 유연하고 효율적으로 메모리를 사용- 삽입과 삭제가 효율적이지만 구현이 복잡하다- 크기가 제한되지 않으며 하나의 링크 필드를 이용하여 연결하고 후속 노드를 찾기 쉽다- 마지막 노드의 링크 값은 NULL이다- 자료를 노드에 담아 보관하며 필요할 때 마다 노드를 생성- 시작노드는 헤드포인터뿐이다.- 연결리스트에서 각각의 원소를 노드(NODE)라고 하며 노드가 갖고 있는 것은 데이터와 뒤쪽 .. 2024. 7. 19. 이전 1 2 다음
