단일 연결 리스트(Singly Linked List) 직접 구현 노드 class Node { E data; Node next; Node(E data) { this.data = data; this.next = null; } } 노드 추가 //리스트의 가장 뒷쪽에 데이터 추가 public void add(E data) { Node newNode = new Node(data); if (head == null) head = newNode; else { Node currentHead = head; while (currentHead.next != null) currentHead = currentHead.next; currentHead.next = newNode; } } 노드 삽입 //리스트의 원하는 인덱스에 데이터..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 을 개인적으로 정리하는 글임을 알립니다. 문자열 탐색 문자열 탐색이란 어떤 문자열 안에 특정 문자열이 들어 있는지를 조사하고, 들어있다면 그 위치를 찾는 것을 말한다. 이 글에서는 검색할 문자열을 패턴이라 하고 문자열 원본을 텍스트라고 하겠다. 문자열 탐색 알고리즘에는 아래와 같은 방법이 있다. 브루트 포스 KMP 보이어-무어 브루트 포스 브루트 포스(Brute Force)는 가장 간단하고 직접적인 문자열 탐색 방법 중 하나이다. 이 방법은 텍스트에서 패턴을 한 글자씩 비교하면서 탐색하는 단순한 방법이다. 각 가능한 위치에서 비교를 수행하고, 일치하지 않으면 다음 위치로 이동하여 계속 비교를 수행한다. 브루트 포스 문자열 탐색 알고리즘의 주요 특..

Do it! 자료구조와 함께 배우는 알고리즘 입문[자바편] 을 개인적으로 정리하는 글임을 알립니다. 정렬 정렬은 이름, 학번, 키 등 핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다. 정렬 알고리즘의 안정성 동일한 키 값을 가진 요소들의 상대적인 순서가 정렬 전과 정렬 후에도 유지되는 정렬 특성을 나타낸다. 안정적인 정렬 알고리즘은 동일한 키 값을 가진 요소들 간의 순서를 보존하는 특성을 갖는다. 위 그림의 왼쪽과 같이 학번, 점수가 학번 순으로 나열되어있다. 이때 점수를 기준으로 오름차순 정렬을 하면 오른쪽 그림과 같다. 점수가 같을 때는 학번이 작은 사람을 앞쪽에 배치한다. 안정된 정렬이란 이렇게 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것을 말한다..

이 글은 이것이 자료구조+알고리즘이다 with C 언어(저자:박상현) 책 내용을 개인적으로 정리하는 글임을 알립니다. 다익스트라 알고리즘의 개념 다익스트라 알고리즘은 여러가지 경로중에 목적지에 도착하기 위해 가장 빠른 경로를 찾아주는 알고리즘이다. 프림 알고리즘이 단순히 간선의 길이를 이용하여 어떤 간선을 먼저 연결할지 결정하는 데 비해 데이크스트라 알고리즘은 경로의 길이를 감안해서 간선을 연결, 데이크스트라 알고리즘의 경우 사이클이 없는 방향성 그래프에 한해서만 사용 가능 다익스트라 알고리즘 동작 방식 ❶ : 각 정점에는 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 각 정점에 대한 경로의 길이를 ∞(무한대)로 초기화 ❷ : 시작 정점의 경로 길이를 0으로 초기화하고(시작 정점에서 ..

이 글은 이것이 자료구조+알고리즘이다 with C 언어(저자:박상현) 책 내용을 개인적으로 정리하는 글임을 알립니다. 최소 신장 트리 가중치 그래프 가중치 그래프 : 그래프에서 정점과 정점을 잇는 간선을 지나기 위해 가중치라는 새로운 속성을 부여한 그래프 신장 트리(Spanning Tree) 모든 정점을 연결하는 트리 신장 트리는 그래프의 하위 개념 모든 정점을 연결하는 그래프(네트워크 그래프)에서 사이클이 되는 간선을 제거하면 신장 트리가 된다. 따라서 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다. 최소 신장 트리 최소 신장 트리는 최소 가중치 신장 트리라고 부르기도 한다. 최소 신장 트리는 그래프의 모든 정점을 최소 비용으로 연결하는 부분 그래프 또는 트리의 모든 노드를 최소 비용으로 연결하..

이 글은 이것이 자료구조+알고리즘이다 with C 언어(저자:박상현) 책 내용을 개인적으로 정리하는 글임을 알립니다. 위상 정렬 위상 : 어떤 정점이 다른 정점과의 관계 속에서 가지는 위치 이 말은 그래프 내 서로 인접한 정점 사이의 관계에 위치라는 속성이 존재한다는 뜻이다. 이 위치는 앞/뒤일 수도 있고, 위/아래일 수도 있다. 이 글에서는 앞/뒤 관계라고 가정한다. 앞:간선을 뻗어내는 정점 뒤: 간선을 받아들이는 정점 이 앞/뒤를 차근차근 정렬하는 작업이 위상 정렬이다. 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때, 그 순서를 결정해 주기 위해 사용한다. 위상 정렬은 여러 개의 답이 존재할 수 있다. 위상 정렬의 시간복잡도 V = 정점의 개수, E = 간선의 개수 O(V + E) 위..

보이어 무어 알고리즘은 패턴의 오른쪽부터 비교하여 텍스트 문자를 모두 비교하지 않아도 탐색이 가능한 알고리즘이다. 전체 문자열과 찾고 싶은 문자열(패턴) 비교 시 문자열의 가장 뒷부분 위치를 비교하고, 다르면 일정 길이만큼 이동하여 비교를 계속하는 방법이다. 보이어무어 알고리즘은 두 가지의 이동으로 나뉜다. 나쁜 문자 이동(Bad Character Shift) 착한 접미부 이동(Good Suffix Shift) 두 가지의 이동을 적절히 이용하여 문자열 탐색을 할 때 최고의 시너지가 나온다. 즉, 전체 문자열과 찾고 싶은 문자열을 비교했을 때 불일치가 발생하면 나쁜 문자 이동과 착한 접미부 이동을 모두 검토해서 더 멀리 옮겨가는 이동 방법을 선택하게 된다. Prefix(접두사), Suffix(접미사) Pr..

KMP 알고리즘이란 이 알고리즘을 만든 Knuth, Morris, Prett 이렇게 3명의 앞 글자를 하나씩 따서 명명하여 KMP 알고리즘이라고 한다. KMP 문자열 탐색 알고리즘의 시간 복잡도는 O(N+M)이다.(전체 문자열 길이 = N, 찾는 문자열 길이 = M) LPS 배열 계산 O(M) + 매칭 O(N) KMP 알고리즘의 핵심 아이디어 IDX 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Text A B C D A B D A B C D A B E A B C D Pattern A B C D A B E 위 표에서 text와 pattern 모두 0, 1번째 인덱스와 4, 5번째 인덱스의 값이 동일하다는 것을 알 수 있다. 즉, 앞에서 2개 뒤에서 2개가 같다는 것을 알 ..