전체 글

오늘은 스택과 큐 자료 구조를 복습한다.스택스택은 LIFO(후입선출) 구조의 자료를 말한다.사용 예시로 이전에 재귀에서 살펴본 시스템 스택이나 DFS을 생각할 수 있다. 구현은 3가지 정도의 방법으로 해볼수 있다.- 리스트를 이용해 전역변수로 구현하는 방법- 구조체리스트를 통해서 마지막 인덱스와 리스트를 함께- allocation(malloc, realloc...) 을 활용한 동적 스택 생성 스택문제의 대표 예시는 다음과 같다.- 괄호 검사 알고리즘- 전위, 중위, 후위 표기식큐큐는 FIFO(선입선출) 구조의 자료를 말한다.사용 예시로 BFS, CPU 스케줄링을 생각할 수 있다 구현은 선형 큐 혹은 원형 큐의 형태로 만들게 된다.퀴즈스택과 큐의 차이점을 설명하고, 각 자료구조가 실제 문제 해결에 어떻게 ..

알고리즘의 점근적 효율성입력의 크기가 커질수록 알고리즘의 효율성을 따지는 것은 매우 중요한 문제다.오늘은 알고리즘의 효율성을 점근적인 평가방식에 대해서 이야기 한다. 알고리즘의 실행 시간알고리즘이 실행완료되는데에 걸리는 실행시간은 입력의 크기에 따라서 달라진다.특히 알고리즘이 돌아가는 하드웨어에 따라, 운영 환경에 따라서 달라지는 부분이다.따라서 실제적인 시간을 따지는 것은 측정이 정확하지 않다. 이런 이유로 우리는 기본 연산(산술/ 비교...)이 몇번 실행되는지를 통해서 측정하게 된다.다만 이 경우 또한 입력 데이터에 따라서 달라진다. 예를 들어서 정렬 알고리즘의 기본연산 횟수를 세어보려고 한다.극단적으로 생각해서, 입력으로 들어오는 값이 이미 정렬된 채로 들어오는 경우가 있을 수 있다.반대로 정렬과 ..

알고리즘 문제를 풀면서 가장 기본적이고, 많이 이용하게 되는 반복과 재귀에 대해서 알아보자.반복우리가 보통 사용하는 while문이나 for문등을 통해서 명령의 반복적인 실행을 통해 로직을 구성하고, 해결하는 것을 말한다.재귀와 비교했을때 일반적으로는 속도가 더 빠르고, 스텍 메모리를 사용하지 않는다는 장점이 있다.다만 무한루프가 생기는 경우에 CPU사이클이 반복적으로 사용된다는 문제가 발생한다.재귀재귀는 함수 자기자신을 다시 호출하여 수행하는 형태의 로직을 말한다.즉, 큰 문제를 풀기 위해서 동일한 구조의 작은 문제로 분할하여 해결한다.반복문보다는 속도가 느릴 수 있고(알고리즘마다 다를 수 있음), 재귀 호출시에 변수나, 리턴값, 위치 등이 스택메모리에 저장되게 된다. 따라서 무한 재귀가 발생하면 스택 ..

오늘부터 매주 다년간 학교에서 공부한 내용을 짧고 간결하게 훑어보는 시간을 가지기로 했다!! 따라서 이 포스팅에는 어떤 공부를 했는지에 대한 개요와 관련 포스팅url을 업로드 할 예정이다.  소프트웨어의 기초 (자료구조+알고리즘)재귀와 반복 https://he-kate1130.tistory.com/114알고리즘의 성능 https://he-kate1130.tistory.com/115스택 / 큐 https://he-kate1130.tistory.com/116우선순위 큐정렬색인과 이진검색트리균형 검색 트리해시 테이블그래프

Graph 알고리즘가장 기본이 되는 그래프 알고리즘인 DFS와 BFS에 대한 이야기는 아래의 링크를 통해 확인할 수 있다.https://he-kate1130.tistory.com/73 [Daira i Noor] Python Algorithm (2) - Brute Force Search오늘은 파이썬을 통해 완전 탐색을 하는 방법에 대해 알아본다.완전 탐색의 방법으로 단순한 brute force와, 순열의 활용, BFS/DFSk에 대해서 알아본다. Brute Forcefor문과 if문을 활용하여 모든 가능한he-kate1130.tistory.com 오늘은 Minimum spanning tree에 대한 이야기를 한다. Minimum spanning tree (MST)MST는 한국어로 최소 신장 트리라 한다. ..

Background논문을 읽기 전에 한번 되짚어보기Gradient DescentBatch Gradient Descent일반적으로 그냥 경사하강법이라 하면 이걸 떠올린다.iteration한번에 전체 training dataset을 사용하여서 gradient를 계산한다.세타 : 모델 파라미터알파: learning rateN: training dataset 크기l : loss func이름에 batch가 들어가서 살짝 혼동될 수 있는데, 그냥 batch를 total trainig dataset으로 생각하면 된다.전체 dataset을 쓰기 때문에 convergence가 안정적이라는 장점이 있다. 다만 메모리를 많이 쓰고, lacal optima로 수렴되는 경우에 빠져나오기 어렵다.Stochastic Gradien..

Word Vectors어떤 문장이 주어졌을때, 문장의 어떤 부분이 문장의 의미를 더 중요하게 표현하는지를 어떻게 알 수 있을까?사람의 언어라는 것은 다양한 의미와 뉘앙스를 가지고 있기 때문에, 언어의 정보를 잘 포함하게 표현하고, 이를 다루는것은 정말 어려운 일이다.one hot vectorword를 다루는 가장 쉽고 기본적인 방법은 단어를 서로 의존하지 않는 개별의 개체로 생각하는 것이다.즉, 단어를 one hot vector를 통해서 나타낼 수 있다. 예를 들어서 finite set {coffee, cafe, tea}의 개별 단어를 다음처럼 1-hot vector로 표현한다.전통적딘 NLP에서 단어를 이와 같은 형태로 표현하여 사용한다. 이렇게 표현하게 되면, 두 단어 사이의 L1, L2 distan..

CNNCNN은 conv layer와 pooling layer를 번갈아 배치하는 구조로 형성되어있다. 이를 통해서 입력되는 이미지의 특징을 추출하고 , 이후에 FC layer를 통해서 분류작업을 수행한다.하지만 이런 CNN 에는 몇가지 한계가 있다.비선형성의 제한Convolution filter를 사용하므로 입력 데이터에 대해서 로컬한 선형 연산을 수행하게 된다. 따라서 이 부분에서는 비선형성이 떨어진다는 문제가 있다. 즉, 이로 인해서 복자한 데이터에 대한 패턴을 캡쳐하는것에 한계가 있다.완전 연결 레이어 오버피팅FC layer는 많은 파라미터가 필요한 layer이다. 따라서 이를 통해서 오버피팅이 발생하게 된다는 한계가 있다.공간적 정보의 손실또한 FC layer에서 vector형태는 이미지의 공간적인..