유진's 공부로그

소수를 대량으로 빠르게 찾는 알고리즘이다. 소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수이다. 자연수 n이 소수인지 아닌지를 판별하기 위해서는 단순히 2부터 n-1까지 반복하면서 나누어 떨어지는지 확인하면 된다. 하나라도 나누어 떨어지는 수가 존재한다면 1과 자기자신을 제외한 수 중 약수를 갖게 되는 것이므로 n은 소수가 아니다. 위의 과정을 Python 코드로 표현하면, def is_prime_number(n): for i in range(2,n): # 2부터 n-1까지 if n % i == 0: # 하나라도 나누어 떨어지는 수가 있다면 return False # 소수가 아니다. return True 위의 방법은 직관적이지만 비효율적이라는 단점이 있다. 2부터 n-1까지 반복해야 하기..

DFS(Depth-First Search; 깊이우선탐색)와 BFS(Breadth-First Search; 너비우선탐색)는 그래프의 정점을 방문하는 그래프 탐색(Graph Search or Graph traversal; 그래프 운행) 방법의 큰 갈래이다. 코딩 테스트 시에는 DFS를 좀 더 많이 활용하는 듯하다. DFS는 스택이나 재귀로, BFS는 큐로 구현한다. python에서 그래프는 아래와 같이 보통 딕셔너리를 활용해서 인접 리스트로 구현하는 경우가 많다. graph = { 1: [2,3,4], 2: [5], 3: [5], 4: [], ... } DFS (깊이 우선 탐색) 일단 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 ..

Computer Vision에서 recognition task 시에 겪을 수 있는 challenges (출처: cs231n notes) 1. Viewpoint variation: 카메라 앵글에 따라 다르게 잡히는 객체 (얼굴의 정면, 측면 등) 2. Scale variation: 같은 객체여도 다른 사이즈로 이미지에 등장할 수 있음. 3. Deformation: 같은 객체여도 다른 모양으로 이미지 내에 표현될 수 있음. (서있어도, 앉아있어도, 누워있어도, 요가 자세를 취해도 사람은 사람이다) 4. Occlusion: 물체가 어느 부분 가려져도 같은 물체임을 판단할 수 있어야 함. (얼굴이 반 잘렸다거나, 갈대밭에 숨어있는 사람이어도 사람이라고 판단할 수 있어야 함) 5. Illumination cond..

이화여자대학교 OpenSWProject 수업을 정리한 글입니다. Mat C++ OpenCV에서 제공하는 n차원 dense array 클래스 실수 혹은 허수 값의 벡터와 행렬값을 저장하기 위함. (ex. 흑백, 컬러 이미지 등) How to allocate new array data Using Mat Constructors Mat::Mat() Mat::Mat(int rows, int cols, int type) Mat::Mat(Size size, int type) Mat::Mat(Size size, int type, const Scalar& s) Mat::Mat(int rows, int cols, int type, const Scalar& s) Using create() Mat::create(int row..

비트 연산자 |, &와 같은 연산자. bitwise하게 작용함으로써 비트 간의 연산을 진행함. (그냥 비트 간 연산이라 주로 이진수에 이용이 되는 듯함) ex. 1001&0110 = 0000 (False) 논리 연산자 or, and와 같은 연산자. or의 경우에는 하나라도 True이면 True를 리턴하고, and는 하나라도 False면 False를 리턴함. ex. 1001 and 0110 = 6 (무조건 뒤에 있는 것을 리턴하게 된다) 비트 연산자 vs 논리 연산자 in Python 같은 and이지만 비트 and는 비트 별로 진행되기 때문에 0000이므로 False로 나오고 논리 and는 뒤의 것을 리턴(파이썬에서 논리 연산자의 경우 마지막에 평가를 한 operand 값이 리턴된다.) 흔히 if 문을 쓸..

이진 탐색 (Binary Search) 이진탐색은 배열의 중앙값(median)을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 대략 반으로 줄여가며 재귀적으로 진행하는 알고리즘이다(물론 반복으로도 구현 가능하다). 정렬된 배열에서의 탐색에 적합한 알고리즘이다(연결리스트에서는 부적합함. 가운데 지점을 빠르게 찾을 수 없기 때문이다). 시간복잡도는 $O(\log_2{n})$ 으로 빠른 수행시간을 보여준다. 이진 탐색 알고리즘 1) 재귀 구현 2) 반복 구현 투 포인터를 어떻게 활용하느냐의 차이로 투 포인터의 응용이라고 볼 수도 있을 듯하다. 이진 탐색 in Python bisect 모듈에 구현이 되어 있으며, bisect_left를 사용하면 된다. 원래는 정렬된 ..

