조용하지않는개발Blog

알고리즘을 공부하다 기본으로 배우게 되는 순열과 조합을 간단하게 이야기하고 코드 및 정리를 하려고 적는다. 이론 순열 : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다 조합 : 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관없게 선택하는 혹은 나열하는 것을 조합(Combination)이라고 한다. 두개의 차이점은 순서에 상관이 있냐 없냐 정도이다. 순열은 nPr 조합은 nCr 이렇게 표현하며 n이 4이고 r이 2일경우 순열은 nPr -> 4P2 -> 4*3*2*1 / 2*1 = 4*3 =12가 된다. 조합은 nCr ->4C2 -> 4*3 / 2 = 6 이 된다. 이론은 간단하게 이야기 하고 코드로 짜면 아래와 같이 된..

알고리즘을 풀 다보면 간혹 나오는 문제중에 하나인 소수 찾기 문제가 존재 한다. 소수란? 1과 자기자신의 수만을 약수로 가지고 있는 수를 소수라고 한다. 간단하게 소수를 찾는다면 2를 뽑았다면 2의 배수를 다 제외 하고 3의 뽑았다면 3의 배수를 다 제외하는 형식으로 찾을 수 있다. 하지만 간단하게 구현한 만큼 O(n)이여서 시간초과가 나는 경우가 많이 있을 것이다. -> 이부분을 노리고 문제를 만들었을 확률이 크다. 그렇다면 O(n)보다 빠르게 소수를 만들어야하는 문제인 것! 그때 사용하는 것이 에라토스테네스의 체 이다. 나의 설명보다는 위키백과의 설명이 더 자세하게 적혀 있어서 가져왔다.. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다...

그래프의 표현 그래프 표현하기 인접리스트 표현 (Adjacency list representation) 인접행렬 표현 (Adjacenry-matrix representation) 인접리스트 표현 (Adjacency list representation) 점점 하나당 리스트 하나인 크기가 v인 배열 정점 하나에 인접한 모든 정점을 리스트에 저장 비방향성 그래프에서는 방향성 그래프로 변환해서 저장, 단점으로는 방향성 그래프에 비해 2배의 공간이 필요 인접행렬 표현 (Adjacenry-matrix representation) 크기가 v*x인 행렬 두 정점 i와 j를 잇는 간선이 있다면 행렬의 (i,j)는 1, 아니면 0 v의 제곱개의 공간 필요 무방향성은 양방향으로 간선이 존재하므로 하위 삼각행렬이 상위 삼각 ..

1. 그래프 기초 그래프 G 그래프G는 (v,e)의 쌍이다. 이때 v는 정점(vertex)의 집합(set)이고 e는 간선(edge)의 집합이다. 정점은 독립된 개체(stand-alone object)로 동그라미로 표현한다. 간선은 두 정점을 잇는 개체로 선이나 화살표가 있는 선으로 표현한다. 방향성 그래프(Directed graph) 방향성이 있는 간선을 가지고 있는 그래프 간선이 방향을 가지기 때문에 화살표가 있는 선(arrows)을 사용한다. 각 간선은 한 정점을 떠나서 한 정점으로 들어간다. 일반적으로, 각 정점은 숫자나 이름으로 구분한다. 각 간선은 간선이 떠나고 도착하는 정점의 쌍을 순서대로 적은 것으로 구분한다. 방향성 그래프에서 두 개의 정점에 대해 최대 2개의 간선이 존재한다. 무방향성 그..

학습목표 1. open Addressing 방법에 대해 이해하고 장단점을 파악 할 수 있습니다. 2. Linear probing, Quadratic Probing, Double hashing 방법에 대해 이해할 수 있습니다. 1. Open-Addressing 개요 오픈 어드레싱(open Addressing) 오픈 어드레싱이란? Collision을 피하기 위한 다른 방법으로 key를 hash table에 직접 저장 오픈 어드래싱의 장점 포인터를 사용하지 않아도 되므로 구현이 간편하다. 포인터를 사용하지 않으므로 추가 메모리 공간 사용이 가능하다. 공간의 충돌 문제가 줄어들며 자료 검색이 미세하게 빨라진다. 선형 프로빙(Linear probing) 특정 조건이 주어졌을때 선형 프로빙으로 key값을 테이블에 ..

