기억을 위한 기록들

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

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

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

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

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 : 해당 블록에서부터 목표 블록..

2021.02.03 첫 작성 2021.03.30 수정 1. 목표점 - 다익스트라는 시작점으로부터 나머지 정점들까지의 최단거리를 구한다. - A* 는 시작점이 정해지고, 목표점이 정해지면 두개의 최단 거리를 구한다. 2. 남은 거리 고려 - 다익스트라는 시작점에서 정점에 이르는 최단 거리만을 고려. 목적 정점이 없기에 남은 거리를 구할수도 없다. - A* 는 고려한다. 3. 최적 경로 - 다익스트라는 임의의 시작점으로부터 시작하여 모든 정점을 탐색. 최적 경로 보장 하지 않는다. (* 이를 해결하기 위해 모든 정점을 시작점으로 가지는 플로이드와샬 알고리즘이다 있다. 하지만 정점의 개수만큼 시간비용이 증가한다.) - A* 는 시작지점부터 목표지점까지의 휴리스틱 함수를 통해 추정하여 점수를 매기고, 그 점수를..

hyo-ue4study.tistory.com/193 [알고리즘] 최단 경로찾기 ? 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 프림 알고리즘 과 동작방식이 비슷하다. 다만 프림알고리즘은 단순히 간선의 길이를 이용해 어떤 간선을 먼저 연결할지 결정하는데 반해, 다익스트라 알고리즘은 '경로 hyo-ue4study.tistory.com 다익스트라 알고리즘과 비교 다익스트라 알고리즘은 하나의 정점에서 출발해서, 출발한 정점을 제외한 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 하지만, 모든 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 플로이드 와샬 알고리즘이 있다. 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 ..

트리의 형태로 생성과정으로는 "이진 공간 분할 법은 하나의 공간을 특정한 최종 목적을 만족할 때까지 공간을 재귀적으로 2개씩 분할하는 과정이다. 예를 들면, 충돌 감지를 목적으로 하는 경우에는 원래 물체가 충분히 충돌 검사를 간단하게 할 수 있도록 공간이 분할되며 렌더링을 목적으로 하는 경우에는 화가 알고리즘을 가장 효율적으로 사용할 수 있도록 볼록한 도형으로 공간이 분할된다." 응용 방법 www.youtube.com/watch?v=1syQjkWeRZ0&ab_channel=Seunggeunjo www.youtube.com/watch?v=FO12bZD3a5M&ab_channel=%EC%8B%A0%ED%98%95%EC%A2%85 아직 구현 해본적은 없지만, 나중에 필요로 할 때, 예를 들어 로그라이크 같은 ..

트리의 자식 노드가 4개인 트리를 뜻하고 있다. 3D 데이터를 표현하기 위한 자료구조를 '장면 그래프( Scene Graph )'라고 부르는데, 이도 역시 그에 포함된다. 장면 그래프( Scene Graph )에는 쿼드 트리 이외에도 이진트리(2)와 옥트리(8)가 존재한다. 말 그대로 이진트리는 자식노드가 2개, 옥트리는 자식 노드가 8개가 있는 트리를 의미한다. 쿼드 트리는 일반적으로 상하 개념이 없어서 3차원 세계를 4개의 평면으로 분할하지만, 옥트리는 4개로 분할한 쿼드트리에서 상하의 분할 평면으로 나누어 총 8개의 자식 노드를 갖게 된다. 일반적으로 지형( Terrain )에 사용된다. 정의 : 공간을 재귀적인 호출로(Recursive ) 4개의 자식 노드로 분할하는 방법 지형으로 설명을 하자면 ..

qiao.github.io/PathFinding.js/visual/ PathFinding.js qiao.github.io 길찾기 알고리즘의 다양한 방법들이 있는데 어떻게 동작하는지 보기 쉽게 표현되는 사이트 시작점 도착점을 드래그로 옮길수 있으며, 빈블럭을 클릭 시 벽이 생깁니다. 오른쪽 UI "Start Search"로 시작

"오던 길을 따라 되돌아 나오다"라는 뜻 여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘. 후보해 속에서 해를 찾아가는 과정 1. 루트에서부터 출발 2. 현재 위치한 부분해에서 선택이 가능한 다음 부분해의 목록을 얻습니다. 3. 2번에서 얻은 목록의 부분해들을 하나씩 방문합니다. 4. 방문한 부분해가 해가 요구하는 조건을 만족시키면 그 자리에서 2번 3번 과정을 수행, 그렇지 않으면 그 이전 부분해로 돌아 나와 다른 부분해를 시도 5. 최종해를 얻을 때까지, 또는 모든 경우의 수를 확인해도 해가 없을음 확인했을 때까지 2~4번 과정을 반복

기존 그래프는 정점의 집합과 간선의 집합으로 이루어진 자료구조이다. 여기서 새로운 속성인 간선간의 가중치(Weight)를 부여해주게 된다. 최소 신장트리에서 신장트리(Spanning Tree)에서 Spanning는 여러 가지 뜻을 갖고 있지만, 떨어져 있는 둘 사이를 다리 등으로 연결한다는 뜻으로 사용. 즉, 신장 트리는 그래프의 모든 정점을 연결하는 트리이다. 신장트리는 한편으로 그래프의 하위 개념이기도 합니다. 그래프는 사이클을 형성하는 간선만 제고하면 트리로 됩니다. 최소 신장트리란 결국 최소 가중치 신장트리라고도 불립니다. 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리인것이다. 보통 "최소한의 비용으로 모든 도시를 연결하는 도로를 건설할 방법을 찾아라"라는 문제..