본문 바로가기

알고리즘

 (105)
원형 이중 연결 리스트 만들기 지난 글 : [알고리즘/Do it 알고리즘] - 배열 커서로 연결 리스트 만들기 원형 리스트 살펴보기 head ↓ A → B → C → D → E → F ↑ ↓ ↑←←←←←←←←←←←←←←←←←←←← 위 그림처럼 꼬리 노드가 머리 노드를 가리키는 연결 리스트를 원형 리스트(circular list)라 한다. 원형 리스트는 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조다. 보통의 연결 리스트와 다른 점은 꼬리 노드의 다음 노드를 가리키는 포인터가 null이 아니라 머리 노드의 포인터라는 점이다. 개별 노드의 자료형은 보통의 연결 리스트와 같다. 이중 연결 리스트 살펴보기 연결 리스트의 가장 큰 단점은 다음 노드는 찾기 쉽지만 앞쪽 노드는 찾기 어렵다는 것이다. 이런 단점을 개선한 자료구조가 이중..
배열 커서로 연결 리스트 만들기 지난 글 : [알고리즘/Do it 알고리즘] - 포인터로 연결 리스트 만들기 배열 커서로 연결 리스트 만들기 이전 글에서 배운 포인터를 이용한 연결 리스트는 '노드의 삽입, 삭제를 데이터 이동 없이 수행한다'는 장점이 있지만 삽입, 삭제를 수행할 때마다 노드용 객체를 위한 메모리 영역을 확보하고 해제하는 과정이 필요하다. 메모리 영역을 확보하고 해제하는 데 드는 비용은 절대 무시할 수 없다. 프로그램 실행 중 수가 크게 바뀌지 않는 경우, 또는 데이터 수의 최댓값을 미리 알 수 있는 경우 배열을 사용해 연결 리스트를 만들면 효율적으로 운용할 수 있다. 여기서 다음 노드를 가리키는 뒤쪽 포인터는 다음 노드에 대한 포인터가 아니라 당므 노드가 들어 있는 배열 요소의 인덱스다. 이 인덱스 포인터를 커서(cur..
포인터로 연결 리스트 만들기 지난 글 : [알고리즘/Do it 알고리즘] - 리스트 포인터로 연결 리스트 만들기 리스트에 데이터를 삽입할 때 노드용 객체를 만들고 삭제할 때 노드용 객체를 없애면 배열로 리스트를 만들 때 발생하는 문제를 해결할 수 있다. 이런 노드를 구현하는 것이 아래 클래스 Node다. class Node { E data;//데이터를 참조 Node next;//다음 노드를 참조 } Node는 제네릭으로 구현되므로 데이터형 E는 임의의 클래스형이 허용된다. Node의 이미지를 좀 더 엄밀히 나타내면 Node { data --> E(데이터) next --> Node(다음 노드) { data --> E(데이터) next --> Node(다음 노드) { data --> E(데이터) next --> Node(다음 노드) }..
리스트 지난 글 : [알고리즘/Do it 알고리즘] - 보이어 • 무어법 리스트 살펴보기 참고 : [알고리즘/알고리즘 도감] - 리스트 리스트란 데이터를 순서대로 나열해 놓은 자료 구조를 말한다. *이전에 배운 스택과 큐도 리스트 구조로 되어 있다. 선형 구조를 갖는 리스트에는 선형 리스트(linear list)와 연결 리스트(linked list)가 있다. 선형 리스트는 데이터가 배열처럼 연속(linear)하는 메모리 공간에 저장돼 순서를 갖는다. 연결 리스트는 데이터가 메모리 공간에 연속적으로 저장되어 있지 않더라도 각각의 데이터 안에 다음 데이터에 대한 정보를 갖고 있어 서로 연결(linked)된다. 이는 위 참고에 잘 나와 있다. 배열로 선형 리스트 만들기 비상 연락망을 선형 리스트로 저장하기 위해 간단..
보이어 • 무어법 지난 글 : [알고리즘/Do it 알고리즘] - KMP법 보이어 • 무어법 알아보기 보이어(R. S. Boyer)와 무어(J. S. Moore)가 만든 보이어 • 무어법은 KMP법보다 이론과 실제 모두에서 더 우수하다 한다. 이 알고리즘은 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정한다. 텍스트 "ABCXDEZCABACABAC"에서 패턴 "ABAC"를 검색하는 경우를 예로 알고리즘을 살펴보자. 아래의 a처럼 텍스트와 패턴의 첫 번째 문자를 위아래로 겹치고 패턴의 마지막 문자 'C'를 검사한다. 텍스트의 'X'는 패턴에 없다. 이 문자는 패턴에 아예 없으니 b ~ d처럼 패턴을 1 ~ 3칸 옮긴다 해도 문자열 "ABCX"와 패턴..
KMP법 ABCABD ========================================== -00120 지난 글 : [알고리즘/Do it 알고리즘] - 브루트 - 포스법 KMP법 알아보기 브르투 - 포스법은 일치하지 않는 문자를 만난 단계에서 그때까지 검사한 결과를 버리고 패턴을 텍스트의 다음 칸으로 옮겨 패턴의 첫 번째 문자부터 다시 검사한다. 하지만 KMP법은 검사한 결과를 버리지 않고 이를 효과적으로 활용한다. 텍스트 "ZABCABXACCADEF"에서 패턴 "ABCABD"를 검색하는 경우를 예로 알고리즘을 이해하자. 1. 텍스트, 패턴의 1번째 문자부터 순서대로 검사한다. 텍스트의 1번째 문자 'Z'는 패턴에 없기에 바로 일치하지 않는다 판단한다. =============================..
브루트 - 포스법 지난 글 : [알고리즘/Do it 알고리즘] - 도수 정렬 문자열 검색 알아보기 문자열 검색이란 어떤 문자열 안에 특정 문자열이 있는지 조사하고, 들어 있다면 그 위치를 찾는 것을 말한다. 예로 문자열 "String", "King"에서 "in"을 검색하면 문자열 검색에 성공한다. 하지만 문자열 "Queen"에서 "in"을 검색하면 문자열 검색에 실패한다. 지금부터 이해를 돕기 위해 검색할 문자열을 패턴(pattern), 문자열 원본을 텍스트(text)라 하자. 브루트 - 포스법 알아보기 텍스트 "ABACDEFGHA"에서 패턴 "ABC"를 브루트 - 포스법(brute force method)을 사용해 검색하는 과정을 간략히 살펴보자. a 텍스트의 첫 문자 'A'부터 시작하는 3개의 문자와 "ABC"가 일치..
도수 정렬 지난 글 : [알고리즘/Do it 알고리즘] - 힙 정렬 도수 정렬 알아보기 지금까지 배운 정렬 알고리즘은 두 요소의 키값을 비교해야 했다. 하지만 오늘 배우는 도수 정렬은 요소를 비교할 필요가 없다. 10점 만점 테스트에서 학생 9명의 점수를 예로 도수 정렬 알고리즘으로 살펴보자. 도수 정렬 알고리즘은 도수분포표 만들기, 누적도수분포표 만들기, 목표 배열 만들기, 배열 복사하기 등 4단계로 이루어진다. 1단계 : 도수분포표 만들기 먼저 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표를 작성한다. 배열 a 5702410313 도수분포표를 저장하기 위해 배열 f를 사용한다. 먼저 배열 f의 모든 요솟값을 0으로 초기화하고, 배열 a를 처음부터 스캔하며 도수분포표를 만든다...

티스토리툴바