[알고리즘] 이분 탐색 Binary Search

이분 탐색데이터들이 "정렬되있는 상태"에서 시작점과 끝점을 반씩 줄여나가며 원하는 데이터를 찾는 탐색 알고리즘이다.시간복잡도는 O(logN)을 갖는다why? 반씩 덜어내며 탐색하기 때문이다.공간 복잡도는 O(N)why? 별도의 메모리 공간을 더 확보하지 않기 때문이다. 코드#include using namespace std;//비교 횟수 기록용int gCount = 0;//이분 탐색 검색void BinarySearch(int tArray[], int Begin, int End, int data) { if (Begin > End) { cout 결과

• format_list_bulleted C++/알고리즘
• · 2025. 7. 5.
• textsms

[STL] 스택 Stack

스택FILO 형태로 동작하며 가변형태를 가지는 자료구조이다.원시배열은 크기가 고정되어 있기 때문에, 가변배열이며 스택의 출입구는 한 곳이므로 단방향 연결리스트로 구현하는 것이 좋다.스택은 메모리 저장에서 활용된다. 이런 형태를 구현하기 위해선 포인터의 이해가 필수이다.(나도 가끔 헷갈린다) 코드/*스택StackFILO Frist In Last Out 형태로 동작하며, 가변형태를 가지는 자료구조이다.원시배열은 크기가 고정되어 있기때문에,가변 배열인 Single Linked List로 구현하는것이 적합하다.Why?스택은 출입구가 하나이므로 Single연결리스트로 push, pop시에 O(1)로 가능하기 때문이다.*/#include using namespace std;struct SNode { //데이터..

• format_list_bulleted C++/자료구조
• · 2025. 7. 5.
• textsms

[자료구조] 이진탐색트리 Binary Search Tree

이진 탐색 트리탐색을 위한 트리형태의 구조를 가진 자료구조로 다음과 같은 조건을 만족해야 한다.1. 같은 값을 갖는 노드가 없어야한다.2. 왼쪽 서브트리에 있는 값은 현재 노드의 값보다 작고, 오른쪽 서브트리에 있는 값은 현재 노드보다 커야한다.3. 서브트리도 이진트리여야 한다.탐색과 추가는 쉽게 구현할 수 있지만 삭제의 경우 좀 번거로움이 있다.탐색탐색하려는 키 값이 루트 노드의 키 값과 같은지 비교한다.탐색하려는 키 값이 루트노드의 키 값 보다 작으면 왼쪽 서브트리로 이동한다. 반대로 키 값이 크면 오른쪽 서브트리로 이동한다.이동한 서브트리에서 1을 재수행한다.추가탐색하려는 키 값이 트리내에 존재하는지 탐색한다.존재한다면 추가작업을 그만한다.존재하지 않는다면 탐색 실패가 발생한 위치에 노드를 생성하여..

• format_list_bulleted C++/자료구조
• · 2025. 7. 5.
• textsms

[자료구조] C++로 양방향 Linked List 구현

C++로 양방향 연결리스트(Linked List) 구현/*양방향 연결리스트 구현(Linked List)연결리스트는 (헤드포인터 , 값, 꼬리포인터)로 구성되어 있다.*/#include using namespace std;//리스트의 노드struct LinkedNode { int Data=0; //항상 nullptr로 초기화 LinkedNode* prev = nullptr; //헤드 노드 LinkedNode* next = nullptr; //꼬리 노드};// 리스트 전체 구조struct LinkedList { LinkedNode* head = nullptr; LinkedNode* tail = nullptr;};//삽입void InsertNode(LinkedList* list..

• format_list_bulleted C++/STL
• · 2025. 6. 27.
• textsms

[STL] Map 컨테이너

map 컨테이너연관 컨테이너로 원소를 key와 value의 쌍으로 저장한다.set은 원소를 key하나로 저장하지만 map은 원소를 key와 value 쌍으로 저장하며, map도 key의 중복 저장을 하지 못하지만 중복저장을 원한다면 multiset을 사용해야한다.map은 [ ] 연산자를 제공하여 key에 해당하는 원소의 value에 쉽게 접근하거나 변경할 수 있다. 균형 이진 트리: 모든 노드가 부모보다 왼쪽이 작고 오른쪽이 큰 형태. (반대라면 반대로) 연관 컨테이너는 균형 이진 트리를 사용하므로 찾기연산( find(), lower_bound(), upper_bound(), equal_range(), count())에 뛰어난 성능(로그 시간)을 보이며 insert 또한 로그 시간 복잡도를 보인다. 중복..

