자료구조 + 알고리즘

자료구조 중 이진트리를 공부하자. ∨ 개념 이진트리는 모든 노드의 차수(=자식노드 수)가 2개 이하인 트리이다. ∨ 특징 노드 N개짜리 이진트리의 간선은 N-1개다 - 노드 하나는 무조건 부모노드 하나랑 연결되어있음 AND 루트노드는 부모가 없음 - 따라서 N-1개 노드 개수와 트리 높이간의 관련성 Let : 트리 높이를 H라고 하자 (유의: 루트부터 어떤 노드까지 다다르는 간선의 수가 높이다!) Then : 노드의 개수는 최소 H+1개 ~ 최대 2^(H+1)-1개 Why? 그림으로 보자 ㄴ> 잠시만! 이진트리의 노드는 '왼쪽자식노드' or '오른쪽자식노드'를 갖는다. ㄴ> 위 좌측 그림에서는 내가 일자로 그렸는데.. 엄밀히는 왼or오 자식 노드를 갖는 상태임을 유의! ∨ 이진트리 종류 - 포화이진트리 ..

https://github.com/yyhh314/DataStructurePractice/tree/main/Client_Server_Queue GitHub - yyhh314/DataStructurePractice Contribute to yyhh314/DataStructurePractice development by creating an account on GitHub. github.com 실습 소스코드는 깃헙에 올려두었다. Queue구조 (Linked / Array)를 실습했다. ArrayQueue는 직접 구현하며 실습해봤다. 역시 LinkedQueue가 훨씬 마음에 든다. 실습 후 가볍게 정리 ↓ Queue 구조를 통해 Server / Client가 동작하는 과정을 실습할 수 있어서 재밌었다.

합병정렬의 시간복잡도는 O(NlogN) (또는 세타(NlogN)) 이 사실은 다들 알고 있을 겁니다. 그리고 이 O(NlogN)이라는 복잡도를 어떻게 따지느냐? 다들 한번쯤 해봤을 것입니다. 혹시 깔끔한 이해 없이 지나갔다면 다시 한번 천천히 해봅시다 그 전에! 분할정렬 자체에 대한 개념이 모호하신 분은 이 포스팅을 읽고 다시 돌아오는 것을 추천합니다. 시작!! 아래 그림 많이 보셨을 겁니다. 합병정렬!! 이 합병정렬의 복잡도가 왜 NlogN인지 차근차근 설명할텐데요, 순서대로 사고하면서 천천히 해봅시다 먼저, 절반으로 분할해가는 과정을 봅시다. - 초기 배열의 요소수는 N개입니다. - 분할정렬 함수의 인자로는 "배열", "p", "r"이 들어옵니다. p는 분할대상인 요소가 시작하는 인덱스였죠. 초기 함..

합병 정렬 (Merge sort)이란? 분할정복알고리즘 중 하나입니다. 일단 분할정복법이 뭔지 먼저 설명하는 게 좋을 듯합니다. 분할정복 (Divide and Conquer) 분할정복은 다음의 3단계로 이루어집니다. 1. Divide --- 문제를 subproblem으로 나눕니다. 2. Conquer --- 그 subproblem을 재귀적으로 주루룩 정복합니다. 이때 Base case까지 다다르게 됩니다. Base case란, subproblem이 충분히 작으면 그냥 아주 쉽게, 거의 그 자체 풀리는 수준의 케이스입니다. 3. Combine --- 2단계에서 subproblem들을 정복해 해답을 얻었습니다. 이 답들을 Combine해서 맨 처음의 original problem의 해답으로 얻어냅니다. 이것..

삽입정렬이란? 어떤 숫자 배열이 Input으로 들어왔을 때, 뒤죽박죽인 그 수열을 오름차순으로 정렬해나가는 과정을 거칩니다. 결국 Output은 "오름차순 수열"로 "정렬"됩니다. 이때, 삽입정렬에서는 정렬시에 다음과 같은 방식을 따릅니다 "이미 정렬된 앞 원소들"과 "기준이 되는 수인 key"를 대소비교합니다. 그리고 key인 수를 "이미 정렬된 앞 수열"의 적절한 자리에 삽입합니다. 이때, 이미 정렬되어있는 앞 원소들과 key를 차례차례 대소비교해가며 삽입의 위치를 정합니다. 이러한 정렬 방식을 삽입정렬이라고 합니다. 예를 들어 3 8 5 2 1이라는 수열이 있다고 합시다. 왼쪽에서 오른쪽 방향으로 차례차례 수의 크기를 비교해나가며 정렬을 쭉 하게 됩니다. 어떤 수를 그 앞자리에 있는 수와 하나하나 ..

