티스토리

꿈꾸며 개발하기

검색하기

블로그 홈

꿈꾸며 개발하기

wooooozin.tistory.com/m

기록

구독자: 5

방명록 방문하기

주요 글 목록

재귀 알고리즘 기초 이해하기 재귀란? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 합니다. 재귀적 정의를 사용하여 무한으로 존재하는 자연수를 정의한다면 - 1은 자연수입니다. - 자연수 n의 바로 다음 정수도 자연수입니다. 재귀를 효과적으로 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 작성할 수 있습니다. 팩토리얼 구하기. 재귀를 사용한 예로 가장 먼저 음이 아닌 정수의 팩토리얼(factorial) 값을 구하는 프로그램을 살펴봅시다. 음이 아닌 정수 n의 팩토리얼은(n!) 다음과 같이 재귀적으로 정의할 수 있습니다. - 0! = 1 - n > 0 이면 n! = n * (n-1)! 즉, 5! 은 5 * 4! 이고 4! 은 4 * 3! 입니다. impo.. 공감수 1 댓글수 0 2023. 6. 16.
스택과 큐 - 스택이란? 스택(Stack)이란? 스택은 데이터를 일시적으로 쌓아놓는 자료구조로 데이터의 입력과 출력 순서는 후입선출(LIFO) 입니다. 가장 나중에 넣은 데이터를 가장 먼저 꺼냅니다. 스택에 데이터를 넣는 작업을 push라고 하며 꺼내는 작업을 pop이라고 합니다. 가장 상단의 값을 top이라고 하고 가장 아랫부분은 bottom이라고 합니다. 자바 프로그램이 실행 될 때도 이와 같은 방식으로 스택 구조에 의해 함수가 실행됩니다. 스택 만들기. 고정 길이 스택을 만들어 필드, 생성자, 메서드 순으로 살펴봅시다. package june2023.day11.stack; import java.util.Scanner; class IntStack { private int[] stack; private int capacity;.. 공감수 0 댓글수 0 2023. 6. 11.
검색 알고리즘과 선형 검색, 이진 검색 데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘을 알아보자. 검색 알고리즘이란? 검색 알고리즘은 주어진 데이터 집합에서 특정 값을 찾는 과정을 수행하는 알고리즘입니다. 일반적으로 데이터가 정렬되어 있는 경우와 그렇지 않은 경우에 따라 다른 알고리즘이 사용됩니다. 검색 알고리즘은 다양한 방법으로 구현될 수 있으며, 효율성과 정확성을 고려하여 선택됩니다. 일반적으로 사용되는 검색 알고리즘으로는 선형 검색(Linear Search), 이진 검색(Binary Search), 해시 검색(Hash Search) 등이 있습니다. 선형 검색(Linear Search): 데이터를 처음부터 끝까지 순차적으로 탐색하여 원하는 값을 찾는 알고리즘입니다. 데이터가 정렬되어 있지 않은 경우에도 사용할 수 있지만,.. 공감수 0 댓글수 1 2023. 6. 9.
기본 자료구조 - 배열이란 자료구조 정의하기. 배열을 공부하기 위해서 자료구조가 무엇인지 간단히 알아야 합니다. 자료구조란 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적인 관계 쉽게 말해 자료를 효율적으로 사용할 수 있도록 컴퓨터에게 저장하는 방법을 말합니다. 자료구조는 데이터를 효율적으로 조직화하고 저장하고 처리하는 방법을 다루는 컴퓨터 과학의 학문 분야이며 데이터의 특성과 연산의 효율성을 고려하여 데이터를 구성하고 저장하는 방법을 설계하며, 데이터의 접근, 삽입, 삭제, 검색 등의 연산을 수행하기 위한 알고리즘을 개발합니다. 자료구조는 다양한 형태로 구현될 수 있으며, 각각의 자료구조는 특정한 상황에서 효율적인 동작을 보장합니다. 예를 들어, 배열은 데이터에 연속적인 메모리 공간을 할당하여 인덱스를 통해 데이터에 접근하.. 공감수 0 댓글수 0 2023. 6. 6.
기초수학 - 조합(Combination) 조합(Combination). 조합(Combination)은 주어진 원소들 중에서 일부를 선택하여 만들어지는 모든 경우의 수를 구하는 것을 말합니다. 조합은 순서가 중요하지 않으며, 중복된 원소를 포함하지 않습니다. 일반적으로 조합은 "n 개 중에서 r 개를 선택하는 경우의 수"를 나타내는 nCr로 표기됩니다. 조합을 구하는 방법에는 여러 가지 방법이 있지만, 가장 일반적인 방법은 재귀적으로 구현하는 것입니다. 재귀적인 방법을 사용하면 간결하고 직관적으로 조합을 구할 수 있습니다. - 서로 다른 n개 중에서 r개를 선택하는 경우의 수 (순서 X, 중복 X) case1. 서로 다른 4명 중 주번을 2명 뽑는 방법 public class CombinationTest1 { public static void m.. 공감수 0 댓글수 3 2023. 6. 4.
기초수학 - 순열(Permutation) 시작하며. 순열은 코딩 테스트에서 여러가지 유형으로 응용되어 나온다. 개념을 확실히 알고 넘어가기 위해 정리하고자 한다. 순열을 이해하기 전에 팩토리얼을 먼저 알아보자. 팩토리얼(Factorial). 팩토리얼은 양의 정수 n에 대해 1부터 n까지의 모든 정수를 곱한 값 n 팩토리얼은 n!으로 표기한다. // 1에서 n까지의 모든 자연수의 곱 (n!) 1! = 1 2! = 2 X 1 3! = 3 X 2 X 1 n! = n(n-1)(n-2) ... X 1 public class Permutation0603 { public static void main(String[] args) { // 팩토리얼 int n = 5; int result = 1; // 반복문으로 구현하기 for (int i = 1; i = n .. 공감수 0 댓글수 0 2023. 6. 3.
기초수학 - 경우의 수 : 합의법칙, 곱의법칙, 약수, 최대공약수, 최소공배수) 경우의 수. 어떤 사건에서 일어날 수 있는 경우의 가짓수로 동전을 던졌을 때 나올 수 있는 가짓수는 2, 주사뤼를 던졌을 때 나올 수 있는 가짓누는 6이다. 사건 A가 일어날 경우의수는 n(A)로 표기하고 크게 순열, 조합, 중복순열 등이 있다. 경우의 수는 주어진 문제나 상황에 따라 다양한 방법으로 계산될 수 있고 게임 이론, 알고리즘 설계, 조합 최적화, 확률과 통계 등 다양한 분야에서 사용된다. 합의 법칙. 합의 법칙은 두 개 이상의 상호 배반적인 사건(이벤트)의 경우의 수를 더하여 전체 경우의 수를 계산하는 원리다. 즉, 두 사건이 동시에 발생하지 않을 때, 두 사건 중 하나가 발생하는 경우의 수는각각의 경우의 수를 더하여 구할 수 있으며 사건 A 또는 사건 B가 일어날 경우의 수는 합집합으로 표.. 공감수 1 댓글수 0 2023. 6. 1.
기초수학 - 집합(Set) 집합(Set). 기초 수학에서 집합은 (특정조건에 맞는)원소들의 모임을 의미합니다. 집합은 중복되지 않는 원소들로 구성되며, 순서는 중요하지 않습니다. 집합은 중괄호{}로 표현되며, 각 원소는 쉼표로 구분됩니다. 집합을 표현하는 방법으로는 원소나열법, 조건제시법, 벤 다이어그램이 있습니다. 집합에 대해 알아보며 이를 자바 코드로 구현해봅시다. 집합 표현 방법. 원소나열법 A = {1, 2, 3, 4, 5}, B = {2, 4, 6, 8, 10} 조건제시법 A = {A | A는 정수, 1 ≦ A ≦ 5 } B = {2B | B는 정수, 1 ≦ B ≦ 5} 벤 다이어그램 교집합. 두 집합이 공통으로 포함하는 원소로 이루어진 집합 A ∩ B = { 𝑥 | 𝑥 ∈ A and 𝑥 ∈ B } 합집합. 어느 하나에라.. 공감수 0 댓글수 0 2023. 5. 31.
비선형 자료구조 - 이진 탐색 트리 (Binary Search Tree) 정의 및 탐색, 삽입, 삭제 구현 시작하며. 앞서 트리가 무엇인지 이진 트리는 무엇인지 이진 트리의 성격에 따라 포화 이진 트리, 완전 이진 트리, 정 이진 트리, 편향 이진 트리 등등 어떤 종류가 있는지 그리고 어떻게 순회할 수 있는지 등을 알아봤습니다. 오늘은 이진 트리의 종류 중 하나인 이진 탐색 트리에 알아보며 데이터를 삽입하고 삭제하는 방법도 정리하고자 합니다. 이진 탐색 트리(Binary Search Tree, BST)를 알아야 하는 이유 탐색 효율성: 이진 탐색 트리는 데이터를 효율적으로 탐색할 수 있는 구조입니다. 각 노드는 특정한 값을 가지고 있으며, 왼쪽 서브트리에는 작은 값의 노드가, 오른쪽 서브트리에는 큰 값의 노드가 위치합니다. 이를 통해 탐색 시 비교를 통해 탐색 범위를 반씩 줄여나가므로, 탐색 속도가 빠릅니다... 공감수 0 댓글수 0 2023. 5. 29.
비선형 자료구조 - 이진 트리(Binary Tree) 구현과 순회 이진 트리 구현. 배열 : 레벨 순회 순으로 배열에 구성 연결 리스트 : 값과 간선을 관리하기 위한 연결리스트 구성 이진 트리의 순회(Traversal). 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산 전위/중위/후위 순회, 레벨순회로 분류할 수 있다. 전위 순회(preorder traversal) 순서 : 부모 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 노드를 방문 경로 : A → B → D → H → I → E → J → C → F → G 1. 현재 노드 A 출력 → A의 왼쪽 노드 B 출력 → B의 왼쪽 노드 D 출력 → D의 왼쪽 노드 H 출력 (하위 노드 없음) 2. D의 오른쪽 노드 I 출력 → B의 오른쪽 노드 E 출력 -> E의 왼쪽 노트 J 출력 (하위 노드 없음) 3. A의.. 공감수 0 댓글수 0 2023. 5. 27.
비선형 자료구조 - 이진 트리(Binary Tree)란 무엇이고 여러 가지 종류를 알아보자 시작하며. 지난 글에서 트리 자료구조는 어떤 것인지 왜 이진 트리가 중요한지 등 정리했었다. 이진 트리는 성격에 따라 여러 가지 종류로 분류되며 오늘은 이진 트리란 무엇이고 종류와 특징에 대해서 알아보고자 한다. 이진 트리(Binary Tree). 각 노드는 최대 2개의 자식을 가질 수 있는 트리 자식 노드는 좌우를 구분하여 값을 저장 (왼쪽 자식 : 부모 노드의 왼쪽 / 오른쪽 자식 : 부모 노드의 오른쪽 아래) 이진 트리의 서브 트리는 공백이 될 수도 있고 하나의 서브트리만 가지거나 두 개 모두 가질 수도 있다. 이진 트리의 종류. Perfect binary Tree : 포화 이진 트리 - 모든 레벨의 노드들이 2개씩 다 채워져 있는 트리 - 모든 리프 노드가 같은 레벨에 있어야 함 Complete .. 공감수 0 댓글수 0 2023. 5. 27.
비선형 자료구조 - 트리(Tree)란 무엇이고 왜 이진 트리를 알아야 하는가? 시작하며. 자료구조를 공부하면서 선형 자료구조는 어떻게 어떻게 이해하겠는데 비선형 자료구조는 정말 멘탈 바사삭이다. 그래서 트리부터 천천히 정리하며 기록하려 한다. 트리(Tree)란 무엇인가? 노드와 링크로 구성된 자료구조, 그래프의 일종, Cycle 없음 계층적 구조를 나타낼 때 사용(폴더 구조, 조직도, 가계도 등) 데이터가 순차적으로 저장되지 않기 때문에 비선형 자료구조 트리의 요소가 여러 수준으로 배열되는 계층 구조 트리는 나무. 나무에는 잎, 가지, 뿌리 및 줄기가 있다 잎을 따라가면 줄기가 있고 이 줄기는 결국 뿌리로 향한다. 트리 구조는 이런 나무의 모습을 그대로 구조화한 모델이다. 뿌리에 해당하는 제일 상위의 노드는 루트 노드라고 하며 줄기에 해당 하는 에지(링크, 브랜치)는 노드 간의 연.. 공감수 0 댓글수 0 2023. 5. 23.
선형자료구조 - 해시, 해시테이블, 해시맵, 해시표 해시 테이블(Hash Table) = 해시맵, 해시표 해시함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 색인(index)삼아 데이터의 값(Value)를 키(key)와 함께 저장하는 자료구조를 해시 테이블 이라고 함 이 때 데이터가 저장되는 곳을 버킷(bucket) 또는 슬롯(slot) 이라고 함 해시테이블(= 해시맵, 해시표)은 키를 통해 해당 데이터에 빠르게 접근이 가능함. 해시 충돌 해시 테이블에 같은 공간에 서로 다른 값을 저장하려는 경우 -> 서로 다른 키의 해시 함수를 통한 해시 값이 동일한 경우 해시 충돌이 일어나 원하는 결과를 얻을 수 없음 해시 충돌을 해결하는 방법에는 선형탐사법, 제곱탐사법, 이중해싱, 분리연결법 등 방법으로 해결할 수 있음 이와 관련된 내용은 추후에 정리할 .. 공감수 0 댓글수 0 2023. 5. 20.
선형자료구조 - 데크/덱(Deque) Deque. Double-ended queue 양쪽에서 삽입과 삭제가 모두 가능한 자료구조 Java에서 Deque는 Java.util 패키지에 있는 Queue 인터페스의 하위 유형으로 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있음 양 쪽 끝에 요소를 삽입하고 삭제할 수 있는 데이터구조를 지원 FIFO, LIFO 모두 사용 가능함(스택과 큐를 합친 것) Deque는 Palindrome Checker , Song Playlist 등에서 사용 Deque 주요 메서드. HTML 삽입 미리보기할 수 없는 소스 Deque 관련 코딩테스트 문제. 프로그래머스 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 .. 공감수 0 댓글수 1 2023. 5. 19.
선형자료구조 - 큐(Queue) Queue. 큐는 대기열이라고도 하며 선입선출(First In First Out) 자료구조 입니다. 먼저 들어온 데이터가 먼저 나가는 구조로 쉽게 말해 선착순을 떠올리면 됩니다. 먼저 온 사람은 먼저 집에가세요.!!!!!!! 입력 순서대로 데이터 처리가 필요할 때 사용하며 프린터 출력 대기열 등과 비교 됩니다. 자바에서는 Queue는 인터페이스로 정의되어 있고 Priority Queue 등 구현되어 있으나 ArryList나 LinkedList 클래스를 활용하여 구현하는 경우가 있음 큐 데이터 추가 큐 데이처 삭제 Queue 주요 메서드. HTML 삽입 미리보기할 수 없는 소스 ArrayList로 Queue 구현하기. HTML 삽입 미리보기할 수 없는 소스 공감수 0 댓글수 0 2023. 5. 18.
자료구조란 무엇이고 선형/비선형 자료구조란? 시작하며. 선형 / 비선형 자료구조 공부하면서 이해 안되는 부분도 많고 머리속에서 두둥실 떠다니는 개념들을 자리잡기 위해 자료구조란 무엇이고 어떻게 분류되는지 어떤 것들이 있는지 간단하게라도 정리하고 넘어가려 한다. 비선형 자료구조는 아직 모르는게 많아서 제대로 정리가 안된거 같다. 자료구조란. 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨. 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 해 자료구조에 대한 이해가 중요 자료구조 형태에 따른 분류. 선형 자료구조 데이터 요소가 순차적 또는 선형으로 배열되고 일대일 관계에 있으며 각 요소.. 공감수 0 댓글수 0 2023. 5. 17.
선형자료구조 - 스택(Stack) Stack. 자료 구조 중 하나인 Stack은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료 구조 후입선출 자료 구조 Last In First Out : LIFO 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용 ex) 함수 콜 스택, 수식 계산, 인터럽트 처리, 웹브라우저 앞으로 / 뒤로 자바에서 스택을 사용하기 위해서 java.util 패키지에서 제공하는 Stack을 사용하면 된다. 기본 Stack 클래스 외에도 ArrayList로도 구현해보자. Stack 한장으로 정리해보기. Stack 주요 메서드. import java.util.Stack; public class Main { public static void main(String[] args) { // Stack 선언 Stack st.. 공감수 0 댓글수 8 2023. 5. 16.
선형자료구조 - 연결리스트(LinkedList) LinkedList. 선형으로 자료를 관리, 자료가 추가 될 때마다 메모리를 할당받고, 자료는 링크로 연결되어 물리적 위치와 논리적 위치가 다를 수 있음. 연결리스트의 각 요소는 다음 주소값을 가리키는 주소값을 가짐 물리적인 메모리가 떨어져 있어도 논리적으로는 앞뒤 순서가 있음. 같은 List 인터페이스를 구현한 ArrayList에 비해 중간에 자료를 삽입하고 제거하는데 시간이 적게 걸림 크기를 동적으로 증가할 수 있음 연결리스트의 각 요소는 요소의 자료와 다음 주소를 저장하는 부분으로 구현 또한 스택이나 큐에서 다양하게 활용할 수 있음 배열과 연결리스트의 차이점. 자료의 변동(수정, 삭제) 등이 많다면 연결리스트 사용 거의 없다면 배열을 사용하는게 좋다. 연결리트스 데이터 추가. 연결 리스트 가장 앞에.. 공감수 0 댓글수 1 2023. 5. 15.
선형자료구조 - Array / ArrayList 배열(Array). 많은 수의 데이터를 다룰 때 자료를 순차적으로 관리하는 자료구조 각 데이터를 인덱스와 1:1 대응하도록 구성 데이터가 메모리 상에 연속적으로 저장되어 물리적 위치와 논리적 위치가 동일 배열의 선언과 초기화. 배열의 선언 자료형[] 배열 이름 = new 자료형[데이터 개수]; 자료형 배열 이름[] = new 자료형[데이터 개수]; int[] numbers = new int[10]; 인덱스 연산 []는 배열 처음 선언 시 사용한 연산자로 배열 이름에 []를 사용하는 것을 인덱스 연산이라고 함 배열 요소의 저장된 메모리 위치를 찾아 주는 역할로 numbers[0] 은 numbers 배열의 0번째 인덱스 요소 값에 접근하는 것 배열의 초기화 배열을 선언하면 그와 동시에 각 요소의 값이 초기화.. 공감수 0 댓글수 0 2023. 5. 15.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.