이번 챕터에서는 트리 중 가장 대표적인 binary tree (이진 트리)를 기록할 예정이다. 순서는 다음과 같다. binary tree - binary tree의 정의와 종류 - binary tree의 ADT - binary tree를 linked list로 나타내면? binary tree traversal - tree algorithm 종류 1. Binary Tree 1-1. Binary Tree 정의와 종류 Binary Tree는 각 노드가 최대 2개의 자식노드만 갖는 트리를 의미하며, 정확히 2개만 갖는 트리는 proper binary tree라고 부른다. 참고로 트리의 종류를정짓는 요소는 크게 2가지로 structural property, relational property가 있다. struct..

이번 챕터에서는 정말 중요한 자료구조 중 하나인 트리에 대해 공부하려고 한다. 정리 순서는 아래와 같다. 트리란 무엇인가? Linked Structure for Trees tree method & tree method's running time 그럼 시작! 1. 트리란 무엇인가? 트리는 그래프의 일종으로, 간단하게 이야기하면 노드로 이루어진 계층 구조를 나타낸다. tree라고 정의될 수 있는 조건은 루트노드가 필수로 존재해야 한다 루트 밑에 있는 노드들도 트리 조건을 만족해야한다 자식노드는 부모노드가 1개여야만 한다 정도로 정의할 수 있다. 위 조건을 모두 만족해야 tree라고 정의할 수 있다. 트리는 File systems, Web sites, Databases 등에서 활용하고, linked list로..

이번 챕터에서는 recursion 재귀에 대해 공부해보려고 한다. 자료구조론에서 중요하게 다루게 될 tree가 재귀로 구현되기 때문에 잘 알아둬야한다! 순서는 다음과 같다. 재귀함수로 코드 짜는 방법 binary recursion (이진재귀) 그럼 시쟉🌟 1. Recursion (재귀) 1-1. 재귀함수란? 재귀는 자체 코드 내에 자기자신을 불러오는 것을 의미한다. 재귀의 예시로 팩토리얼(!)을 들 수 있는데, 재귀함수를 이용한 팩토리얼은 다음과 같다. 위 사진을 보면, n! 안에 (n-1)! 즉 팩토리얼이 포함되어 있는 것을 확인할 수 있다. 만약 n에 4를 대입하면 4 x 3! 이 되고 3!은 3 x 2! 을 불러오는 과정을 반복하여 결국 n = 0이 되어 함수를 불러오는 과정이 종료된다. 이후에는 ..

저번 챕터에서 했던 스택과 큐 구현에 이어, 이번 챕터에서는 다항식을 연결리스트로 구현하는 방법을 작성할 예정이다. 작성은 다음과 같은 순서로 진행할 것이다. 왜 연결리스트( linked list )로 구현할까? 구현방법과 소스코드 그럼 스타-트! 1. 왜 연결리스트로 구현할까? 다항식은 말 그대로 여러개의 단항식이 연결된 구조를 띈다. 이러한 다항식의 특성상 항의 개수 변동이 심하기 때문에 미리 크기를 정해둬야하는 배열은 효율성이 떨어진다. 따라서 배열보다는 linked list로 짜는 것이 더 효율적이다 😎 2. linked list를 이용한 다항식 구현방법 구현방법을 보이기 위해 c = a + b 를 예시로 보여주려고 한다. 이때, a = 6x^6 + 2x^3 + 2 , b = 2x^6 + 7x^4..

프로그래머스 _ 코딩 기초 트레이닝 DAY 11 - (1) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181902 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 알파벳 대소문자로만 이루어진 문자열 my_string이 주어질 때, my_string에서 'A'의 개수, my_string에서 'B'의 개수,..., my_string에서 'Z'의 개수, my_string에서 'a'의 개수, my_string에서 'b'의 개수,..., my_string에서 'z'의 개수를 순서대로 담은..

저번 챕터에서 했던 연결리스트에 이어 이번 챕터에서는 연결 리스트를 이용해 스택과 큐를 구현하는 것을 기록하려고 한다. 배운거 + 배운거 = 쉬운거 일 줄 알았으나.. 아니었던 거😂 이번 챕터에서는 아래 순서로 작성할 예정이다. 연결리스트로 스택 구현하기 연결리스트로 큐 구현하기 그럼 시작-!! 1. 연결리스트로 스택 구현하기 배운지 오래돼서 리마인드를 해주자면, 스택은 후입선출구조 즉 push와 pop이 top에서만 이루어지는 자료구조이다. 위 사진에서 t는 top을 가리키며, push,pop 모두 t에서 일어난다. 1-1. push 구현 push는 새 요소를 넣는 것을 말한다. 위 linked list에 black이라는 요소를 넣는다고 가정하자. 먼저 black이라는 새 노드를 생성한다. 그 후 이 ..

이번 챕터에서는 연결리스트에 관한 내용을 작성하려고 한다. 관련내용은 아래와 같은 순서로 정리할 예정이다. 연결리스트의 원리 단일 연결리스트의 특징 단일 연결리스트 생성코드 단일 연결리스트에서 노드 추가/제거 순환 연결리스트의 특징 순환 연결리스트에서 노드 추가/제거 그럼 시작 -! 0. Linked Lists 연결리스트란 노드들로 구성된 자료구조형태이며 노드는 두 칸으로 쓴다. 앞에는 데이터를 저장하고, 뒤 칸에는 다음 노드의 주소값을 저장해 멀리 있어도 찾아갈 수 있도록 한다. 첫 노드의 주소는 head라는 변수를 설정하여 저장하고, 마지막 노드는 주소값을 NULL값으로 가진다. 배열은 값이 연속으로 할당된다는 특징이 있어, 만약 내가 5칸의 메모리공간이 필요한데 2칸, 4칸의 공간이 각각 있다면 이..

이번 챕터에서는 꽤나 중요한 자료구조형태인 스택과 큐를 아래와 같은 순서대로 작성할 것이다. ✅ 스택의 원리 ✅ 스택의 ADT와 알고리즘코드 ✅ 큐의 원리 ✅ 큐의 ADT와 알고리즘코드 1. Stacks (스택) 스택은 한 쪽 끝에서 데이터를 넣고 뺄 수 있는 구조를 의미한다. 아래 그림과 같이 스택의 아래 부분을 bottom, 윗 부분을 top 이라고 칭하며, 데이터를 넣고 빼는 것은 top에서만 이루어진다. 스택은 후입선출(lifo, last in first out) 방식으로 처리된다는 특징이 있다. 1-1. stack ADT 스택을 ADT로 나타낸다면 아래와 같이 쓸 수 있다. ADT Stack is objects : a finite ordered list with zero or more eleme..

프로그래머스 _ 코딩 기초 트레이닝 DAY 9 - (4) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 어떤 문자열에 대해서 접미사는 특정 인덱스부터 시작하는 문자열을 의미합니다. 예를 들어, "banana"의 모든 접미사는 "banana", "anana", "nana", "ana", "na", "a"입니다. 문자열 my_string이 매개변수로 주어질 때, my_string의 모든 접미사를 사전순으로 정렬한 문자열 배열을..

프로그래머스 _ 코딩 기초 트레이닝 DAY 8 - (5) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181913 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 문자열 my_string과 이차원 정수 배열 queries가 매개변수로 주어집니다. queries의 원소는 [s, e] 형태로, my_string의 인덱스 s부터 인덱스 e까지를 뒤집으라는 의미입니다. my_string에 queries의 명령을 순서대로 처리한 후의 문자열을 return 하는 solution 함수를 작성해..