Big Tree

투 포인터(Two Pointers) 알고리즘은 주로 배열이나 리스트와 같은 순차적인 자료구조에서 특정 범위를 탐색하거나 부분합, 부분 문자열 등을 찾을 때 유용한 알고리즘이다. 투 포인터 알고리즘은 이름 그대로, 두 개의 포인터를 이용하여 문제를 해결한다. 이 알고리즘은 보통 정렬된 배열에서 찾는 문제에서 유용하게 사용한다. 1. 배열이나 리스트에서 각각 왼쪽 포인터(left)와 오른쪽 포인터(right)를 정한다. 2. right를 체크 대상 추가를 위해 +1 씩한다. 3. left를 체크 대상 해제를 위해 +1 씩한다. 4. 반복해서 두 포인터의 위치를 조정하며 문제를 해결한다. 보통 이 알고리즘은 두 포인터의 위치를 이동시키는 규칙을 설정하여 사용한다. 예를 들어, 부분합을 구하는 문제에서는 왼쪽 ..

우선순위 큐 우선순위 큐(Priority Queue)는 데이터를 저장하고, 꺼내올 때 우선순위에 따라 처리하는 자료구조이다. 일반적으로는 힙(Heap)이라는 자료구조를 이용하여 구현된다. (우선순위 큐 != 힙) 우선순위 큐는 일반 큐와 달리, 데이터가 들어올 때마다 우선순위를 비교하여 적절한 위치에 삽입하거나, 이미 삽입된 데이터 중 가장 우선순위가 높은 데이터를 먼저 꺼내오는 동작을 수행한다. 우선순위 큐는 다양한 분야에서 사용됩니다. 예를 들어, 다익스트라 알고리즘과 같은 최단 경로 알고리즘에서는 우선순위 큐를 이용하여 다음으로 방문할 노드를 선택한다. 또한, 운영 체제에서는 프로세스 스케줄링을 위해 우선순위 큐를 사용한다. 우선순위 큐는 일반적으로 삽입과 삭제 연산의 시간복잡도가 O(log n)입..

그리디 알고리즘(Greedy Algorithm)은 최적해를 구하는데 사용되는 근시안적인 방법론이다. 즉, 현재 상황에서 가장 최적인 선택을 하여 결과적으로 최적해를 도출하는 방법. 최적화 문제를 그리디 알고리즘으로 풀 수 있는 부분 문제들로 나눈다. 각 부분 문제에 대한 최적해를 구한다. 각 부분 문제의 최적해를 결합하여 전체 문제의 최적해를 구한다. 하지만, 그리디 알고리즘이 항상 최적해를 도출하는 것은 아니다. 때로는 그리디 알고리즘이 최적해를 보장하지 않는 경우도 있다. 그리디 알고리즘이 근시안적인 방법론이라고 말하는 것은, 현재 순간에서만 최적인 선택을 하기 때문에 전체적인 상황에서 최적해가 아닐 수도 있다는 것을 의미한다. 그러나, 그리디 알고리즘이 결과적으로 최적해가 될 수 있는 이유는 부분 ..

여러 프로세스를 사용하면, 같은 메모리 공간을 건드리는 경우도 있을텐데 그러면 문제가 발생할 것이다. 가령 남의 메모리 공간을 지워버린다거나.. 수정한다거나.. 코드를 캡슐화하는 것과 조금 비슷한 고민이라고 생각한다. 즉 Q. 어떻게 메인 메모리를 프로세스간에 공유할 수 있을까? Q. 어떻게 각각의 메모리들을 보호할 수 있을까? 이와같은 물음에 대해 우리는 가상 메모리 개념을 도입한다. 가상 메모리는 physical memory의 주소값을 갖는 형태로, 프로세스별로 각각 독립된 가상 메모리 공간을 가지면 physical memory에 가상 메모리에 담긴 주소값으로 접근하는 것이다. Virtual Memory -> Physical Memery 로의 전환은 MMU(Memory-Management-Unit)이..

"값이 싸면서 처리속도가 빠른 메모리는 없다" SRAM을 활용하는 캐시메모리는 값이 비싸지만 속도가 빠르다 > 0.5ns - 0.2ns per $500 - $1000 DRAM을 활용하는 메인메모리는 값이 싸지만 속도가 느리다 > 50ns - 70ns per $10 - $20 비싼 재료를 쓰면 맛은 좋지만 가격이 많이 나가는 원리랄까.. 이러한 메모리 처리속도의 문제는 컴퓨터 동작에서 문제를 일으킨다. 가령 CPU가 데이터 내놔!! 라고 소리지르는데, 램은 처~언~처~언히 주는 경우, 지연(latency)가 발생한다. 따라서 램보다 빠른놈을 중간에 둬서(캐시) 연산을 하면, 많이 쓰는 놈은 중간놈(캐시)에게 두면 좀 편안해진다. CPU < 캐시 < 메인메모리(RAM) < HDD 순서로 두는 것이다. CPU..

