728x90

CS/알고리즘 및 자료구조33

[알고리즘] 다양한 이분 탐색 문제 풀이 2차 배열 이분 탐색 row 값과 cols값을 구하기만 한다면 문제는 import java.io.IOException; public class Main { private static boolean solution(int[][] arr, int target) { if (arr == null || arr.length == 0) { return false; } int left = 0; int rows = arr.length; int cols = arr[0].length; int right = rows * cols - 1; while (left days) { minWeight = carryingWeight + 1; } //현재 적재량이 넉넉하기 때문에 적재량 감소 else { maxWeight =.. 2023. 2. 24.

이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree) 규칙 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼 중복된 키를 허용하지 않음 각가의 서브 트리도 이진 탐색 트리를 유지 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬됨 이진 트리에 비해 탐색이 빠르다. (균형 유지 필요) 균형 상태 : O(logN) 불균형 상태 : O(N) 탐색 찾고자 하는 데이터를 루트 노드부터 비교 시작 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동. 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어진다. 찾는 데이터가 없으면 null반환 삽입 루트 노드부터 비교 시작 삽입할 키가 현재 노드의 키보다 작으면 왼쪽, 크면 오른쪽 노드로 이동. L.. 2023. 2. 15.

해시 테이블(Hash Table) 해시 테이블(Hash Table) 키, 값을 대응시켜 저장하는 데이터 구조로 키를 통해 해당 데이터에 빠르게 접근 가능 해싱 키를 특정 계산식에 넣어 나온 결고를 사용하여 값에 접근하는 과정 해시 테이블 구조 키 : 해시 테이블 접근을 위한 입력 값 해시 함수 : 키를 해시 값으로 매핑하는 연산 해시 값 : 해시 테이블의 인덱스 해시 충돌 해시 함수를 통한 해시 값이 동일한 경우 해시 테이블의 같은 공간에 서로 다른 값을 저장하려는 경우 해시 충돌 해결 방법으로는 크게 개방 주소법과 분리 연결법이 있다. 해시 충돌 해결 방법 개방 주소법(Open Address) 충돌 시, 테이블에서 비어 있는 공간의 hash를 찾아 데이터를 저장 hash와 value가 1:1 관계 유지 (해시 키는 하나의 데이터만 가지.. 2023. 2. 10.

[Algo]-Counting Sort 요약 핵심 아이디어 카운팅 정렬(계수 정렬)은 입력을 반복하고 각 항복이 발생하는 횟수를 새로운 배열에 카운트한다. 카운트한 배열을 사용해 정렬한다. 장점 시간복잡도는 O(n) 으로 엄청난 성능을 보여주는 알고리즘이다. 대표적인 빠른 정렬 알고리즘보다 성능이 좋다. 큌 정렬, 힙 정렬, 합병 정렬 등의 시간복잡도는 O(nlogn) 으로 빠른 성능을 가지고 있다. 단점 입력값의 범위를 미리 알고 있을때만 사용하는게 좋다. 정렬을 하기 위해 새로운 배열을 선언해주어야 한다. 즉, 입력값의 범위가 커지면 메모리 낭비가 된다. ex) 5개의 원소를 정렬하고 하는데, 수의 범위가 0~5000 이라면 새로운 배열의 사이즈는 5000이 된다. 작동 애니메이션 URL https://www.cs.miami.edu/hom.. 2022. 10. 14.

동기(Synchronous), 비동기(Asynchronous), 블록킹(Blocking),논블록킹(Non-Blocking) Reference - https://poiemaweb.com/js-async 동기 비동기 차이 동기는 요청 후 결과를 받을 때까지 다른 일을 하지 못한다. 비동기는 요청 후 결과를 받을 때까지 다른 일(다른 요청)을 할 수 있다. 동기(Synchronous) - 블록킹(Blocking)방식 동기식 처리는 직렬 적으로 태스크(task)를 수행한다. 즉, 태스크는 순차적으로 실행되며 어떤 작업이 수행 중이면 다음 작업은 블로킹(blocking, 작업 중단) 된다. T1, T2 트렌젝션의 단위를 동시에 맞춘다. 동기식 처리는 T1, T2의 -10000, +10000이 동시에 일어나기 위한 것으로, T1의 전송, T2의 결과 전송 후 동시에 진행 되어야 한다. 트랜젝션을 이용한 동시성 제어를 하기때문에 설계가 .. 2022. 2. 11.

Keras Tuner 딥러닝에 입문후 모델을 가져다 사용하다가 이제 어느정도 모델을 구성할 수 있다면, 어떻게 이 모델의 성능을 높일까 고민하게 된다. 최적의 모델을 위해 모델의 요소 값을 찾는 과정을 "하이퍼파라미터 튜닝"이라고 한다. 한 모델의 하이퍼파라미터 요소의 개수가 많을수도 적을 수도 있어 모델 구성에 따라 성능의 차이는 천지차이이며 어렵다. 그래서 구글이 이러한 캐라스 모델을 쉽게 튜닝하기 위해 "Keras Tuner" 프레임 워크를 개발했다. Cutting Edge TensorFlow: New Techniques (Google I/O'19) "Keras Tuner"에 관한 발표 - 7분 20초 까지 공식 문서 기준으로 부분부분 이해해 보자. - https://keras-team.github.io/keras-tu.. 2021. 6. 4.

C언어 - 힙 정렬 구현 코드 #include #define num 8 int node[] = {2,1,33,21,6,42,50,5}; void heapify(int n, int start, int *node) { int l,r,tmp; l = start*2+1; r = start*2+2; if(r>n) { return; } if(node[l] > node[start] || node[r] > node[start]) { if(node[l] > node[r]) { tmp = node[start]; node[start]=node[l]; node[l]=tmp; return heapify(n,l,node); } else { tmp = node[start]; node[start]=node[r]; node[r]=tmp; return heapify.. 2021. 5. 21.

하이퍼밴드(Hyperband), Successive Halving Algorithm(SHA)의 흐름 이해하기 하이퍼 밴드는 Kerads Tuner 에서 사용되는 탐색 방법(알고리즘)의 하나이다. 가끔 요약을 미리 보면 이해하기 수월할 때가 있다. 요약 HYPERBAND는 SHA를 이용해 탐색하며 SHA의 B와 n을 일정 비율로 정해준다. SHA는 B/n번 탐색 B*(2^0) -> b/2(1)*(2^1) -> ... -> b/2(n-1)*(2^(n-1)) -> 1*(2^n) ex) B =32 n=8 일 경우 32개중 랜덤하게 8개를 뽑아 1번 학습 후 4개 추출 -> 추출된 4개 2번 학습 후 2개 추출-> 추출된 2개 4번 학습 후 1개 추출 -> 1개 8번 학습 -> 결과!!!! 하이퍼 밴드 알고리즘은 keras tuner 프레임 워크에서 사용되는 알고리즘 중 하나이다. keras tuner는 모델을 쉽게 튜.. 2021. 5. 19.

힙 정렬(Heap Sort) 힙 정렬(Heap Sort)은 큌 정렬(Quick sort)과 병합 정렬(Merge Sort)과 같은 시간 복잡도 O(N*logN)를 가지고 있다. 힙 트리를 이용하는 정렬 방법이다. 힙 트리란 힙 트리의 조건 중 부모 노드의 값은 항상 자식 노드(하위 노드)의 값보다 크거나 작아야 한다. 힙 트리는 위의 조건은 만족하는 정렬은 두가지 뿐이다. 최대 힙(Max Heap), 최소 힙(Min Heap) 힙 트리 구조의 자녀 트리 사이에는 대소관계는 정해지지 않는다. 또한 힙 트리는 완전 이진 트리를 조건으로 가지고 있어야 한다. 왼쪽부터 차근차근 채워나가며 1~n까지 만들어지는 트리구조이다. 완전 이진 트리의 장점은 트리를 배열로 쉽게 구현이 가능하며, 부모 노드와 자식 노드 간에 관계를 수식화 할 수 있다.. 2021. 5. 14.

c언어 - 이진 트리 레벨 순회 (LevelTraverse) 이진트리 레벨 순회란. 트리를 레벨이 낮은 순으로 순회하는 검색 방식 중 하나이다. 같은 레벨에 있다면 왼쪽부터 오른쪽으로 나열된다. (ex. 1, 2, 3, 4, 5, 6, 7) 레벨 순회를 하기 위해서는 트리를 큐 자료구조에 넣어주면 된다. 이런 식으로 첫 root를 넣으면 그 root의 왼쪽 자식과 오른쪽 자식 순으로 넣어준다. Queue는 FIFO 방식으로 먼저 넣은 값이 우선으로 나오기 때문에 부모-자식 순으로 자식-자식의 자식 순으로 레벨 순회를 하게 된다. 사실 이진 탐색 트리(BST) 포스팅에서 다룬 트리와 Queue 포스팅에서 다룬 내용을 합치면 루트 노드를 넣으면 그 노드의 자식 노드를 넣고 그 노드의 자식을 넣는 하는 방식이다. 트리 노드를 큐에 넣어야 하는데 큐를 선언할 때 '트리노.. 2021. 4. 16.

C언어 - 큐, 큐 구현 (Queue), 배열 구현 큐는 FIFO 구조로 먼저 들어오면 먼저 나가는 성질을 가지고 있다. 스택과 비슷하면서도 다른 구조를 가지고 있다. 그래서 스택은 세워서 넣는 식으로 하고 큐는 눕혀서 넣고 빼면서 설명을 한다. 코드 #include #define MAX 5 int front = 0; int rear = 0; int queue[MAX]; void init(int data) { int tmp=(rear+1)%MAX; if(tmp == front) { printf(" Full "); printf(" \n"); return; } else { rear = (rear+1) % MAX; queue[rear]=data; } } void delete() { if(front == rear) { printf(" Emty "); printf.. 2021. 3. 12.

C언어 - 이진 트리, 이진 탐색 트리 구현 (binary tree, binary search tree) 코드 //binary search tree #include #include typedef struct node { int data; struct node* left; struct node* right; }node; node* root; node* insert(node* root,int data) { if(root == NULL) { root = (node*)malloc(sizeof(node)); root->right = root->left = NULL; root->data = data; return root; } else { if(data data) root->left = insert(root->left,data); else root->right = insert(root->right,dat.. 2021. 3. 5.

트리와 이진 트리(Binary Tree) 트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 그리고 부모 노드와 자식 노드로 이루어진 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.(ko.wikipedia.org/wiki/트리_구조) 이진트리란 (Binary Tree) 컴퓨터에서 쓰이는 이진트리는 수학과 다르다. 컴퓨터에서 이진트리는 부모 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 이진 트리의 조건들 한 부모 노드에 자식 노드는 최소 0부터 최대 2개의 자식 노드를 가질 수 있다. 부모보다 작으면 왼쪽 자식 부모보다 크면 오른쪽 자식으로 보내야 한다. 이진트리를 순회하는 방식은 4가지가 있다. 1. 전위 순회 2. 중위 순회 3. 후위 순회 4... 2021. 2. 5.

C언어- 폰트 컬러 색갈 바꾸기 윈도우와 맥이랑 운영체제가 다르다 보니 해더 파일이 차이가 난다. (window.h) 그중 하나는 출력할 때 폰트 컬러 바꾸는 기능이다. 다음번엔 sleep 함수에 대해서도 설명할까 한다. 윈도우에서는 window.h 헤더 파일은 가져와서 사용하면 되는데, 맥은 유니스 기반이라 조금 다르다. 윈도우에서는 위와 같은 색상표를 가지고 있으며 코드는 SetConsoleTextAttribute( GetStdHeandle( STD_OUTPUT_HANDLE ), 색갈표 숫자 ); ex ) SetConsoleTextAttribute( GetStdHeandle( STD_OUTPUT_HANDLE ), 6 ); //노란색 글자 Mac, 맥에서는 위와 같은 색상표를 가지고 있으며 코드는 #include int main() .. 2021. 1. 8.

