Grace's Tech Blog

동적계획법이란, 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 것이다. 즉, '나'를 해결함으로써 더 큰 '나'를 해결하는 것 => '나'가 두 번 나오는 것으로 봐서 딱 떠오르는게 있다면?!! 바로 재귀호출! 즉, 동적계획법은 재귀호출을 사용한다. 동적계획법이 어떤 식으로 활용 될 수 있는지 예제 문제를 통해 살펴보자. 예) 피보나치 수 구하기 - 피보나치 수열의 n번째 수를 구하시오 풀이 1. 먼저 피보나치 수열의 특성 상 '재귀만 사용하여' 풀 수 있다. def getFibo(n): if n < 2 : return n else: return getFibo(n-1) + getFibo(n-2) 그런데 이 해결법이 가장 효과적일까? 아니다. 이 방법은 이전에 한 번 계산한 적이 있던 것이 다시..

개념 Hash: 임의 값을 고정 길이로 변환하는 것 Slot: 한 개의 데이터를 저장할 수 있는 공간 Hashing Function: key에 대해 연산을 이용해서 Hash value(Hash address)를 알 수 있는데 이 Hash value(Hash address)가 key에 대한 value가 저장된 공간(slot)과 연결되어 있다. Hash Table: key에 대한 Hash value(Hash address)에 연결된 공간(slot)에 value를 저장하는 데이터 구조이며, 키 값의 연산에 의해 직접 접근이 가능한 데이터 공간이다. (그래서 key를 통해 데이터를 바로 받아올 수 있으므로 속도가 획기적으로 빨라진다.) 장점 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.) 키에 대한 ..

소수(Prime Number)란 약수가 1과 자기자신 뿐인 수이다. 주의해야 할 것은 1은 소수가 아니며, 흔히 짝수라서 소수가 아닐꺼라고 생각할 수도(?) 있지만 2는 소수이다. 구현 소수에 관한 문제는 2가지로 생각해 볼 수 있다. 1) 특정 수(n)가 소수인지/아닌지 판별해야 할 경우 이때는 n의 약수 가 1과 자기 자신(n) 뿐이면 소수, 아니면 소수가 아니라는 정의를 이용하는게 좋다. 다시 말해, 1~n 중 1, n을 제외한 2~(n-1) 중에서 하나라도 나누어 떨어지는 것이 있으면 소수가 아니다. / 하나도 나누어 떨어지지 않으면 소수이다. 로 판단 할 수 있는 것이다. ※ 하지만 그냥 2~(n-1)을 모두 탐색하면서 검사하려면 시간복잡도가 O(n)으로 너무 크다.. 고 생각된다. 이를 줄일 ..

유클리드 호제법이란 주어진 두 수 사이에 최대공약수를 구하기 위한 알고리즘이다. 이를 통해 최대공약수를 구하면 최소공배수 역시 쉽게 구할 수 있다. 두 수 A, B가 있다고 하자. 그리고 r은 A를 B로 나눈 나머지(A%B) 라고 하자. 유클리드 호제법은 A, B, r 세 수를 가지고두 단계를 반복하는 것이다. step1. A를 B로 나누어 r을 만든다. step2. r이 0이면 이 때의 B가 최대공약수이고, r이 0이 아니면 B의 값은 A가, r의 값은 B가 되어 step1~step2를 반복한다. (언제까지?? r이 0이 되어서 B라는 최대공약수를 구할 때까지) 구현 위의 방법을 구현하는 방식은 2가지가 있다. 1) 반복문을 이용한 방법 while(1){ let r = A%B; if(r===0){ re..

1. 그래프 순회(탐색) 그래프란, 정점과 간선으로 이루어진 자료구조이다. libertegrace.tistory.com/entry/3-ES6-Practice 5. Data Structure - Graph, Tree, BST Graph 1)개념 : 노드(정점,Node, vertex) 와 간선(edge)로 구성된 자료구조 용어들 차수(Degree): 정점에 몇 개의 간선이 연결되어 있는가 사이클(Cycle): 자기 자신으로 다시 돌아올 수 있는 경로 2) 구현 그�� libertegrace.tistory.com 여기서 Graph와 Tree에 대해 정리한 적이 있는데, 둘 다 정점과 간선으로 이루어져있다. 컴공에서 자료구조는 효율적인 접근 및 수정을 가능케하는 자료의 조직, 관리, 저장을 의미한다. 그러니까,..

삽입정렬: 배열의 모든 요소를 현재 위치보다 아래(현재 위치보다 아래의 값들은 이미 정렬된 배열이다.)의 값들과 (대소)비교해가면서, 현재값의 알맞은 위치를 찾아서 넣어줌(삽입) 으로써 정렬하는 알고리즘 1) 원리 배열의 모든 요소에 대해서 위의 정의를 진행한다. 맨 첫번째 값은 자신의 위치(currIndex:0)보다 아래의 위치가 없으니까 두번째 값(currIndex:1)부터 시작한다. 1. 자신의 위치(currIndex)의 아래 위치((currIndex-1)~0)의 값을 자신과 비교한다. 2. 오름차순으로 정렬할 것이면, 2-1. 자신의 값이 아래위치의 값보다 작으면 자신은 그보다 이전의 자리에 위치해야하므로 아래위치의 값을 뒤로 보낸다. 2-2. 반대로 자신의 값이 아래위치의 값보다 크면 그 자리가..

버블정렬: 오름차순이 기준일 때, 인접한 원소를 비교하여 큰 수를 뒤로 보내는 것을 반복하는 정렬 1) 원리 선택정렬과 달리 버블정렬은 정렬이 완료 된 것(bar 오른쪽)과 아닌 것(bar 왼 쪽)을 나누는 기준인 bar가 시작할 때 맨 뒤에 있다고 생각합니다. 그리고 나서 앞에서 부터 자신의 옆의 원소 (첫 번째 원소와 두 번째 원소, 두 번째 원소와 세 번째 원소, 세 번째와 네 번째 ..) 를 비교하며 bar가 있는 곳 까지 정렬기준에 맞게 자리를 바꿔주면서 큰 것을 뒤로 보내는 정렬을 해나갑니다. 이렇게 앞에서 부터 비교하면서 최대값을 계속 뒤로 밀고 있으므로 한 loop를 돌고 나면 (오름차순 일 때) 최대값이 맨 뒤로 가게 됩니다. 이렇게 이렇게 원소 하나의 자리를 찾아 주었다면 bar를 한 ..

1. 정렬이란, 특정 기준을 적용하여 나열하는 것입니다. ex) 3 4 1 2 →오름차순 정렬→ 1 2 3 4 2. 정렬 알고리즘의 효율성을 판단하는 기준 비교 횟수 데이터가 정렬될 때 이동하는 횟수 사용되는 메모리 양 선택정렬 1) 원리: 정렬이 완료 된 것(bar 왼쪽)과 아닌 것(bar 오른 쪽)을 나누는 기준인 bar가 시작할 때 맨 앞에 있다고 생각합니다. 즉, 시작 할 때는 bar 왼쪽에 아무 원소도 없으니 '아 아직 정렬 된 게 아무 것도 없구나' 라는 의미가 되는 것입니다. 본격적으로 (오름차순)정렬 시에는 그 bar의 오른쪽에 있는 원소들 중 가장 최소 값을 찾고, 찾은 최소값을 bar가 있는 원소의 자리와 바꾸어줍니다. 이렇게 원소 하나의 자리를 찾아 주었다면 bar를 한 칸 옆으로 이..