*공부하면서 정리한 부분이라 잘못된 부분이 있을 수도 있습니다. 암호화 방식은 (1)대칭키 암호화 방식과 (2)공개키(비대칭키) 암호화 방식이 있다. 대칭키 암호화 방식 대칭키 암호화 방식은 암호화, 복호화를 오직 한 가지 키값으로 진행하는 방식으로, 해당 키값이 해커에 의해 노출되면 복호화가 된다는 단점이 있다. 예) A가 B에게 비밀번호를 보내려고 한다. A가 특정 키값으로 비밀번호 텍스트를 암호화를 하여 변형시킨다. (키값+비밀번호) 데이터를 함께 B에게 보낸다. 앗! 근데 사실 C가 A와 B 사이 네트워크를 감시하다가 해당 내용을 봤다. 복호화 키값을 알고, 비밀번호 텍스트도 알고 있으니 그냥 알고리즘 방식에 따라 복호화를 진행하면 원래 내용이 보인다. 이런 방식의 공격자(C)를 막기 위해서, 키..

웹 개발 中 클라이언트는 HTTP 를 통해 서버에 해당 웹문서를 요청하고 서버는 해당하는 요청에 따라 문서를 응답하는 형식을 기본으로 한다. 이것이 우리가 통용하고 있는 웹서비스의 구조이다. 요청과 응답, 이 두가지 개념을 갖고 그 위에 다양한 기술들이 쓰이는 것 뿐. 쿠키(Cookie) "하루동안 이 창을 열지 않음" 과 같은 것을 본 적이 있을 것이다. 여기에 체크를 하게 되면 클라이언트의 쿠키에 해당 값을 False 로 지정할 수 있도록 처리되는 것이다. Set-Cookie : eventPopup = 'False' 처럼 말이다. (그냥 이해하기 쉬운 예시임. 이렇게 안할듯) 나중에 이런 것들이 쌓여서 Cookie 값들을 만들어내고 웹서버에 요청을 할때, 같이 전달해서 수고를 더는 것이다. "네가 필..

추천 엔진을 구현하며, ALS(Alternating Least Sqaure) 를 기반으로 Matrix Factorication 모델을 구현하고 있다. 그 중, 평가를 위한 함수인 MSE(Mean Sqaured Error) 를 구현하며 이해한 부분을 바탕으로 간단 정리한다. 평균제곱오차(MSE)는 Regression 과 같은 실수 기반의 결과에 대한 오차를 판별하는 방식이다. Classification 과 같은 경우, 맞다/아니다가 판별이 가능하지만, 주식 가격 예측과 같은 수치 판단은 애매한 경우가 많다. 예시로, 실제 값이 100,000 원인 주식 가격을 내가 만든 모델이 95,000원 이라고 판별한다면, 이 모델이 얼마나 잘 판단한 것인지 애매하다. 따라서 실제 값과 예측값의 차이를 기준으로 오차를 ..

추천 알고리즘이 대세가 된 시점이다. 유저들은 내가 원하고 좋아하는 아이템을 추천 받는 것을 좋아하며 각종 기업들은 소비자의 니즈를 파악하여 결제까지 연결시키고자 한다. 그 중심에 있는 것이 바로 추천 알고리즘 (Recommendation Algorithm) 이다. 아마도 가장 유명한 추천 알고리즘을 이용한 기업은 넷플릭스나 유튜브가 아닐까 싶다. 내가 본 영상들, 얼마나 오래 봤는지, 추천해줬던 영상들 또한 클릭 했는지.. 등 다양한 데이터를 이용하여 유저들에게 추천하고 계속 서비스에 머무르게 유도한다. 이번에는 이 알고리즘은 어떤 원리로 구현하는지 대표적인 알고리즘으로 정리해보고자 한다. Collaborative Filtering 협업 필터링은 단어에서 유추할 수 있듯이, 다른 사용자들과의 협업을 통..

You Only Look Once: Unified, Real-Time Object Detection Joseph Redmon, Santosh Divvala, Ross Girshick, Ali Farhadi (Submitted on 8 Jun 2015 (v1), last revised 9 May 2016 (this version, v5)) 위 논문 내용에 대한 이해 및 서치를 바탕으로 개인적인 정리 내용입니다. 가끔 잘못 이해한 내용이 있을 수도. 기존의 컴퓨터 비젼 분야의 객체 인식 (Image Detection) 은 두 가지 단계를 거쳤다. YOLO 이전에 주류 객체 인식 알고리즘인 R-CNN 을 예시로 들어보자. 이미지 내의 특정 영역을 먼저 캐치한 후 (Region Proposal), 이에 대한 분..