c언어 - 병합 정렬(Merge Sort) 이전 글에서 퀵 정렬에 대해 포스팅 했다. 병합 정렬은 퀵 정렬과 매우 비슷하지만 조금 다른 정렬이다. 퀵 정렬은 피벗을 정해 정렬을 하는데 피벗을 선택하는데서 정렬의 성능이 정해진다. 병합 정렬은 배열의 크기를 반으로 쪼개 정렬해 정렬되는 속도가 일정하다. 시간 복잡도로 보면 최악 평균 최선 퀵 정렬 O(N^2) O(NlogN) O(NlogN) 병합 정렬 O(NlogN) O(NlogN) O(NlogN) 시간 복잡도를 보면 평균은 비슷 하지만 최악에서 차이가 난다. O(N^2)는 버블, 선택 정렬과 같아 느리다. 속도가 일정하다는 장점을 가지고 있다. 단점은 메모리가 필요하다. 병합과정에서 같은 사이즈의 다른 배열에 임시로 저장하기 때문이다. 이제 병합 정렬은 배열의 크기/2 의 값을 기준으로 좌, 우로.. 2021. 1. 1.

c언어 - 퀵 정렬 (QuickSort) 퀵 정렬은 이름처럼 빠른 정렬이다. 퀵 정렬은 적절한 하나의 기준(피벗)을 잡고 피벗을 기준으로 삼아 값들을 정렬해나간다. 피벗(pivot)을 어떻게 설정하느냐에 따라 정렬 시간에 큰 영향을 준다. 그래서 최악의 경우 O(n^2)의 시간이 걸릴 수 있다. 피벗을 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 보내면서 정렬해간다. 정렬할 리스트가 1~0일때 까지 반복하는 정렬이다. 글로 설명하는건 쉬우나 코딩할때 조금 꼬일수있으니 주의하면서 코딩해보자. low, high 을 좌표로 잡고 피벗과 비교하면서 low 는 피벗보다 큰 수를 high 는 피벗보다 작은수를 서로 교환한다. low 와 high가 교차하는 순간 low 와 피벗을 교체한다. 그리고 피벗을 기준으로 -1, +1 한 값을 재귀함수를 이용하여 퀵.. 2020. 12. 25.

