[서론] 알고리즘 풀다가 트리에 대한 개념이 너무 오래전에 배워가지고 가물가물하기 때문에 블로그 글을 작성하기로 하였다. 내가 지금 실무에 있으면서 트리 구조로 이루어진 것이 있을까? 라는 생각을 하면서 공부를 하긴 했는데 아직 못찾은거 같다. 그래도 자료구조에 대한 공부를 하면 실무에서 어떤 원리로 이루어지는지 금방 파악을 할수 있어서 좋은거 같다. 이제 본론으로 들어가보자! [목차]1. 트리란 무엇인가?2. 트리와 관련된 개념들( 형제, 루트, 레벨 등등) 3. Tree Code로 표현하기 1. 트리란 무엇인가? 트리의 구조란? 위키 백과에서 찾아보았다. 아래 내용으로 트리를 정의하고 있었다. 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회..

[목차] 1. LinkedList란 무엇인가? 2. LinkedList를 구현하려면 Node가 필요하다 2.1 python Node구현하기 2.2 java Node 구현하기 3. LinkedList를 소스로 구현해보자 3.1 python LinkedList 구현해보기 3.2 java LinkedList 구현해보기 4. BigO표기 1. LinkedList란 무엇인가? 일단 LinkedList란 말 그대로 연결된 리스트라는 뜻이다. 그렇다면 리스트란 무엇인가? 리스트란 데이터를 연속적으로 저장하는 자료구조이다. 나무 위키에서 본 리스트의 정의는 아래와 같다. 추상적 자료형, 자료구조의 하나. 순열(Sequence)이라고도 불리며, 순서를 가지고[1] 일렬로 나열한 원소들의 모임으로 정의한다. 순서가 있다는..

1. 버블 정렬이란? 거품정렬 또는 버블정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 양방향으로 번갈아 수행하면 칵테일 정렬이 된다. 출처 : https://ko.wikipedia.org/wiki/거품_정렬 거품 정렬 - 위키백과, 우리 모두의 백과사전 무작위 배열수의 거품 정렬 예 거품 정렬 또는 버블 정렬( - 整列, 영어: bubble sort, sinking sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O ( n 2 ) {\displaystyle O(n^{2})} 로 상당 ko.wikipedi..

삽입정렬이란? 삽입정렬(Insert Sort)은 정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 찾아 삽입하는 방법이다. 삽입정렬에서 정렬할 자료가 두개가 있다. 먼저 S(Sorted)와 U(United)로 나누어져 있다. 앞부분 원소부터 정렬을 수행하여 정렬된 앞부분의 원소들은 부분집합 S가 되고 아직 정렬되지 않은 나머지 원소들은 부분집합 U가 된다. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입하여 부분집합 S의 원소는 하나씩 늘리고 부분집합 U의 원소는 하나씩 줄인다. U의 원소를 모두 삽입하여 공집합이 되면 삽입 정렬이 완성된다. 위의 글처럼 책에서는 삽입정렬의 정의가 기술되어있다. 쉽게 말해서 두개 리스트로..

Kadane 알고리즘 1234567891011121314151617181920212223242526272829import java.io.*;// Java program to print largest contiguous array sumimport java.util.*; class Kadane{ public static void main (String[] args) { int [] a = {-2, -3, 4, -1, -2, 1, 5, -3}; System.out.println("Maximum contiguous sum is " + maxSubArraySum(a)); } static int maxSubArraySum(int a[]) { int size = a.length; int max_so_far = In..