기억을 위한 기록들

초안: 2021년 1월 27일 1차 수정 : 2023년 4월 23일 이름의 뜻? - 이름은 각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 붙여진 것. (탐욕에 눈이 멀어서 이렇게 [ 됐다고 붙여졌다고...) - 탐욕 알고리즘은 특별한 코드가 있는 알고리즘이 아닌 '개념적인' 알고리즘. - 어떠한 문제에도 적용할 수 있지만, 문제마다 적용하는 방식이 모두 다르다. 동적계획법(DP) 보다 효율적이긴 하지만, 동적계획법처럼 반드시 최적의 해를 구해준다는 보장 하지는 못한다. 최적의 해가 나오길 바랄 뿐이다. -> 빠른 의사결정이 가능. 괜찮은 해법인 경우가 많음. 탐욕알고리즘의 동작과정 1. 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합(Solution Set)에 ..

동적 계획법이란? - 큰 의미에서 분할 정복과 같은 접근 방식을 의미. - 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문. - 두번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계기법을 동적 계획법이라고 한다. 하지만! 모든 문제를 이렇게 풀 수 없고 특별한 속성이 필요하다. 사용방법 : 1. 문제를 부분 문제로 나눈다. 2. 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장. 3. 테이블에 저장되어 있는 부분 문제의 해를 이용하여, 점차적으로 상위 부분 문제의 최적해를 구한다. 사용 조건 : 1, 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있습접니다. 2. 중복되는..

- 해시 테이블에서 데이터를 저장할 위치를 사용하기 위해 사용 - 길이가 긴 데이터 둘을 빨리 비교하기 위해 (단, 해시값이 다른 경우만 빨리 비교 가능) - 누출되면 곤란한 데이터의 원본을 저장하지 않기 위해 - 용도에 따라 해시 알고리즘의 요구수항이 조금씩 달라질 수 있다. - 어떤 입력값을 받으면 어떤 해시함수의 규칙에 의해 특정 비트라던가 어떤 정수로 된 값으로 변하게 하는데, 이렇게 변한 값을 해쉬값, 해쉬코드라고 부른다. - 함수임으로 입력값이 같으면 출력값도 일치 해야한다.

초안 : 2021년 1월 3일 1차 수정 : 2023년 4월 10일 해시테이블이란? 해시 테이블(Hash Table)은 키(Key)와 값(Value)으로 이루어진 데이터를 저장하기 위한 자료구조 중 하나입니다. 해시 테이블은 일반적으로 배열(Array)과 연결 리스트(Linked List)를 조합하여 구현됩니다. 해시 테이블의 핵심 아이디어는 키를 해시 함수(Hash Function)에 넣어서 고유한 해시 코드(Hash Code)를 생성하고, 이 해시 코드를 배열의 인덱스로 사용하여 값을 저장하는 것입니다. 이렇게 하면 키와 값 쌍을 빠르게 찾을 수 있습니다. 해시 테이블의 장점은 검색, 삽입, 삭제 등의 연산이 O(1)의 시간 복잡도로 수행된다는 것입니다. 하지만 해시 함수의 충돌이 발생할 경우 해결하..

초안 : 2021년 9월 22일 1차 수정 : 2023년 4월 10일 기존 Sort(정렬) 알고리즘들이 여러 가지가 있다. 그중에서도 크게 2가지로 나눌 수가 있는데, 바로 Stable Sort와 UnStable Sort로 나눈다. 우선 Stable와 UnStable의 사전적 의미로는 아래와 같다. 정렬 알고리즘의 stability란, 동일한 키(key) 값을 가진 원소(element)들이 정렬 후에도 서로의 상대적인 위치가 유지되는 성질을 말합니다. 따라서 stable 한 정렬 알고리즘은 같은 값을 가진 원소들의 순서가 보존되어야 하는 경우에 유용합니다. 안정적인(stable) 정렬과 불안정한(UnStable) 정렬로 해석이 되는데, 먼저 안정적인 정렬은 나열된 수를 정렬한 뒤에도 기존에 있던 순서를 ..

초안 : 2020년 12월31일 1차수정 : 2023년 4월 10일 트리는 이름처럼 나무(tree)와 같은 자료구조이다. 뿌리를 가지고 뻗어져 나뭇가지에서 잎들이 있는 모습을 거꾸로 뒤집으면 자료구조에서의 트리가 된다. 트리 관련 용어 - 노드(Node) : 실제로 저장하는 데이터 - 루트 노드(Root Node) : 최상위에 위치한 데이터 - 리프 노드(Leaf Node) : 마지막에 위치한 데이터들 - 부모-자식 : 연결된 노드들 간의 상대적 관계 - 깊이(Depth) : 노드 -> 루트 경로의 길이 - 높이(Height) : 노드 -> 리프 경로의 최대 길이 - 하위 트리(Subtree) : 어떤 노드 아래의 모든 것을 포함하는 트리 트리의 용도 - 계층적 데이터를 표현한다. - 검색 트리를 통해 ..

- 초안 작성 : 2020년 12월 27일 - 1차 수정 : 2023년 4월 3일 정렬 알고리즘이란? - 목록 안에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘 - 입력데이터는 보통 배열과 같은 데이터 구조 (연결리스틑 사용하면 처음 or 끝부터 차례대로 훑어야해서 정렬 시 사용이 복잡해진다) - 흔히 사용하는 순서 : 숫자 , 사전 순서(A~Z) - 정렬 방향 : 오름차순, 내림차순 사용하는 이유?? - 좀 더 효율적인 알고리즘을 사용하기 위해 - 사람이 읽기 편함을 위한 등등... 정렬시 고려사항 - 시간 복잡도 - 메모리 사용량 - 안정성(stability) - > safety가 아니라 stable 이다. -> 데이터의 순서가 바뀌지 않느냐 여부 문제 - 직렬 vs 병렬 안정성을 잘 모르는 ..

1. 장점 - 가독성이 좋음. - 코드가 짧음. - 각 단계의 변수상태가 자동 저장됨. (함수의 스택프레임 덕분) - 코드 검증도 쉬움 2. 단점 - 재귀적 문제 분석 및 설계가 직관적X - 맹목적인 믿음이 필요 (수학적 귀납법 이해하면 믿음이 생김) - 스택 오버플로 발생가능(재귀 함수 호출이 너무 깊은 경우) - 함수 호출에 따른 과부하 * 읽기 좋은 코드 작성이 기본이다. 가독성이 좋고, 유지보수가 쉬운 코드가 더 중요하다. 다음과 같은 경우는 반복문으로 변경 - 스택 오버 플로가 날 가능성이 있는 경우 - 성능 문제가 일어날 가능성이 큰 경우 - 성능 문제가 확인 된 경우 * 모든 재귀 함수는 반복문으로 작성 가능하다.

std::set ? - std::set은 std::map과 동일한 자료구조를 사용하므로, 서능의 특성은 맵과 동일하다. - 차이점 한가지는 검색으로 반환된 항목이 std::set에 있다는 것이다. - key는 있지만 value는 없다 - 중복을 허락하지 않고, 정렬되는 집합 - 용도로 특정 값에 대해 검색을 빠르게 하고 싶을때 사용 std::set 사용법 https://blockdmask.tistory.com/79 [C++] set container 정리 및 사용법 안녕하세요. BlockDMask 입니다 ! 오늘은 연관 컨테이너 set, multiset, map, multimap 중 set에 대해 학습해보겠습니다. 순서는 set container -> set의 사용법 -> set의 생성자와 연산자 -> ..

std::map은? - 순서가 지정된 연관 컨테이너 - 항목을 삭제하는 경우를 제외하고 반복자와 참조가 절대 무효화 되지않는다. - 반복자는 항목을 정렬한 순서나 역순으로 정렬한 순서로 생성 - 노드기반 자료구조. 하지만 키의 값에 따라 노드를 자동으로 정렬 - 내부는 균형 이진트리로 구현 - 트리를 사용하지만 트리는 아니다. - 메모리 관리자와 매우 간단하고 예측 가능한 방법으로 상호작용 - 각 항목에 할당된 저장 공간의 크기는 모두 같음.(메모리 단편화 생길 가능성 낮음) - 검색은 std::vector로 std::lower_bound 사용하는게 더 빠름 사용 방법 : https://blockdmask.tistory.com/87 [C++] map container 정리 및 사용법 안녕하세요. Bloc..

2020-08-28 첫 작성 2021-02-03 1차 수정 2021-04-08 2차 수정 언리얼 엔진을 이용하여 구현해보았고, 위젯 버튼만 블루프린트 사용. 우선순위 큐 기반(TArray 사용)으로 작성. 마우스 왼쪽 버튼으로 시작 지점을 선택 후 도착 블록을 선택하게 되면 로직이 동작하고, 쉬프트+마우스 왼쪽 버튼으로 검은색 벽을 설정. 벽을 피해 경로가 설정된다. 경로 추출 시 타이머를 이용해 0.1초 간격으로 찾은 경로의 블록 매터리얼의 색상을 변경. https://www.youtube.com/watch?v=0J2aWNcIU9o&feature=youtu.be 작동원리: - 각각의 블록들에는 3개의 값이 들어 있다. G : 시작블록부터 해당 블록까지의 이동한 거리값 H : 해당 블록에서부터 목표 블록..

hyo-ue4study.tistory.com/111 [자료구조]트리(Tree) 특징 / 운행 3가지 / C++ 트리는 이름처럼 나무와 같은 자료구조이다. 뿌리를 가지고 뻗어져 나뭇가지에서 잎들이 있는 모습을 거꾸로 뒤집으면 자료구조에서의 트리가 된다. 게임에서의 트리 게임 개발을 할때의 트리 hyo-ue4study.tistory.com #include #include #include using namespace std; class Node { public: Node() : mData(0) , mLeft(nullptr) , mRight(nullptr) , mRoot(nullptr) {} Node(int data) : mData(data) , mLeft(nullptr) , mRight(nullptr) , m..