학습목표 1. Direct-address Tables에 대해 이해하고 장단점을 파악할 수 있다. 2. Hash Tables를 이해하고 장단점을 파악할 수 있습니다. 1. Direct-address Tables Direct-address Tables 크기가 U인 테이블 T를 생성하고 key k를 slot k에 저장하는 방식 단, 중복되는 key는 없다고 가정 Direct-address tables의 주요 함수 Direct_Addtess_search(T,k) return T[k] Direct_Addtess_insert(T,x) T[x.key] = x Direct_Addtess_delete(T,x) T[x.key] = nil 각각의 수행 시간은 O(1) Direct-addressing의 공간 복잡도 Θ(U) ..

오늘의 핵심 내용 비교 정렬의 하한값을 이해하기 비교 정렬을 하지 않는 계수정렬과 기수정렬을 이해하고 선형 수행시간을 확인하기 1. 비교 정렬의 하한 값 비교 정렬을 이용하는 정렬 지금까지 소개한 정렬 알고리즘은 비교연산으로 정렬을 하였다. 비교연산은 두 개의 원소의 관계를 다음 중 하나로 판단하는 것이다. 비교 정렬의 하한값(Lower bounds) 비교 연산으로 정렬방법은 아무리 빨라도 nlogn보다 느리다. 2. 계수 정렬 알고리즘 계수 정렬 계수를 이용하여 정렬 - 실제 숫자를 세는 방법으로 숫자가 몇 개인지를 기록한다. x라는 입력은 x보다 작은 원소의 개수가 i-1개라면 정렬 후에 i 번째에 위치해야한다. x보다 작은 원소의 개수는 원소의 개수를 세어서 확인할 수 있다. 계수 정렬의 특징 입력..

퀵(Quick) 정렬 알고리즘 퀵 정렬 - Divide - and - Conquer paradigm을 사용 partition을 이용 - Partitioning을 이용한 정렬 방법 파티션이라고 하는 것은 pivot element라고 하는 것을 통해 반으로 나누어 그 기준을 통해 작은 것을 왼쪽으로 큰 것은 오른쪽으로 이동시키는 것을 반복하는 것 - 퀵 정렬의 pseudo code QUICKSORT(A,p,r) if p

힙(heap) 정렬 알고리즘 힙 구조 - 힙의 형태 완전 이진 트리에 가까운 형태 이진트리는 각 노드의 자식수가 2이하인 경우 완전 이진트리는 Root 노드 부터 Leaf 노드까지 빠짐없이 채워져 있는 트리 - 최대힙 특성 A[PARENT(i)]>=A[i] 부모 노드의 값은 항상 자식 노드의 값보다 크다. 따라서 전체 트리의 Root 노드값이 가장 크다. 또한 각 하위 트리 구조의 Root 노드가 가장 큰 값을 가진다. - 최소힙 특성 A[PARENT(i)]

합병(Merge) 정렬 알고리즘 - 알고리즘 설명 합병정렬은 무엇인가? 합병을 이용한 정렬 알고리즘 무엇을 합병을 할것인가? 두 개의 정렬된 배열이 주어졌을때, 정렬된 하나의 배열로 합병 -> 위 예시 처럼 정렬된 리스트가 두개를 정렬하기 위해서는 맨 왼쪽에 있는 값만을 비교하여 정렬할수있다. 합병 정렬을 이용했을 때, 수행시간은 어떻게 될까? O(nlogn) 합병 정렬은 어떻게 풀까? - A divide and Conquer approach : 크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러개의 문제로 바꾸어서 푸는 방법 * Divide : n keys를 두개의 n/2 keys로 나눈다. * Conquer : 합병정렬을 사용하여 두개의 배열을 정렬한다. * Combine : 두 개..