꼬박로그 꼬박로그

BubbleSort(버블 정렬)란? 인접한 두 항목의 값을 비교해서 일정한 기준을 만족하면 서로 값의 위치를 변경하여 정렬하는 방식입니다. 오름차순 정렬은 두 항목의 값을 비교하여 앞에 있는 값이 더 크다면 두 항목의 위치를 변경합니다. 장점 : 두 개의 항목을 비교하는 방식으로 정렬하기에 개념이 단순하어 구현이 간단하다. 단점: 비교 작업이 많으면 많아질수록 연산 시간이 오래 걸린다. 버블 정렬은 첫 번째 값과 두 번째 값 , 두 번째 값과 세 번째 값 , 세 번째 값과 네 번째 값 이런 패턴으로 마지막까지 값을 비교하여 값의 위치를 바꾸며 정렬합니다. 1회 반복하게 되면 가장 큰 값은 마지막 자리에 위치하게 되고, 다시 배열의 첫 요소 부터 지금까지의 정렬된 배열의 모든 요소가 크기 순서대로 정렬될 ..

백트래킹 모든 경우의 수를 전부 고려하는 알고리즘이다. 단 조건에 만족할 때만. 일종의 트리 탐색 알고리즘 탐색하는 과정에서, 유망(promising)하지 않은 노드를 생략하고 이전 단계로 돌아가 다른 후보해를 찾는 알고리즘. *해 : 노드의 유망성 가지치기(Pruning) : 불필요한 탐색 부분을 제거하는 방법 트리 구조에서 나무 가지를 치듯 가능성이 없는 부분을 제거 함 일반적으로 DFS(깊이 우선 탐색)을 통하여 구현함 BFS(너비 우선 탐색)의 경우 상대적으로 많은 메모리가 필요함 N-Queens에서 백트래킹 N-Queens는 N * N 체스판에 N개의 Queen을 놓아야 하는 문제입니다. Queen은 동서남북 대각선으로 이동을 해야 하고, 충돌이 발생하는 위치를 피해서 Queen을 놓아야 합니다..

오늘 했던 일 DFS(깊이 우선 탐색) BFS(너비 우선 탐색) 그래프 자료구조를 탐색하는 방법에는 대표적으로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)가 있습니다. DFS DFS(Depth First Search)는 어떤 정점(Root)으로 부터 시작하여, 해당 정점의 자식들을 먼저 탐색하는 방식을 말합니다. 스택(Stack)과 재귀 호출을 사용하여 구현할 수 있다. 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 시간 복잡도 : O(V + E) BFS BFS(Breadth First Search)는 어떤 정점(Root)으로 부터 시작하여, 정점들과 같은 레벨에 있는 노드들(형제 노드)을 먼저 탐색하는 방식을 ..