삽입정렬 삽입정렬이란 정렬되어 있는 앞 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정을 반복하며 정렬하는 알고리즘이다. 1) 삽입정렬 과정 초기 상태는 첫번째 원소를 정렬이 되어있다고 가정하고 시작함. 이후, 정렬된 부분 바로 뒷원소(a)와 정렬된 부분의 모든 원소를 비교하며 a의 제자리를 찾아 넣어줌. 예를 들어, 아래 그림에서의 2를 보면 1,3,5,8의 정렬된 부분 리스트와 비교를 시작하여 1보다 크고 3보다 작으므로 1과 3 사이에 삽입해주고, 탐색을 마친다. 2) 삽입정렬 알고리즘 이중 반복문 구조를 가진 알고리즘 1. 배열의 길이만큼 반복 2. key = 삽입할 원소 3. j는 배열의 오른쪽에서 왼쪽으로 이동한다. 4. 삽입할 원소를 정렬된 부분의 원소와 하나씩 비교하면서 한 칸씩 밀어냄..

스택(Stack) 스택은 후입선출(LIFO)로 처리되는 자료구조이다. 즉, 스택에 가장 마지막에 들어간 요소가 가장 처음으로 꺼내진다. Stack은 무엇인가가 쌓여있는 걸 지칭한다는 점을 생각해보면 가장 마지막에 쌓여진 것이 가장 처음으로 꺼내진다는 것의 개념은 쉽게 이해될 것이다. 스택은 흔히 연결리스트로 구현된다. 이 경우에 스택 선언을 위해 메모리 내의 연속된 공간을 할당할 필요가 없어지며, 실제로 스택 내의 요소 간 순서가 메모리 내의 물리적 순서와는 무관하게 될 것이다. 그러나 파이썬에서는 리스트가 스택으로 충분히 기능할 수 있기 때문에 연결리스트로 스택을 구현하지 않아도 된다. 스택의 주 연산은 삽입(push)와 제거(pop)이다. 삽입은 스택의 가장 마지막 자리에 요소가 추가되는 것이고, 제..

트라이 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 혹은 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조. 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 주로 문자열이 키인 경우가 많고, 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 트라이는 트리와 유사하지만, 우리가 주로 살펴본 이진 트리의 모습이 아닌 전형적인 다진 트리(m-ary Tree)의 형태를 띤다. 도식을 참고하면, 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. (이 부분은 어떻게 구현하냐의 차이인 것 ..

런너(Runner) 기법 연결 리스트 순회 시 2개의 포인터를 동시에 사용하는 기법. 한 포인터가 다른 포인터보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다. 연결리스트의 경우 중간 위치나 길이를 파악하는 데에 배열에 비해 상대적으로 복잡하다. (전체를 다 탐색해야 하므로 O(n)의 시간이 소요됨) 따라서 fast runner와 slow runner 간의 step을 2배 차이를 두는 식으로 (ex. fast, slow = 2,1) 지정한 후 fast runner가 리스트의 끝지점에 도착하면 slow는 정확히 리스트의 중간 지점에 도달하게 된다. 중간위치를 찾아냄으로써 값 비교 (palindrome linked list 문제), 뒤집기를 시도하는 등의 연결 리스트..