코딩 일기장

구현 문제에 속하는 자물쇠와 열쇠 문제입니다. https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제 설명 고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각..

🐶 이진 탐색 Binary Search 이미 정렬된 데이터에서 특정 원소를 찾을 때 시작점, 끝점, 중간점을 지정하여 수행함 찾으려는 값과 중간값을 비교하여 중간점 이후 혹은 이전으로 데이터 탐색의 범위를 절반으로 줄일 수 있음 따라서 확인할 때마다 데이터의 개수가 절반으로 줄어들기 때문에 시간 복잡도 = O(logN) 탐색 범위가 1000만을 넘어갈 때 사용하면 좋다는 점! recursion으로 구현한 이진 탐색 const n = 10, target=7; const array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]; function binarySearch(start, end, target) { let mid = Math.floor((start + end) / 2); if(s..

전형적인 divide-and-conquer 알고리즘이다. divide-and-conquer이란, 큰 문제를 작은 문제로 쪼개고 쪼개서, 작은 문제를 푼 후 결과를 병합하여 푸는 방법을 의미한다. #include #define max 6 //conquer void merge(int a[], int low, int mid, int high){ int b[1000]; // sort된 배열을 넣을 새로운 배열 int i=low, j=mid+1; //i는 왼쪽 배열의 시작, j는 오른쪽 배열의 시작 int k=0; //k는 새로 sorted된 array의 현재 위치 //한쪽이 다른 한쪽보다 완전히 작을때까지 while(i

insertion sort는 한 기준점을 중심으로 오른쪽에는 unsorted list, 왼쪽에는 sorted list가 있는 형식입니다. 오른쪽의 정렬되지 않은 element를 하나씩 왼쪽으로 옮기면서 부분적으로 리스트를 정렬하고, 결론적으로 기준점이 맨 끝에 갔을때 (오른쪽에 element가 없을 때) sorting이 완료됩니다. #include #include #define max 6 int main() { // sample input: 5 12 6 80 2 15 int key, now, temp; int A[] = { 5, 12, 6, 80, 2, 15}; printf("unsorted: "); for(int i=0 ; i key) { A[temp+1] = A[temp]; temp--; } A[te..