Study/Today_I_Learned
-
1. 이진 탐색이란 정렬된 데이터로부터 효과적으로 타겟을 찾을 수 있는 알고리즘입니다. 탐색할 자료를 둘로 나누어 찾는 데이터가 있는지 없는지 확인하기 때문에, 데이터가 정렬되어 있을 때 순차 탐색 sequential search보다 훨씬 빠르게 찾을 수 있습니다. 특정 범위 내에서 숫자를 추측하는 guessing game등을 할 때 필승할 수 있는 방법입니다. 이진 탐색은 분할 정복 알고리즘의 일종이기도 합니다. 1부터 71까지 랜덤하게 존재하는 숫자 배열로부터 7을 찾는 제일 효율적인 방법으로 시각화하면 아래 그림과 같습니다. 분할 정복 알고리즘 divide and conquer이란, 문제를 하나 또는 둘 이상으로 나누어 문제를 해결하는 알고리즘입니다. 나눠진 문제가 충분히 작은 상태에서 해결이 가능..
[알고리즘] 이진 탐색 Binary search1. 이진 탐색이란 정렬된 데이터로부터 효과적으로 타겟을 찾을 수 있는 알고리즘입니다. 탐색할 자료를 둘로 나누어 찾는 데이터가 있는지 없는지 확인하기 때문에, 데이터가 정렬되어 있을 때 순차 탐색 sequential search보다 훨씬 빠르게 찾을 수 있습니다. 특정 범위 내에서 숫자를 추측하는 guessing game등을 할 때 필승할 수 있는 방법입니다. 이진 탐색은 분할 정복 알고리즘의 일종이기도 합니다. 1부터 71까지 랜덤하게 존재하는 숫자 배열로부터 7을 찾는 제일 효율적인 방법으로 시각화하면 아래 그림과 같습니다. 분할 정복 알고리즘 divide and conquer이란, 문제를 하나 또는 둘 이상으로 나누어 문제를 해결하는 알고리즘입니다. 나눠진 문제가 충분히 작은 상태에서 해결이 가능..
2022.09.07 -
1. 그리디 알고리즘이란? 매순간 최적이라고 생각하는 경우를 선택하는 알고리즘입니다. 'greedy' 혹은 탐욕 이라고 이름이 붙은 이유는 전체적인 맥락에서의 최적과 각 순간(locally)에서 최적이라고 생각되는 경우가 다를 수도 있기 때문입니다. 그리디 알고리즘에서는 지나간 선택 중에서 혹시 더 좋은 경우의 수가 있었는지 돌아보지 않는다는 점이 동적 프로그래밍과 다른 점입니다. 2. 한계 '각 단계'에서의 최선을 선택하기 때문에 반드시 최적의 해를 구할 수 있는 것은 아닙니다. 따라서 overall optimal option 보다는 최적에 가장 가까운 값을 구하기 위해 사용하는 알고리즘입니다. 최적의 답을 구해주지 않는다면 왜 그리디 알고리즘을 활용할까요? 그 이유는 시간 절약 때문입니다. 더 적은 ..
[알고리즘] 탐욕 알고리즘 Greedy algorithm1. 그리디 알고리즘이란? 매순간 최적이라고 생각하는 경우를 선택하는 알고리즘입니다. 'greedy' 혹은 탐욕 이라고 이름이 붙은 이유는 전체적인 맥락에서의 최적과 각 순간(locally)에서 최적이라고 생각되는 경우가 다를 수도 있기 때문입니다. 그리디 알고리즘에서는 지나간 선택 중에서 혹시 더 좋은 경우의 수가 있었는지 돌아보지 않는다는 점이 동적 프로그래밍과 다른 점입니다. 2. 한계 '각 단계'에서의 최선을 선택하기 때문에 반드시 최적의 해를 구할 수 있는 것은 아닙니다. 따라서 overall optimal option 보다는 최적에 가장 가까운 값을 구하기 위해 사용하는 알고리즘입니다. 최적의 답을 구해주지 않는다면 왜 그리디 알고리즘을 활용할까요? 그 이유는 시간 절약 때문입니다. 더 적은 ..
2022.08.31 -
Hadoop&Hive 강의를 시작하기 전 AWS 에서 인스턴스를 생성하고, aws 서버에서의 shell programming을 위한 리눅스 기초에 대해 배웠습니다. 1. 기본 명령어 - 파일 생성 및 생성된 파일 확인하기 $ #optional $ sudo apt install tree #설치 시 tree 구조를 확인할 수 있음 $ touch hello.txt #파일 생성 $ echo #파일 내용 확인 $ ls #디렉토리 내 파일 리스트 확인 $ ls -l $ ls -a $ cat
[리눅스] basic - 명령어Hadoop&Hive 강의를 시작하기 전 AWS 에서 인스턴스를 생성하고, aws 서버에서의 shell programming을 위한 리눅스 기초에 대해 배웠습니다. 1. 기본 명령어 - 파일 생성 및 생성된 파일 확인하기 $ #optional $ sudo apt install tree #설치 시 tree 구조를 확인할 수 있음 $ touch hello.txt #파일 생성 $ echo #파일 내용 확인 $ ls #디렉토리 내 파일 리스트 확인 $ ls -l $ ls -a $ cat
2022.08.30 -
그래프에서 '탐색'이란 노드를 순회하는 것을 말합니다. 영어로는 graph traversal이라고 합니다. 노드의 탐색 알고리즘 중 가장 대표적인 두 가지는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)입니다. 아래 예제 그래프를 통해서 탐색 방식이 어떤지 자세히 알아보도록 하겠습니다. 그림은 트리처럼 생겼지만, 그래프 순회 시 cycle을 이루게 하는 edge가 추가되어도 순회하는 데에는 오류가 없을 것입니다. 1. 너비 우선 탐색 breadth-first search : 같은 레벨에 있는 노드, 즉 형제 노드들을 우선으로 순회 그래프의 구현은 딕셔너리로, 탐색 방법은 두 개의 리스트 자료구조를 활용할 수 있습니다. 그래프를 구현한 딕셔너리는 아래와 같이 key에 한 노드를, value에 해당 노..
[알고리즘] 그래프 Graph (2) - BFS&DFS그래프에서 '탐색'이란 노드를 순회하는 것을 말합니다. 영어로는 graph traversal이라고 합니다. 노드의 탐색 알고리즘 중 가장 대표적인 두 가지는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)입니다. 아래 예제 그래프를 통해서 탐색 방식이 어떤지 자세히 알아보도록 하겠습니다. 그림은 트리처럼 생겼지만, 그래프 순회 시 cycle을 이루게 하는 edge가 추가되어도 순회하는 데에는 오류가 없을 것입니다. 1. 너비 우선 탐색 breadth-first search : 같은 레벨에 있는 노드, 즉 형제 노드들을 우선으로 순회 그래프의 구현은 딕셔너리로, 탐색 방법은 두 개의 리스트 자료구조를 활용할 수 있습니다. 그래프를 구현한 딕셔너리는 아래와 같이 key에 한 노드를, value에 해당 노..
2022.08.23 -
그래프란? 실제 세계의 현상이나 사물을 노드 Node와 간선 Edge 로 표현하기 위해 사용하는 알고리즘으로, 네비게이션 길찾기, 게임 내 캐릭터 이동, 지식 그래프 등에 사용되며, 앞서 배웠던 트리 또한 그래프의 일종입니다. 우리에게 익숙한 그래프의 예시로는 쾨니히스베르크의 다리 문제가 있습니다. 1. 용어 노드 Node : 위치, 정점 vertex와 같음 간선 Edge : 위치 간의 관계를 표시한 선, 노드를 연결한 선, link 또는 branch 와 같 인접 정점 Adjacent vertex : 간선으로 직접 연결된 노드를 말함 차수 Degree : 방향이 없는 그래프에서 하나의 노드에 연결된 노드의 갯수 평균 차수 average degree: 노드 개수와 간선의 개수를 비교하기 위한 값 진입 차수..
[알고리즘] 그래프 Graph (1)그래프란? 실제 세계의 현상이나 사물을 노드 Node와 간선 Edge 로 표현하기 위해 사용하는 알고리즘으로, 네비게이션 길찾기, 게임 내 캐릭터 이동, 지식 그래프 등에 사용되며, 앞서 배웠던 트리 또한 그래프의 일종입니다. 우리에게 익숙한 그래프의 예시로는 쾨니히스베르크의 다리 문제가 있습니다. 1. 용어 노드 Node : 위치, 정점 vertex와 같음 간선 Edge : 위치 간의 관계를 표시한 선, 노드를 연결한 선, link 또는 branch 와 같 인접 정점 Adjacent vertex : 간선으로 직접 연결된 노드를 말함 차수 Degree : 방향이 없는 그래프에서 하나의 노드에 연결된 노드의 갯수 평균 차수 average degree: 노드 개수와 간선의 개수를 비교하기 위한 값 진입 차수..
2022.08.01 -
1. 특징 데이터에서 최댓값/최솟값을 빠르게 찾을 수 있는 완전 이진 트리 (complet binary tree) 완전 이진 트리란? 노드를 삽입할 때 최하단 왼쪽 노드부터 채워지는 트리 최댓값과 최솟값의 시간복잡도, 데이터 삭제 및 삽입의 시간복잡도는 $O(logn)$ (depth가 한 단계씩 내려가면서 체크횟수를 1/2로 줄여주기 때문) 값의 중복을 허용함 좌/우 노드 간 값의 크기는 상관 없음 2. 구조 최대 힙 Max heap / 최소 힙 Min heap 최대 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 (최소 힙은 반대 - 자식 노드보다 부모 노드의 값이 항상 같거나 더 작다) → 최댓값은 탐색할 필요도 없이 root node\ 3. 힙& 이진 탐색 트리의 비교 공통..
[자료구조] 힙 (Heap)1. 특징 데이터에서 최댓값/최솟값을 빠르게 찾을 수 있는 완전 이진 트리 (complet binary tree) 완전 이진 트리란? 노드를 삽입할 때 최하단 왼쪽 노드부터 채워지는 트리 최댓값과 최솟값의 시간복잡도, 데이터 삭제 및 삽입의 시간복잡도는 $O(logn)$ (depth가 한 단계씩 내려가면서 체크횟수를 1/2로 줄여주기 때문) 값의 중복을 허용함 좌/우 노드 간 값의 크기는 상관 없음 2. 구조 최대 힙 Max heap / 최소 힙 Min heap 최대 힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 (최소 힙은 반대 - 자식 노드보다 부모 노드의 값이 항상 같거나 더 작다) → 최댓값은 탐색할 필요도 없이 root node\ 3. 힙& 이진 탐색 트리의 비교 공통..
2022.07.27 -
current와 parent의 라임 속에서 허덕이는 자료구조입니다. 1. 용어 ▶ Node 노드: 트리에서 데이터를 저장하는 기본 요소 + 연결된 다른 노트에 대한 branch 정보 ▶ edge = branch: 노드를 연결하는 선 ▶ Root node: 트리의 가장 위에 있는 노드 ▶ Parent node: 위아래로 연결되어 있는 두 개의 노드 중 위에 있는 노드 ▶ Child node: 위아래로 연결되어 있는 두 개의 노드 중 아래에 있는 노드 ▶ Leaf Node (terminal node): childe node가 없는 노드 ▶ Level: Root node로부터 하위 branch로 연결된 노드의 길이 (root node: level 0) ▶ Depth 깊이: Root node로부터 노드까지 거쳐..
[자료구조] 트리 (tree)current와 parent의 라임 속에서 허덕이는 자료구조입니다. 1. 용어 ▶ Node 노드: 트리에서 데이터를 저장하는 기본 요소 + 연결된 다른 노트에 대한 branch 정보 ▶ edge = branch: 노드를 연결하는 선 ▶ Root node: 트리의 가장 위에 있는 노드 ▶ Parent node: 위아래로 연결되어 있는 두 개의 노드 중 위에 있는 노드 ▶ Child node: 위아래로 연결되어 있는 두 개의 노드 중 아래에 있는 노드 ▶ Leaf Node (terminal node): childe node가 없는 노드 ▶ Level: Root node로부터 하위 branch로 연결된 노드의 길이 (root node: level 0) ▶ Depth 깊이: Root node로부터 노드까지 거쳐..
2022.07.26 -
처음 딥러닝 개론에서 CNN에 대한 개념을 들은 이후, 여러 강의에서 CNN에 대한 언급이 많고 그 배경지식을 요구하는 내용이 많아 CNN에 대한 개념을 정확히 짚어놓아야겠다는 생각이 들어 따로 포스팅합니다. 1. CNN이란? Computer vision 분야에서 널리 사용되는 딥러닝 신경망 모델입니다. convolutional layer와 pooling layer를 통해 이미지를 픽셀 단위로 받아들여 그 특징들을 파악합니다. 그림에서 C1 으로 넘어갈 때 첫 번째 convolutional layer에서 padding이 적용되지 않은 $ n \times n \times 6 $ 인 filter가 사용되었음을 확인할 수 있습니다. 이게 대체 무슨말인지 용어를 같이 살펴보겠습니다. 2. 용어 ▶Convolut..
[딥러닝] CNN처음 딥러닝 개론에서 CNN에 대한 개념을 들은 이후, 여러 강의에서 CNN에 대한 언급이 많고 그 배경지식을 요구하는 내용이 많아 CNN에 대한 개념을 정확히 짚어놓아야겠다는 생각이 들어 따로 포스팅합니다. 1. CNN이란? Computer vision 분야에서 널리 사용되는 딥러닝 신경망 모델입니다. convolutional layer와 pooling layer를 통해 이미지를 픽셀 단위로 받아들여 그 특징들을 파악합니다. 그림에서 C1 으로 넘어갈 때 첫 번째 convolutional layer에서 padding이 적용되지 않은 $ n \times n \times 6 $ 인 filter가 사용되었음을 확인할 수 있습니다. 이게 대체 무슨말인지 용어를 같이 살펴보겠습니다. 2. 용어 ▶Convolut..
2022.07.25