c언어 - 쉘 정렬 (Shell's Sort) 쉘정렬은 삽입 정렬의 개선판으로 생각하고 접근하면 편하다. 그러므로 사전지식으로 삽입정렬을 이해하고 있어야한다. 간단하게 삽입 정렬은 한번에 하나의 값만 바꿔가며 정렬하는 알고리즘이다. 만약 8,2,4,5,1,9 라는 배열이 있다고 가정하고 삽입 정렬을 하면 단1회 만으로 1,2,4,5,8,9 로 정렬이 된다. 이런 장점을 키운 정렬이 쉘 정렬이다. *참고 - 삽입 정렬 쉘 정렬은 갭의 크기가 줄어들면서 정렬되는 알고리즘이다. 예를들어 n개의 값을 가지고 있는 배열이 있다고 가정하면, 처음 갭은 n/2인 값으로 그 후의 갭은 전의 갭/2 인 값으로 정렬해 나간다. *갭은 짝수보다 홀수가 좋다, 갭이 짝수일때 + 1을 해서 홀수를 만들어주자 *c언어에서 정수인 변수의 소숫점은 무시된다. ex) 1.9 =>.. 2020. 12. 18.

c언어 - 삽입 정렬 (Insertion Sort) 정렬되는 모습이 마치 삽입되는 것과 유사해 삽입 정렬로 불린다. 삽입 정렬은 이전에 봤던 순차, 버블, 선택 정렬과 큰 차이점이 있다면 최선의 경우 N번의 비교 후 정렬이 종료된다. 비교 시 자기 자신보다 작은 수가 있으면 멈추고 다음 자리로 가 비교를 시작하기 때문이다. 그러므로 더 효율적이고 자주 이용되는 정렬이다. 비교하는 값은 노란색 정렬후 값은 보라색 핵심 알고리즘 void InsertionSort(int *arr,int n, int i, int j){ int key; for(i=1; i=0; j--){ if(arr[j] > key) arr[j+1] = arr[j]; else break; } arr[j+1] = key; } } 코드 #include void InsertionSort(int *ar.. 2020. 12. 11.

