본문 바로가기

전체 글

 (104)
[자료구조] 이진 탐색 트리 목표이진 탐색 트리에 대한 이해들어가기 전 본 글에서 직접적으로 설명하지 않지만, 언급하고 있는 내용입니다. 이진 트리완전 이진 트리편향 이진 트리 (= 경사 이진 트리)이진 탐색 트리 (BST, Binary Search Tree)이진 탐색 트리이진 트리 기반으로, 효율적인 자료 검색을 위해 몇 가지 제약 사항을 추가한 트리 이진 탐색 트리는 특정한 키 값에 해당하는 노드를 신속하게 찾는 것이 기본적인 기능이다.이진 탐색 트리의 탐색은 반복적 방법 또는 순환적 방법으로 구현할 수 있다.키 값은 중복될 수 없고, 중위 순회 시 오름차순으로 정렬된 원소의 목록을 획득할 수 있다. 이진 탐색 트리를 왜 사용하는가? 선형 구조에 비해 탐색과 삽입에서 연산 횟수가 줄어 시간 복잡도상 더 효율적이기 때문이다. 검색..
[자료구조] 스레드 이진트리 목표스레드 이진 트리에 대해 알아보자들어가기 전 본 글에서 직접적으로 설명하지 않지만, 언급하고 있는 내용입니다. 중위 순회스레드 이진 트리스레드 이진 트리란?이진 트리의 한 종류로, 중위 순회 시 모든 왼쪽 널 포인터에 중위 선행자 또는 모든 오른쪽 널 포인터에 중위 후속자를 연결한 트리 스레드 이진트리는 중위 순회를 하며, 기존의 스택을 사용하여 재귀적으로 순회하던 방식과 달리 중위 후속자를 가리키는 포인터를 통해 재귀적인 방법 없이 빠르게 순회한다. 스레드 이진 트리를 왜 사용하는가? 이진 트리의 순회를 순환 호출(재귀) 없이 효율적으로 빠르게 하기 위함이다. 일반적으로 이진 트리는 순회 시 스택을 이용 순환 호출(=재귀 호출)을 사용하는데 함수를 반복 호출해야 한다는 점에서 오버헤드가 발생하기 때..
[C++] 라이브러리, 헤더 파일 목표라이브러리를 사용하는 방법과 동적/정적 라이브러리에 대한 이들어가기 전 본 글에서 직접적으로 설명하지 않지만, 기본 지식이 필요한 내용입니다. C++ 프로그램의 빌드 과정라이브러리라이브러리개발 진행 시 자주 사용하는 기능들을 필요 목적에 따라 사용할 수 있도록 모듈화하여 모아 놓은 기능들의 집합 (like 책)기계어로 번역된(컴파일) 바이너리 (0과 1로 구성)1. 라이브러리가 왜 필요한가?컴퓨터에서 자주 사용하는 부분 프로그램들을 모아 놓은 개념.반복적인 동작과 기능, 코드들을 모듈화하여 라이브러리 형태로 사용하면 중복 표현을 줄이고 효율적인 개발 진행 및 유지 보수가 가능하다.코드 재사용유지보수 편리기술 유출 방지 (라이브러리로 제공하여 소스 파일 숨김)개발 기간 단축 및 코드 품질 향상컴파일 시..
[자료구조] 덱, 회문 검사 알고리즘을 통해 파헤치기 목표덱, 원형덱 코드 이해하기들어가기 전 본 글에서 직접적으로 설명하지 않지만, 언급하고 있는 내용입니다. 덱 개념 및 ADT회문 검사 문제 회문(palindrome)이란 앞뒤 어느 쪽에서 읽어도 같은 말, 구, 문 등을 의미한다.덱을 이용하여 주어진 문자열이 회문인지 아닌지를 결정하는 프로그램을 작성하라.  문제 풀이덱을 이용해서 문자열의 앞뒤가 같은지 판별하라는 덱의 앞(front), 뒤(rear) 접근이 가능한 특성을 이용하여 비교하라는 뜻이다.while문으로 덱이 공백 상태일 때까지 맨 앞과 맨 뒤의 값을 가져와 검사 후, 삭제하고 이를 반복한다.이때, 전부 삭제될 때까지 앞과 뒤가 동일하면 회문, 그 전에 두 문자가 동일하지 않다면 회문이 아니다. while (!is_empty(deque)..
[자료구조] 시간복잡도 (feat. 알고리즘 성능 분석) 목표시간복잡도의 계산 방법에 대해 알아보자.들어가기 전 본 글에서 직접적으로 설명하지 않지만, 언급하고 있는 내용입니다. 빅오 표기법 알고리즘 성능 분석알고리즘의 성능 분석 기법알고리즘의 분석은 그 알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 자원은 메모리, 하드웨어도 있지만 주로 주 측정 대상은 계산 시간이다. 수행 시간은 수행 시간 측정, 알고리즘의 복잡도 분석 2가지 방법으로 분석한다. 수행 시간 측정은 실제 두 코드 작성 후 수행 시간을 측정하는 것인데 주로 clock 함수를 사용하여 측정한다. 그러나 일일이 코드를 작성하기 어려우므로 직접 구현하지 않고 수행 시간을 분석하는 알고리즘의 복잡도 분석을 주로 다룬다. 시간 복잡도와 공간 복잡도 중 시간 복잡도를 우선순위로 둔다. 공..
[C++] 파라미터와 스택 프레임 (feat. 메모리 구조) 목표함수 호출 시 함수의 매개변수가 스택에 담기는 원리를 파악해보자.파라미터로 배열을 넘겼을 경우를 자세히 파헤쳐보자. 들어가기 전 본 글에서 직접적으로 설명하지 않지만, 언급하고 있는 내용입니다. - 자료구조 스택- 2차원 배열 중요한 부분 요약스택프레임은 함수 호출 시 스택 영역에서 생성되는 함수의 호출 공간이다. 목차 스택 프레임메모리란?주기억 장치(RAM), 컴퓨터의 계산을 위해 어딘가에 데이터를 보관할 공간이다. 메모리의 4가지 영역 Code 영역: rodata, TEXT (읽기 전용)      /          Data영역: BSS, DATA, CONST문자열 리터럴은 읽기 전용 메모리 영역에 할당된다.rodata: read only part of data segment 문자열 리터럴은 읽기..
[C++] const 키워드 목표const 키워드를 완전히 이해해보자.   들어가기 전 본 글에서 직접적으로 설명하지 않지만, 언급하고 있는 지식입니다. - static- mutable 중요한 부분 요약- const 메서드는 해당 객체 안의 모든 데이터 변경을 금지한다는 의미이다.- const 객체는 const 메서드만 호출 가능하다.- static 메서드에는 const를 사용할 수 없다. - const 포인터 시 cosnt의 선언 위치에 따라 포인터 자체 또는 포인터가 가리키는 값의 변경 불가능 여부가 결정된다.- const는 선언과 동시에 초기화해야 한다. (참조 변수 가능)- static const 멤버 변수의 경우 초기화는 구현부에서 따로 해줘야 한다. (C++11 이전 버전)  목차 const 키워드const란?const는..
[TIL43장] 함수 객체 사용 이유 (feat. 오버헤드, inline 함수) TIL 24.01.22 리스트 개념 배열 리스트 연결 리스트 함수 객체 사용 이유 ▩ 연산자 함수 ** 범용성(누구나 사용 용이), 효율성(최적화) ** 효율성: 1. 함수에서 매개변수 전달하려면 "스택" 사용 -> "오버헤드" 발생 => inline함수 사용 시 해결 (inline은 함수 호출이 아닌 코드로 치환해줌) 범용성: 1. 함수포인터 사용 - 선언 형식: 반환값(*변수명)(매개변수); ex. // Add, Minus는 inline 함수 int(*func)(int, int); A일 경우, func = Add 함수; B일 경우, func = Minus 함수; func(1, 3); // 경우에 맞게 Add나 Minus 함수가 실행됨 => 함수 포인터 사용 시 "런타임에 결정"도기 떄문에 "컴파일 타..

티스토리툴바