알고리즘 문제를 풀다보면 재귀함수를 비재귀적으로 구현해보라고 하는 문제가 자주 나온다. 얼마 전에도 재귀함수를 비재귀적으로 구현해보는 문제를 접했는데, 재귀함수의 동작 과정을 이해하고 받아들이는 큰 도움이 되었다: https://splendidlolli.tistory.com/343 재귀의 제거 | Stack에 잠시 저장해두기 | 재귀의 과정 이해 | 비재귀적 구현해보기 코드출처: Doit! 자료구와 함께 배우는 알고리즘 입문 (자바 편)의 174~177페이지 다음의 간단한 재귀함수를 비재귀적으로 표현해보자. 이 활동은 재귀함수의 동작 과정의 이해를 돕는다. 이번 포스 splendidlolli.tistory.com 위 링크에서 풀었던 재귀함수 문제는, 메서드 내부에서 'recur(n-1)->print(n)..

하노이의 탑 알고리즘 이해 돕기 하노이의 탑은 크게 어렵지 않고 간단해서 초보자도 설명을 차근히 읽어본다면 이해하기 어렵지 않다. 하지만 내 기준에서 '코드를 이렇게 설명하면 더 좋은 이해가 될 것 같다'라는 생각에 이 글을 올린다. [하노이의 탑 알고리즘의 기본적 도해] 시작기둥1에서 목적기둥3으로 n개의 원반을 모두 옮기는 단계를 보여주는 흔한 그림이다. 위 그림에서 볼 수 있듯이, 하노이의 탑을 이루는 n개의 원반은 '맨 아래원반'과 '나머지 원반묶음'이라는 두 분류로 바라봐야 한다. 그리고 나서 n-1원반묶음을 또 분리하여 '맨밑원반'과 'n-2원반묶음'으로 나누는 방식을 통해서, 원반묶음의 이동을 연쇄적으로, 재귀적으로 바라볼 수 있다. 그럼 이제 슬슬 코드로 확인해보자 재귀함수의 대표적 사례인..

코드출처: Doit! 자료구와 함께 배우는 알고리즘 입문 (자바 편)의 174~177페이지 다음의 간단한 재귀함수를 비재귀적으로 표현해보자. 이 활동은 재귀함수의 동작 과정의 이해를 돕는다. 이번 포스팅의 학습 목적은 "재귀함수의 동작 원리를 깔끔하게 이해하여, 같은 동작을 비재귀적으로 표현할 줄 알기"이다. 1. 다음의 재귀함수를 보자. static void recur(int n) { if (n>0) { recure(n-1); System.out.println(n); recur(n-2); } } 두 번의 재귀호출이 존재하는 메서드 recur이다. 동작 설명: 메서드의 인자로 어떤 양수 n이 들어오면, - recur(n-1) 동작이 완전히 수행된 후 - n을 출력하고 - recur(n-2) 동작이 완전히..

이번에는 다음 문제를 해결해보았다. 내가 해결한 모양새는 대충 이렇다. 실행부 말고, Stack을 구현한 클래스 내용만 살짝 올려본다. 1. 변수, 예외, 생성자 //변수 private int max; private int ptrA; private int ptrB; private int[] stk; //예외 public class EmptyStack3Exception extends RuntimeException { public void EmptyStack3Exception() {} } public class OverflowStack3Exception extends RuntimeException { public void OverflowStack3Exception() {} } //생성자 public Stac..

제네릭 스택의 구조 임의의 객체를 담을 수 있는 제네릭 스택의 구조를 살펴보자. - 제네릭 클래스는 클래스명 뒤에 과 같은 파라미터를 붙여서 선언한다. - 제네릭 스택 사용 이유: 임의의 객체를 스택(배열)에 담을 수 있다. 대략적인 구조 - 스택 관련 필드 - 스택 관련 메서드 - 예외처리 부분 - 생성자 간단히 보자면 아래와 같다. public class Gstack { //제네릭 클래스로 선언되어있다. private int max; // 스택의 용량 private int ptr; // 스택 포인터 private E[] stk; // 스택 본체 // 생성자 public Gstack(int capacity) { ptr = 0; max = capacity; try { stk = (E[]) new Obje..