c언어 - 선택 정렬 (Selection Sort) 선택 정렬은 기준점을 잡고 처음부터 끝까지 비교 후 가장 작은 값을 바꾸는 정렬이다. 순차 정렬, 버블 정렬, 선택 정렬 세 정렬은 코드는 단순하나 컴퓨터 입장에서 비효율 적이여서 싫어하는 정렬이다. 비교대상이 30개 미만일 경우 사용하기에 좋다. 비교 횟수는 n-1 -> n-2 -> n-3 -> ... -> n-n+3 -> n-n+2 -> n-n-1 순으로 값이 줄어들며 비교된다. 비교하는 값은 노란색 정렬후 값은 보라색 핵심 알고리즘 void SelectionSort(int *arr,int n, int i, int j){ int min; for(i=0; i 2020. 12. 4.

C언어 - 버블 정렬 (Bubble Sort), 버블 정렬 개선 파도타듯 두 값씩 정렬해가면서 큰 수를 맨 뒤로 보내면서 채워간다 마지막 수를 제외하고 다시 처음부터 반복하여 비교하며 정렬하는 알고리즘이다. 순차 정렬, 버블 정렬, 선택 정렬 세 정렬은 코드는 단순하나 컴퓨터 입장에서 비효율 적이여서 싫어하는 정렬이다. 비교대상이 30개 미만일 경우 사용하기에 좋다. 비교 횟수는 n-1 -> n-2 -> n-3 -> ... -> n-n+3 -> n-n+2 -> n-n-1 순으로 값이 줄어들며 비교된다. 비교하는 값은 노란색 정렬후 값은 보라색 핵심 알고리즘 void BubbleSort(int *arr,int n, int i, int j){ for(i=n-1; i>0; i--){ for(j=0; j arr[j+1]){ swap(&arr[j],&arr[j+1]); } }.. 2020. 11. 27.

C언어 - 순차 정렬 순차정렬은 단순하게 0~N의 자리를 순차적으로 진행하며 정렬하는 알고리즘이다. 기준점을 0 혹은 N으로 두고 커지거나 작아지면서 정렬해가면 된다. 순차 정렬, 버블 정렬, 선택 정렬 세 정렬은 코드는 단순하나 컴퓨터 입장에서 비효율 적이여서 싫어하는 정렬이다. 비교대상이 30개 미만일 경우 사용하기에 좋다. 비교 횟수는 n-1 -> n-2 -> n-3 -> ... -> n-n+3 -> n-n+2 -> n-n-1 순으로 값이 줄어들며 비교된다. 비교하는 값은 노란색,정렬후 값은 보라색 핵심 알고리즘 for(int i = 0; i 2020. 11. 20.

C언어 - 정렬 (Sort) 정렬이란 Computer Science 에서 정렬 알고리즘은 데이터를 일정한 순서로 나열하는것이다. 흔히 사용되는 것은 숫자 정렬과 문자 정렬 (사전순 정렬)이다. 좋은 정렬을 만들기 위해 알고리즘의 최적화가 중요하다. 정렬에는 다양한 종류가 존재한다. 크게 내부 정렬과 외부 정렬이 존재하고 내부 정렬은 하나의 배열에 저장할 수 있을 경우 사용되고 외부 정렬은 데이터가 많아 하나의 배열로 저장하기 어려울때 사용된다. 외부 정렬은 내부 정렬을 응용한 정렬이기 때문에 내부 정렬을 먼저 공부하면 된다. 내부정렬에는 순차 정렬, 버블 정렬, 선택 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬, 병합 정렬, 힙 정렬, 도수정렬 등 다양하게 존재한다. 순차 정렬 자세히 보기 버블 정렬 자세히 보기 선택 정렬 자세히 보기 .. 2020. 11. 13.

C언어 - 배열 배열이란 같은 데이터형의 요소들이 동일한 크기를 나열되어 있는 집합이다. 이름으로 구분이 아닌 첨자에 의한 구분이라 그에 따른 장단점이 있다. 배열이 1 ~ n까지 있는 배열이 있다고 가정하면 c언어에서는 0 ~ n-1로 나타낸다. 배열도 변수와 같이 정수형 문자형 자료형 등으로 선언할 수 있다. //배열의 크기만 선언후 초기값을 설정하지 않음 int main() { int arr[5]; } //배열의 크기만 선언후 초기값을 설정하지 않음 int main() { char arr[5]; } 위와 같이 선언 가능하다. 배열에는 선언과 같이 초기화하는 것이 중요한데 초기화하는 방법은 아래와 같다. //배열의 크기설정과 배열의 값을 따로 지정, 크기 선언과 동시에 초기화를 해 주는것이 프로그래밍상 안전하다. i.. 2020. 11. 6.

자료구조 (Data Structure) 개념 및 정의 컴퓨터에서 자료를 효율적으로 사용하기 위해서 특성에 따라 분류 및 관리하여 저장 및 처리하는 모든 작업을 자료구조라 한다. 반복적이거나 복잡한 자료처리를 효율적으로 처리하기 위해 자료구조를 잘 이용해야 한다. 자료구조는 프로그래밍의 직접적인 영향을 미친다. 단순하게 하나의 반복을 생각하는 게 아닌 1000만 번 반복한다고 가정했을 때 자료구조가 주는 이점은 무시하기 어렵다. 이러한 자료구조가 모이면 알고리즘이라 할 수 있다. 정렬부터 선형구조 비선형구조 순으로 공부해 보자. 공부할 때 사용할 언어는 c언어이고 c언어를 택한 이유는 순차적 언어이기 때문이다. 선형구조 - 순차 리스트 또는 선형 리스트라고도 한다. 순차 리스트 - 데이터를 연속적인 기억공간에 배정하는 자료구조로서 배열, 큐, .. 2020. 10. 30.

순서도란? 순서도 (flow chart)의 flow는 ‘흐름’이라는 뜻입니다. 일이 일어나는 순서나 작업의 진행 흐름을 기호와 도형을 이용해서 순서대로 적어놓은 것을 말한답니다. 일의 순서를 흐름선으로 연결하며 각 도형에 정해진 의미에 따라 처리를 하게 됩니다. 밑의 흐름도에서 볼 수 있는 것처럼 타원은 시작과 끝을 의미하고 직사각형은 일을 순서대로 진행한다는 뜻입니다. 마름모 모양은 조건 기호라고 볼 수 있는데 그 조건이 맞는지를 확인하는 역할을 합니다 [네이버 지식백과] 순서도 [flow chart] (천재학습백과 초등 소프트웨어 용어사전) 그럼 기호와 도형에 정의된 의미를 알아보면서 어떻게 쓰이는지까지 알아보자 간단하게 자주 사용되는 순서도만 가져왔다. 이외의 것은 주로 사용되진 않지만 아래 링크에서 참고하길.. 2020. 10. 23.

이전 1 2 다음

728x90

하루 2시간

CS/알고리즘 및 자료구조33

티스토리툴바