Junior-Developer

1일 1커밋! 1일 1 백준!

알고리즘

0. 목차 최대공약수(Greatest Common Divisior) 의 개념 최대공약수 알고리즘 1 (시간복잡도 O( min(A ,B) ) ) 최대공약수 알고리즘 유클리드 호제법 (시간복잡도 O(logN)) 최소공배수(Lease Common Multiple)의 개념 최소공배수 알고리즘 (시간복잡도 O(logN)) 1. 최대공약수(Greatest Common Divisior)의 개념 최대 공약수의 개념을 설명하기 위해선, 먼저 공약수의 개념을 짚고가자. 공약수란? 2개이상의 N개의 수가 있을때, N개의 숫자에 모두 나누어떨어지는 공통되는 약수를 의미한다. 예를들어 4, 10, 16 세개의 공약수를 살펴보자 4의 약수는 1, 2, 4 10의 약수는 1, 2, 5, 10 16의 약수는 1, 2, 4, 8, 1..

2021. 8. 12.

알고리즘

0.목차 소수의 개념 소수판별1 (시간복잡도 O(N) 알고리즘) 소수판별2 (시간복잡도 O(√N) 알고리즘) 소수판별3 (시간복잡도 O(Nlog(logN)) 에라토스테네스의 체 알고리즘) 1. 소수(Prime Number) 의 개념 소수는 1과 자기자신을 제외하고 약수를 갖지 않는 1보다 큰 자연수를 의미한다. 2는 소수다. 왜냐하면 2의 약수는 1과 자기자신인 2뿐이기 때문이다. 3은 소수다. 왜냐하면 3의 약수는 1과 자기자신인 3뿐이기 때문이다. 4는 소수가 아니다. 왜냐하면 4의 약수는 1, 2, 4 로 1과 자기자신인 4를 제외한 2가 있기때문이다. 5는 소수다. 왜냐하면 5의 약수는 1과 자기자신인 5뿐이기 때문이다. 6은 소수가 아니다. 왜냐하면 6의 약수는 1, 2, 3, 6 으로 1과 자..

2021. 8. 11.

알고리즘

0. 목차(클릭시 이동) 퀵정렬의 개념 퀵정렬의 과정 정리 퀵정렬의 시간복잡도 퀵정렬 코드 1. 퀵정렬의 개념 퀵정렬은 이름 그대로, 다른 정렬보다 빠른 수행속도로 데이터를 정렬하는 기법이다. 퀵정렬은 버블정렬, 삽입정렬, 선택정렬과 같이 다른원소와 비교를 하며 정렬을 하는 비교정렬이다 한 문제를 작은 문제로 나눈뒤, 각각의 작은 문제들을 해결하고, 그 결과를 종합하여 본 문제를 해결하는 분할정복 알고리즘이다. 피봇(Pivot) = 분할된 배열을 정렬할 기준원소 left = 분할된 배열에서 피봇값보다 작은 원소들을 판별해주는 포인터 right = 분할된 배열에서 피봇값보다 큰 원소들을 판별해주는 포인터 먼저 초기값으로 배열에 5 1 4 7 2 3 8 6 9 가 있다고 가정을 해보자. 1. 피봇을 설정을 ..

2021. 7. 12.

알고리즘

0. 목차 버블정렬의 개념 버블정렬의 과정 정리 버블정렬의 시간복잡도 버블정렬 코드 1.버블정렬의 개념 버블정렬은 거품이 위로 올라가는것과 유사하다는 의미에서 버블정렬이라는 이름이 붙여졌다. 버블정렬은 인접한 두 데이터를 비교해가며, 조건을 만족하면 SWAP을 하며 정렬하는 방식이다. 말로는 어려울테니 아래의 그림을 보며 이해해보자. 5 1 4 7 2 의 데이터를 버블정렬을 이용하여 오름차순으로 정렬하는 과정을 보여준다. 1. 5와 1을 비교했을 때, 5>1 이므로 교환 2. 5와 4를 비교했을 때, 5>4 이므로 교환 3. 5와 7을 비교했을 때, 52 이므로 교환 =>이렇게 1페이즈에서 정렬되지않은 데이터중 가장 큰 수인 7이 맨 위(맨 뒤) 로 떠올랐다. 그럼 다음으로 정렬되지않은 데이터중에서 가장..

2021. 5. 6.

알고리즘

0. 목차 삽입정렬의 개념 삽입정렬의 과정 정리 삽입정렬의 시간복잡도 삽입정렬 코드 1. 삽입정렬의 개념 정렬의 개념은 앞의 선택정렬에서 설명한것과 동일하다. (khu98.tistory.com/102?category=858723) 선택정렬에서 정렬을 하는법은, 정렬될 자리에 들어갈 원소를 선택한뒤, 교환을 하며 정렬을 하는거였다면, 삽입정렬은 해당 원소가 자기가 들어가야할 자리에 찾아가 삽입하며 정렬을 하는 방법이다. 선택정렬의 예와 동일한 예를 사용해보자. 배열에 5 1 4 7 2 가 있고, 이것을 오름차순으로 정렬하고싶다고 해보자. 편의상 인덱스를 1부터 시작한다고 가정하자. 이때, 맨 앞에있는 1번인덱스를 정렬되어있는 원소라고 생각한다. 인덱스 1 2 3 4 5 데이터 5 1 4 7 2 이제 2번인..

2021. 5. 5.

알고리즘

0. 목차 선택정렬의 개념 선택정렬의 과정 정리 선택정렬의 시간복잡도 선택정렬 코드 1. 선택정렬의 개념 우리는 여러개의 데이터를 가지고 있을때, 탐색이 용이하려고, 또는 작업을 편리하게 하기 위해, 특정 조건을 기준으로 데이터들을 "정렬" 한다. 정렬을 하는 방법중 선택정렬이 있다. 말 그대로 선택을 하며 정렬을 하는 방법이다. 오름차순으로 정렬을 하기위해선, 맨앞에서부터 제일 작은것, 그다음 작은것, 그다음 작은것 을 차례대로 나열을 해야하는데, 이를 정렬되지않은 배열을 탐색하며 최솟값을 찾은 뒤, 앞에다가 놓음으로써 정렬을 시키는 방법이다. 예를들어 배열에 5 1 4 7 2 가 있고, 이것을 오름차순으로 정렬하고싶다고 해보자. 편의상 인덱스를 1부터 시작한다고 하자. STEP 0 RESULT 인덱스..

2021. 5. 3.