해시테이블이란? 해시테이블은 키-값 쌍을 저장하고 검색하는 데 특화된 자료구조입니다. 키를 사용하여 값을 빠르게 검색할 수 있도록, 해시 함수를 이용해 키를 인덱스로 변환하여 값을 저장합니다. 이 과정에서 해시 충돌이 일어날 수 있는데 이를 해결하기 위해 개방 주소법이나 폐쇄 주소법을 사용할 수 있습니다. ※ 해시 충돌 : 해시테이블에서 서로 다른 두 개의 키가 같은 해시 함수 값을 가지는 상황을 의미합니다. 해시테이블 작동 원리 해시 함수 : 키를 인덱스로 변환하기 위해 해시 함수를 사용합니다. 해시 함수는 키의 데이터를 정수 형태의 해시 값으로 변환하여 테이블 내 값의 위치를 저장합니다. 해시 충돌 해결 1. 개방 주소법 : 충돌이 발생한 경우, 빈 슬릇 발견할 때 까지 인덱스를 늘려 충돌을 해결하는..
Heap이란? Heap은 이진 트리를 기반으로한 자료구조로 부모 노드와 자식 노드 간의 순서 관계를 유지합니다. Heap은 순서 관계에 따라 최대 힙(Max Heap), 최소 힙(Min Heap) 두 가지로 나눠집니다. 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리입니다. 루트는 항상 최대값이 있습니다. 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리입니다. 루트는 항상 최솟값이 있습니다. Heap의 기본 연산 삽입 : 새로운 원소를 삽입하는 경우 힙의 속성을 유지하기 위해 트리를 재구성하는 과정이 포함되기 때문에 O(logN)의 시간 복잡도를 가집니다. 삭제 : 노드의 값을 삭제하는 경우 힙의 속성을 유지하기 위해 트리를 재구..
Queue란? Queue는 FIFO(First In First Out) 원칙을 따르는 데이터 저장 방식의 자료구조입니다. 데이터가 한쪽 끝에서 삽입되고 반대쪽 끝에서 삭제 및 검색이 됩니다. 이 때 삽입되는 곳을 'rear' 또는 'enqueue' 라고 하며 삭제 및 검색되는 곳을 'front' 또는 'dequeue'라고 합니다. Queue의 기본 연산 1. add(n) : 큐의 rear에 데이터를 추가합니다. 2. poll() : 큐의 front의 데이터를 제거하고 반환합니다. 큐가 비어 있으면 null을 반환합니다. 3. remove() : poll()과 동일하지만 큐가 비어있으면 NoSuchElement 에러를 반환합니다. 4. peek() : 큐의 front의 데이터를 반환합니다. 5. isEmp..
Stack이란? 스택은 데이터를 저장하고 가져오는 작업이 LIFO(Last In First Out) 순서로 이루어지는 자료구조입니다. 이렇게 데이터가 들어오고 나가는 입구가 일정한 위치에서만 이뤄지기 때문에 한쪽 끝에서만 삽입과 삭제가 된다는 점이 스택의 주요 특징입니다. Stack의 기본 연산 1. push(n) : 스택의 제일 위에 데이터를 추가하는 연산입니다. 2. pop() : 스택의 제일 위의 데이터를 제거하고 반환하는 연산입니다. 3. peek() : 스택의 제일 위의 데이터를 반환하는 연산입니다. 4. isEmpty() : 스택이 비어있는지 확인하는 연산입니다. Stack의 장점 간단한 구현 스택은 배열이나 연결 리스트를 사용하여 쉽게 구현할 수 있습니다. 빠른 속도 스택에서 데이터를 삽입하..
Linked List란? Linked List는 데이터 요소들이 선형적으로 연결된 자료구조입니다. 각 요소는 Node라고 부르고 노드는 데이터를 저장하는 공간과 이웃 노드를 가르키는 포인터로 구성됩니다. 각 요소들은 물리적 순서가 아닌 포인터를 통해 연결되어 있습니다. Linked List 종류 1. 단일 연결 리스트 : 각 노드가 다음 노드를 가르키는 포인터를 가지고 있는 가장 기본적인 형태 2. 이중 연결 리스트 : 각 노드가 이전 노드와 다음 노드를 가르키는 포인터 2개를 가지고 있어 양방향으로 탐색할 수 있는 형태 3. 원형 연결 리스트 : 마지막 노드가 처음 노드를 가르키는 포인터를 가지고 있어 연결 리스트가 원형으로 구성되어 있는 형태 Linked List 장점 동적 크기 크기를 동적으로 조정..
ArrayList란? ArrayList란 배열의 크기를 가변할 수 있는 자료구조 입니다. 일반 배열을 사용하여 구현하되, 배열 크기를 동적으로 조절할 수 있도록 추가되었습니다. 따라서 요소가 추가되거나 제거할 수 있기 때문에 유연하게 크기를 재조정할 수 있습니다. 대부분의 프로그래밍 언어에서는 ArrayList와 같은 동적 배열을 제공하며, Java에서는 ArrayList클래스, Python에서는 list 클래스를 사용할 수 있습니다. ArrayList 특징 동적 크기 조절 배열과 달리 ArrayList는 크기를 동적으로 조절할 수 있습니다. 요소가 추가되거나 제거되면 크기가 자동으로 조정됩니다. 빠른 검색 기본 배열과 마찬가지로 인덱스를 활용하여 요소에 빠르게 접근할 수 있으므로 O(1)의 시간 복잡도..
배열(Array) 이란? 배열은 int, boolean 등 동일한 타입의 데이터 요소들이 나열된 자료구조입니다. 배열은 역속된 메모리 공간에 데이터를 저장하며, 각 요소는 인덱스를 통해 쉽고 빠르게 접근할 수 있습니다. 인덱스는 0부터 시작하며, 대부분의 프로그래밍 언어에서 사용되는 방식입니다. 배열의 특징 고정된 크기 배열은 크기가 고정되어 있습니다. 배열을 선언할 때 메모리 크기가 결정되고, 이후 크기를 변경할 수 없습니다. 만약, 배열의 크기를 변경할 경우에는 새로운 배열은 생성하고 기존 배열을 복사하여 넣어야 합니다. 빠른 검색 배열은 인덱스를 통해 각 요소에 빠르게 접근할 수 있습니다. 원하는 데이터를 인덱스를 통해 즉시 찾으며 O(1)의 시간 복잡도를 가집니다. 데이터 삽입 및 삭제 배열의 크..
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42578 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다. 예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코드 코니는 각 종류별로 최대 1가지 의..
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 입출력 예시 풀이 모든 경우의 수를 확인해야 한다고 생각하여 순열을 사용해서 ..
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의..
