Fundamental

문제를 쪼개서 각각 따로 처리한 다음 결과를 합쳐나가는 방법. 배열의 길이가 1이면 정렬이 끝난 것이다. 아니라면 배열을 반으로 나눠서 왼쪽과 오른쪽을 따로 정렬한다. 둘 다 정렬이 끝나면 merge라는 작업을 통해 배열을 합쳐준다. 이미 sorted인 2개의 서브 배열 이 2개의 서브 배열의 merge된, 병합된 하나의 결과를 담을 배열 와 같이 3개의 배열로 이루어져 있다. 위의 배열과 아래의 배열이 합쳐지는데 sorted를 읽지 않도록 합치는 것이다. 배열이 3개인만큼 포인터 역시 3개다. 윗쪽 배열을 A 아래쪽 배열을 B라고

sorted된 배열에 원소를 추가할때 sorted가 깨지지 않게 원소의 위치를 찾아서 넣는 알고리즘이 insertion sort다. 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다. 들어갈 위치를 선택하는데 N번, 선택하는 횟수로 N번이지만 선택정렬보다 약간 빠르다. 선택정렬과 똑같이 O(N^2) 의 시간 복잡도를 가진다. 가장 앞 인덱스의 원소가 정렬되어있다고 가정했을때 바로 뒷부분의 인덱스부터 올바른 위치로 insertion하는 알고리즘이다. temp변수를 두고 원소를 하나씩 swap하는 방법은 비용이 크다. 그래서 temp변수

RDB는 오랜시간 대표적인 DBMS의 자리를 지켜왔다. 그러나 소셜서비스의 규모가 커짐에 따라 비정형 데이터를 이용하고자 하는 빅데이터 개념과 인프라 에코시스템도 클라우드 컴퓨팅의 바람이 불어오면서 기존의 RDB가 가진 단점들이 부각되기 시작했다. RDB를 유지하면서 스케일업 하는것은 한계가 있기 때문이다. 시대적 흐름이 NoSQL의 등장을 이끌었다. RDB의 특징인 ACID 일부를 포기 하고 스키마를 없앴다. 이로인해 비정형 데이터를 신속하게 저장하고 처리하는데 적합했다. 정합성을 포기하며 분산 처리로 인해 뛰어난 확장성 또한 장

Vertex를 연결하는 edge에 순서가 없는 pair로 표현되는 edge들로 이루어져있다. {v1,v2}를 edge라고 표현한다. 예를 들어 v1,v2,v3,v4,v5,v6,v7,v8,v9의 vertex가 있을 때 {v1,v2},{v3,v5},{v4,v7},{v4,v7}의 edge가 있으면 4개의 edge가 있다고 표현한다. 방향이 없기 때문에 v1에서 v2로 가는 edge, v2에서 v1로 가는 edge모두 있다고 본다. 자기 자신에서 자기 자신으로 가는 edge는 없다. V개의 vertext가 있는 방향이 없는 그래프에서 최대

정렬의 기준이 되는 가중치를 key 필드로 임의 지정할 수 있다. 원소가 이터러블일때 모두 사용가능하다. 가중치를 자유롭게 지정할 수 있다. 소수 구하기 이진트리기반의 heapq와 연결리스트 기반의 데크는 원소를 추가하고 삭제하는 것이 배열보다 비용이 적다. heqpq : 우선순위 큐 deque : 양 끝단에서 데이터를 넣고 뺄 수 있는 큐

2월 4일 목요일 알고리즘 스터디에서 진행한 프로그래머스 문제 풀이다. 브레인스토밍과 채점이 끝나고 다른사람의 코드 보기를 보면 파이써닉한 코드가 많은데 그렇게까지 해야 할 필요가 있나 싶다.. 같은 카테고리로 dictionary를 만든다 dictionary key의 길이를 구한다 (총 카테고리의 개수) n개의 카테고리중 1개만 입는 경우를 구한다 → 각 카테고리의 원소 개수를 전부 합한다. 2~n개 까지는 combinations 함수를 통해 구한다 → 각 카테고리 원소 개수를 곱한다. 3과 4에서 구한 경우의 수를 모두 합한다.

교집합 슬라이딩 윈도우 참가자와 완주자의 명단에서 완주하지 못한 참가자를 가져온다. 두 리스트의 교집합을 증명하는 과정에서 완주자와 비교해 참가자를 반환한다 (완주하지 못한 참가자) 소스코드 리스트 내 원소에 대해 슬라이딩 윈도우로 비교하고 요구조건에 따라 boolean을 반환한다. 소스코드 첫번째 시도 : dictionary를 만든 후 set으로 원소 생성 → 실패 두번째 시도 : list 원소를 단순 조합하여 set으로 요구조건 원소 생성 → 테스트 케이스는 통과하지만 효율성에서 모두 탈락 세번째 시도 : 순서에 상관없는 조합(

해시함수는 메시지 길이가 길던, 짧던 항상 동일한 길이의 메시지를 만들어내는 함수다. 메시지를 일정한 길이의 블록으로 분할 후 해시 함수에 입력한다. 짧고 일정한 길이의 메시지 다이제스트 (160,256,512bit)생성 대표적인 Hash함수 : MD5, SHA-256, SHA-512 어떤 크기의 데이터 블록이든지 적용 가능해야 한다. 일방향성을 만족해야한다 = 메시지 다이제스트로부터 원래의 메시지를 만들어낼 수 없어야 한다. → 복호화 불가능 강한 충돌 회피성 : 다른 데이터에 의해 생성된 메시지 다이제스트는 동일하면 안된다. 해