거북이의 IT 공부

백트래킹이란? 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는(Backtracking) 기법을 말한다. -> 반복문의 횟수를 줄여서 효율적이다!!! 좀더 정확하게 말하자면 어떤 노드의 유망성, 즉 해가 될 만한지 판단한 후 유망하지 않다고 결정되면 그 노드의 이전(부모)로 돌아가(Backtracking) 다음 자식 노드로 가는 기법을 말한다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다'(완전 탐색 기법) 에 기본 아이디어가 있다. 대표적인 완전 탐색 방법으로는 DFS (Depth First Search, 깊이 우선 탐색) 이 있다. 하지만 DFS 는 모든곳..

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%9F%AC%EB%93%9C_%ED%95%84 플러드 필 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 4방향 재귀적 플러드 필 플러드 필(영어: flood fill) 혹은 시드 필(영어: seed fill)은 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 이 알고리즘은 그림 프로그램에서 연결된 비슷한 색을 가지는 영역에 "채우기" 도구에 사용되며, 바둑이나 지뢰 찾기 같은 게임에서 어떤 비어 있는 칸을 표시 할 지를 결정할 때에도 사용된다. 알고리즘[편집] 8방향 재귀적 플러드 필 플러드 필 알고리즘은 시작 ko.wikipedia.org 플러드 필 알고리즘 : 주어진 시작점으로부터 연결된 영역..

기본세팅 typedef struct ListNode { int data; struct ListNode* link; } ListNode; int main(void) { ListNode* p1, * p2, * head; p2 = (ListNode*)malloc(sizeof(ListNode)); p1 = (ListNode *)malloc(sizeof(ListNode)); p1->data = 10; p1->link = NULL; p2->data = 20; p2->link = NULL; p1->link = p2; head = p1; } ListNode라는 구조체를 만들고 ListNode의 포인터를 이용하여 연결 리스트를 만든다. 삽입 //phead : head를 가리키는 포인터 -> head의 손상 방지 //p ..

1. 선택 정렬 : 가장 작은 숫자를 찾아서 정렬되지 않은 구간의 맨 처음으로 옮긴다. c언어 code #define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t)) void selection_sort(int arr[], int n) { int i, j, least, temp; //least : 정렬되지 않은 것 중에서 가장 작은 숫자 for (i = 0; i arr[j]) { least = j; } } SWAP(arr[i], arr[least], temp); } } 2. 삽입정렬 : 정렬되지 않은 요소 하나를 정렬된 구간에 어디에 넣을지 정하는 정렬 key..