• format_list_bulleted C++/STL
• · 2025. 3. 22.
• textsms

[STL] Set 컨테이너

set 컨테이너연관 컨테이너 중 단순한 컨테이너로 Key라 불리는 원소(value)의 집합으로 이뤄진 컨테이너. 중복 혀용X노드 기반의 컨테이너로 균형 이진 트리로 구현되어 있다.set은 원소를 삽입할때 유일한 멤버 함수 insert( )를 제공한다. 균형 이진 트리: 모든 노드가 부모보다 왼쪽이 작고 오른쪽이 큰 형태. (반대라면 반대로) 연관 컨테이너는 균형 이진 트리를 사용하므로 찾기연산( find(), lower_bound(), upper_bound(), equal_range(), count())에 뛰어난 성능(로그 시간)을 보이며 insert 또한 로그 시간 복잡도를 보인다. 중복을 허용하는 multiset 컨테이너템플릿 형식, 인터페이스, 멤버의 형식 모두 set과 같고, key가 중복으로 저..

• format_list_bulleted C++/STL
• · 2025. 3. 22.
• textsms

[STL] 6장 문제풀이

1. 다음 중 vector 컨테이너의 특징을 고르세요.1. 시퀀스 컨테이너입니다.2. sort( ), splice( ) 멤버함수를 제공합니다. (vector 자체에서 sort splice는 제공하지 않음)3. 배열 기반 컨테이너 입니다.4. 컨테이너 앞, 뒤로 추가/제거가 가능합니다. (vector는 뒤로 추가 제거만 가능)5. 임의 접근 반복자를 제공합니다.6. reserve( ) 멤버 함수를 제공합니다.7. 빠른 시간(상수 시간)에 원소를 삽입, 삭제 할 수 있습니다. (삽입 삭제 시 필요한 만큼의 메모리 공간을 위해 빠른 시간 내에 할 수는 없음) 답: 1, 3, 5, 6 2. 다음 중 deque 컨테이너의 특징을 고르세요.1. 시퀀스 컨테이너 입니다.2. sort( ), splice( ) 멤버 함..

• format_list_bulleted C++/STL
• · 2025. 3. 17.
• textsms

[STL] list 컨테이너

list컨테이너노드 기반의 컨테이너로, 원소가 노드 단위로 저장되며 이중 연결 리스트로 구현됨. list 의 주요 인터페이스템플릿 형식 template >class listT는 list컨테이너 원소의 형식 생성자생성자list ltlt는 빈 컨테이너list lt(n)0원소 n개로 초기화된 컨테이너list lt(n, x)x원소 n개로 초기화된 컨테이너list lt(lt2)lt는 lt2 컨테이너의 복사본 (복사 생성자 호출)list lt(b,2)lt는 반복자 구간 [b, e)로 초기화된 원소를 같는다. 멤버함수멤버함수lt.assign(n,x)lt에 x값으로 n개의 원소를 할당한다lt.assign(b,e)lt에 반복자 b부터 e까지 시퀀스 구간으로 할당한다.lt.back()lt에 마지막 원소를 참조한다.p=l..

• format_list_bulleted C++/STL
• · 2025. 3. 16.
• textsms

[STL] Deque 컨테이너

Deque 컨테이너vector 컨테이너와 비슷하게 동작하지만 앞으로도 삽입과 삭제가 가능한 컨테이너 vector와 다른 push_backvector에서의 push_back은 기존 메모리에 필요한 메모리를 추가한 메모리공간에 원소들을 삽입했지만deque의 push는 원소가 여러 메모리 블록에 나뉘어 저장된다. Deque의 주요 인터페이스템플릿 형식 template >class dequeT는 deque 컨테이너 원소의 형식 생성자생성자deque dqdq는 빈 컨테이너deque dq(n)0원소 n개로 초기화된 컨테이너deque dq(n, x)x원소 n개로 초기화된 컨테이너deque dq(dq2)dq는 dq2 컨테이너의 복사본 (복사 생성자 호출)deque dq(b,2)dq는 반복자 구간 [b, e)로 초기화..

• format_list_bulleted C++/STL
• · 2025. 3. 15.
• textsms