Taene's

- 순차 탐색 sequential search이란 순서대로 찾아간다는 의미이다. 배열은 메모리가 1차원 직선으로 나열된 형태라 선형(linear)이라는 용어를 사용하는 경우가 많은데, 배열을 순차적으로 탐색하는 것은 메모리를 한 칸 한 칸 선형으로 찾는 것이므로 선형 탐색이라고도 부른다. #include using namespace std; void Print(int* arr, int size) { for (int i = 0; i < size; i++) { cout

- 자료 배열의 모든 값을 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교 하여, 자신의 위치를 찾아 삽입해서 정렬을 완성한다. - best case에서 (배열의 크기 - 1)만큼만 정렬하고자 탐색하고 바로 끝나고, stability하다. #include using namespace std; void Print(int* arr, int size) { for (int i = 0; i < size; i++) cout

- 서로 인접한 두 값을 검사해 정렬한다. (인접한 2개의 값을 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.) - swap을 많이 해야하기 때문에 전반적인 효율성은 떨어지나, best case에서는 빨리 끝나고, stability하다. #include using namespace std; void Print(int* arr) { for (int i = 0; i < 5; i++) cout

- 배열의 index를 0부터 시작해서 바꿀 위치를 정해두고 index가 0~size-1 중 가장 작은 값(최소값)을 찾아서 index가 0인 값과 가장 작은 값을 (swap)바꾸고, 다음 index가 1인 값과 index가 1~size 중 가장 작은 값을 바꾸는 선택 정렬이다. - 중복된 최소값이 있을 경우에도 똑같이 정렬하기 때문에 key, value의 쌍으로 이뤄진 정렬에서는 같은 key값의 정렬에서 value의 정렬이 바뀌어있을 수 있으므로 instability하다. #include using namespace std; int main() { for (int size = 1; size < 1000; size++) { int count = 0; int* arr = new int[size]; for ..

- 보통 탐색 알고리즘에서 상하좌우나 대각선 등의 방향을 탐색해야할 때 사용한다. - 아래 예시는 dirX,dirY 배열을 만들고 반복문을 돌리면서 newY, newX를 만들어 재귀함수에 다시 넣는 경우이다. bool arr[51][51] = { false }; bool visit[51][51] = { false }; int dirX[4] = { 0,0,-1,1 }; int dirY[4] = { -1,1,0,0 }; int m, n, k; void dfs(int y, int x) { visit[y][x] = 1; for (int i = 0; i < 4; i++) { int newY = y + dirY[i]; int newX = x + dirX[i]; if (arr[newY][newX] == 1 && vi..

- 데이터 타입에는 각 메모리 사용 크기가 있다. int를 표현하자면 4byte(32 bit)의 크기를 가지고, 00000000 00000000 00000000 00000000이 된다. 1byte = 8bit - 만약 무언가를 있고 없고만 체크한다면 bool 변수 32개를 쓰는 대신, 하나의 비트를 다룰 수있으면 우리는 int하나로 32개의 유무를 표시할 수 있다. 또 비트 연산은 연산 속도도 빠르다. (만약 2번째 아이템이 있다면 0100 이런식으로 0을 1로 바꾸어 표현함) & 비트단위로 AND 연산을 한다. (둘 다 1일 경우에만 1이고, 나머지는 0) | 비트단위로 OR 연산을 한다. (둘 중 하나라도 1일 경우 1이고, 둘 다 0일 경우에만 0) ^ 비트단위로 XOR 연산을 한다. (둘이 같으면..