얄루의 개발일기🥑

1. 포인터를 이용한 연결 리스트란? 노드마다 뒤쪽 노드를 가리키는 포인터가 포함되도록 구현하는 연결 리스트를 포인터를 이용한 연결리스트라고 한다. 2. 포인터로 연결 리스트 만들기 연결 리스트에 데이터를 삽입할 때 노드용 인스턴스를 생성하고, 데이터를 삭제할 때 노드용 인스턴스를 없애면 앞에서 제시한 데이터를 옮기는 문제를 해결할 수 있다. Node는 데이터용 필드 data와 별도로 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 갖는다. 이처럼 같은 형의 인스턴스를 참조하는 필드가 있는 구조를 자기 참조형이라고 한다. 3. 포인터로 연결 리스트 구현하기 #포인터로 연결 리스트 구현하기 class Node: def __init__(self,data): #초기화 self.data ..

1. 리스트란? 데이터에 순서를 매겨 늘여 놓은 자료구조를 리스트라하고 리스트 중 가장 단순한 리스트 구조인 연결리스트를 알아보도록 하자 2. 연결 리스트란? 순서가 있는 데이터를 늘어놓은 자료구조로 구조가 단순한 리스트로 선형리스트(Linear list) 또는 연결 리스트(Linked list)가 있다. 연결 리스트에서 각각의 원소를 노드라고 하고 노드가 갖고 있는 것은 데이터와 뒤쪽 노드를 가리키는(참조하는) 포인터이다. 특별히 맨 앞에 있는 노드를 머리 노드, 맨 끝에 있는 노드를 꼬리 노드라고 한다. 또 각 노드에서 바로 앞에 있는 노드를 앞쪽 노드, 바로 뒤에 있는 노드를 뒤쪽 노드라고 한다. 3. 배열로 연결 리스트 만들기 배열로 연결 리스트를 만들게 되면 삽입, 삭제 과정에서 계속 불필요한 ..

1. 보이어 · 무어법이란? 보이어 · 무어법은 KMP 알고리즘보다 이론이나 실제 효율 면에서 뛰어난 알고리즘이다 . 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행한다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정한다. 이처럼 패턴의 마지막 문자를 텍스트와 비교하여 일치하면 맨 뒤에 문자에서 1칸씩 앞으로가며 문자를 비교해야 한다. 2. 보이어 · 무어 알고리즘 구현 코드 def bm(txt,pat): skip = [None]*256 # 건너뛰기 표 for pt in range(256): skip[pt] = len(pat) for pt in range(len(pat)): skip[ord(pat[pt])] = len(pat) - pt -1 # 검색..

1. KMP법이란? 브루트 포스법은 일치하지 않는 문자를 만나면 이전 단계에서 검사했던 결과를 버리고 패턴의 첫 문자부터 다시 검사를 수행한다. 하지만 KMP법은 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘이다. 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하고 패턴의 이동을 되도록이면 크게 하는 알고리즘이 KMP 알고리즘이다. 2. KMP 알고리즘 구현 코드 # KMP법으로 문자열 검색하기 def kmp(txt, pat): pt = 1 # 텍스트를 따라가는 커서 pp = 0 # 패턴을 따라가는 커서 skip = [0] *( len(pat) + 1) # 건너뛰기 표 skip[pt] = 0 while pt != len(pat): if pat[pt] == pat[pp..

1. 문자열 검색이란? 문자열 검색(String searching)은 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것을 말한다. 이때 문자열을 텍스트, 찾아내는 문자열을 패턴이라고 한다. 2. 부르트 포스법으로 문자열 찾아내기 검색 알고리즘 중 가장 기초적이고 단순한 브루트 포스법(brute force method)부터 알아보도록 하겠다. 선형 검색을 단순하게 확장한 알고리즘이라 단순법이라고도 브루트 포스를 부르기도 한다. #브루트 포스법으로 문자열 검색하기 def bf(txt,pat): pt = 0 #텍스트를 따라가는 커서 pp = 0 #패턴을 따라가는 커서 while pt != len(txt) and pp != len(pat): if tx..

