코딩테스트/자료구조

B2805 나무자르기- 이진검색 이진 검색 이란? 뭘까요 선형 탐색을하게 되면 너무 많은 시간 복잡도를 사용하게 됩니다. 따라서 데이터를 둘로 나눠 찾고자하는값을을 탐색해가며 범위를 좁혀나가는것입니다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 설명 "B2805 나무 자르기"는 주어진 나무들을 일정 높이로 잘라서 필요한 총 나무 길이를 얻는 최대 절단 높이를 찾는 문제입니다.이 문제는 이진 탐색..

그리디 알고리즘의 정의 그리디 알고리즘은 각 단계에서 최선의 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다. 📌 가장 대표적인 예시로 동전이 500원 , 100원 , 50원 ,10원이 충분히 있을때 동전을 최소한으로 사용해서 거스름돈을 주어야한다묜? 예) 650원 기준 → 500원: 1개 , 100원 :1개 , 50원 : 1개 예) 730원 기준 → 500 + 100_2 + 10_3 그리디 알고리즘은 각 단계에서 최선의 선택을하는 방식으로 문제를해결해야하는데 바꿔서 말하면 각단계에서 최선의 선택을 모두 합쳤을때 전체의 최선의 선택과 다르다면 풀이는 성립하지않습니다. 📌 만약 동전이 500원 400원100원이있다고하면 예) 800원 기준은 500_1 + 100_3 과 400*2 는 같은 800원이지만..

해시 테이블 해시 테이블과 힙에 대해서 정리해보는 시간을 가지겠습니다 해시테이블의 구조 키(Key)에 데이터(Value)를 매핑할 수 있는 데이터 구조 - 해쉬 함수를 통해, 배열에 키에 대한 데이터를 저장할 수 있는 주소(인덱스 번호)를 계산 - Key를 통해 바로 데이터가 저장되어 있는 주소를 알 수 있으므로, 저장 및 탐색 속도가 획기적으로 빨라짐 - 미리 해쉬 함수가 생성할 수 있는 주소(인덱스 번호)에 대한 공간을 배열로 할당한 후, 키에 따른 데이터 저장 및 탐색 지원 Direct-address table 키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table이라고 합니 다. Direct-address table의 장점은 키 개수와 해시테이블 크기가 동일..

스택 Slack 그리고 큐 Queue 스택 데이터를 한쪽끝에서만 넣었다 뻈다 하는 구조. 스택은 LIFO (Last In, Fast Out) FILO( First In Last Out) 데이터 관리 방식을 따름 대표적인 스택으 활용으로는 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 스택의 장단점 장점 : 구조가 단순해서 , 구현이 쉽다. 또한 데이터 저장시 읽기 쓰기 속도가빠르다 단점: 데이터의 최대 저장 갯수를 미리 정해야함, 또한 저장공간의 낭비가 일어날수있음. 스택은 단순하고 빠른 성능을 얻기위해 사용되므로 , (파이썬제외)배열 구조를 활용해서 구현하는것이 보편적이다. 큐 구조 큐는 줄서는 행위와 유사함 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 음식점에서 가장 먼저 줄을 선 사람이 ..