1. 힙 정렬 알아보기 힙 정렬은 힙의 특성을 이용해 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 두 값의 대소 관계가 일정하면 힙이라고 할 수 있다. 이때 형제사이의 대소 관계는 일정하지 않는다. 최대 힙(Max heap) 부모의 값이 자식의 값보다 항상 클 때 최소 힙(Min heap) 부모의 값이 자식의 값보다 항상 작을 때 💁‍♀️ 완전 이진 트리란? 트리의 한 종류로 완전 이진 상태라는 특징이 있고, '완전'은 부모는 왼쪽 자식부터 추가하여 모양을 유지하라는 뜻으로 '이진'은 부모 노드가 가질 수 있는 자식 노드의 최대 개수는 2개라는 의미이다. 즉, 왼쪽부터 추가하..

퀵 정렬(Quick sort)은 가장 빠른 정렬 알고리즘으로 알려져 있고 또한 널리 사용된다. 배열을 두 그룹으로 나누기 5 7 1 4 6 2 3 9 8 pl x pr 그룹을 나누려면 피벗 이하인 원소를 배열 왼쪽(맨 앞쪽)으로, 피벗 이상인 원소를 배열 오른쪽(맨 뒤쪽)으로 옮겨주어야 한다. a[pl] >= x가 성립하는 원소를 찾을 때까지 pl을 오른쪽 방향으로 스캔한다. 👉 왼쪽에서부터 시작해서 피벗보다 큰 값을 찾는 과정 a[pr] >= x가 성립하는 원소를 찾을 때까지 pr을 왼쪽 방향으로 스캔한다. 👉 오른쪽에서부터 시작해서 피벗보다 작은 값을 찾는 과정 5 7 1 4 6 2 3 9 8 -----------------> pl pr pl pr # 배열을 두 그룹으로 나누기 from typing ..

shell sort는 단순 삽입 정렬의 장점은 살리고 단점을 보완해서 더 빠르게 정렬하는 알고리즘이다. 단순 삽입 정렬 6 4 1 7 3 9 8 # 두 번째 원소인 4부터 주목해서 바로 앞의 원소보다 큰지 작은지를 비교해서 바꿔주는 작업 4 6 1 7 3 9 8 # 세 번째 원소인 1을 주목해서 앞의 원소인 6보다 앞의 앞의 원소인 4보다도 앞으로 가야 하기에 맨 앞으로 옮겨준다. 1 4 6 7 3 9 8 # 네 번째 원소 7의 경우엔 앞의 원소 어느 것과 비교해도 다 크기 때문에 그대로 유지한다. 1 4 6 7 3 9 8 1 3 4 6 7 9 8 1 3 4 6 7 9 8 1 3 4 6 7 8 9 # 최종적으로 단순 삽입 정렬을 끝낸 모양 단순 삽입 정렬의 장 · 단점 장점 : 정렬을 이미 마쳤거나 정렬..

정렬 알고리즘 정렬이란? 정렬(sorting)이란 이름, 학번, 학점 등의 키를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다. 오름차순(ascending order) - 값이 작은 데이터를 앞쪽에 늘어놓는 것을 의미한다. 내림차순(descending order) - 값이 큰 데이터를 앞쪽에 늘어놓는 것을 의미한다. 정렬 알고리즘의 안정성 정렬 알고리즘은 안정적인(stable) 알고리즘과 그렇지 않은 알고리즘으로 나눌 수 있다. 안정적인 알고리즘은 정렬한 후에도 순서가 변하지 않고 값이 같은 원소의 순서가 정렬 후에도 유지되는 것을 말한다. 반면 그렇지 않은 정렬 알고리즘은 정렬 후에 원래 순서가 유지된다는 보장을 할 수 없다. 내부 정렬과 외부 정렬 하나의 배열에..

재귀 알고리즘의 기본 여러가지 재귀 알고리즘과 분석 방법, 그리고 재귀 알고리즘을 비재귀적으로 구현하는 방법을 살펴보도록 하자 재귀 알아보기 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀(recursion)이라고 한다. 재귀의 개념을 표현한 예로, 화면 가운데 계속해서 같은 화면이 반복해서 나타난다. 이러한 재귀의 개념을 사용하여 1,2,3,4,,,과 같이 무한하게 이어지는 자연수를 다음과 같이 정의할 수 있다. 자연수의 정의 1은 자연수이다. 어떤 자연수의 바로 다음 수도 자연수이다. 무한히 존재하는 자연수를 재귀적 정의(recursive definition)를 사용하여 위의 두 문장으로 정의했다. 재귀를 효과적으로 사용하면 이러한 정의뿐만 아니라 프로그램을 간결..