Coding Diary

1. 개념 두 수의 최대 공약수를 구하는 알고리즘이다. + 두 수의 곱을 최대 공약수로 나누면 최소공배수도 구할 수 있다. 2. 방법 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. 위의 작은 수와 MOD 연산의 결과로 MOD 연산을 수행한다. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다. MOD연산은 큰 수를 작은 수로 나눈 나머지를 구하는 연산이다. 3. 코드 // 반복문으로 구현 public static int gcd(int num1, int num2){ int small = num1 num2 ? num1 : num2; int temp = 0; while(small != 0){ temp = big % small..

1. 개념 1과 n까지의 수 중에서 n과 서로소인 수의 개수를 찾는 함수. 예를 들어 8을 오일러 피 함수에 넣어 값을 구하면 4가 나온다. 8과 서로소인 수는 1, 3, 5, 7이기 때문이다. *서로소 두 수의 공약수가 1뿐인 수. 2. 방법 구하고자 하는 범위만큼 배열을 초기화한다. 2부터 시작해서 현재 선택된 숫자(2)의 배수에 해당하는 수를 탐색하면서 그 수를 수-수/2 로 업데이트한다. 그 다음 소수로 넘어가서 위 과정을 반복한다. 3. 원리 1) 소수의 배수/소수의 의미 소수의 배수/소수를 하면 소수의 배수보다 작은 수 중 소수를 무조건 약수로 가져서 소수의 배수와 서로소가 될 수 없는 수들의 개수를 구할 수 있다. 2) 수-수/2 결국 수에서 위에서 구한 걸 빼주면 수보다 작거나 같은 수 중..

1. 개념 소수를 구하기 위해 사용하는 방법. 2. 방법 구하고자 하는 소수의 범위만큼 1차원 배열을 만든다. 1부터 보면서 해당 수가 소수인지 아닌지 판별한다. 만약 소수가 아니면 지운다. 만약 소수면 놔두고, 그 수의 배수를 배열에서 모두 지운다. 배열 끝까지 위 과정을 반복한 후 남아있는 수들이 해당 범위 내에서의 소수다. 3. 특징 이중 for문을 사용해야 하므로 이론적인 시간 복잡도는 O(n2)이다. 하지만, 배수를 삭제하는 과정이 있기 때문에, 실제로 실행을 해 보면 바깥쪽 for문을 건너뛰는 경우가 많이 발생한다. 그래서 실제 시간복잡도는 O(nlog(logn))이다. 4. 코드 nums[0] = -1; nums[1] = -1; for(int i = 2; i

1. 개념 현재 상태에서 문제를 해결할 수 있는 가장 좋은 해를 선택해나가면 최적의 답을 구할 수 있게 되는 알고리즘 2. 과정 1) 해 선택 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다 2) 적절성 검사 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다 3) 해 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다. 3. 특징 시간 복잡도는 O(n)이다. n개를 쭉 살펴보면서 하나를 해라고 선택한 후, 적절성 검사를 하고, 적절하면 해라고 인식, 적절하지 않으면 해라고 인식하지 않는 과정을 n개 동안 진행한다. 앞의 선택(해를 선택하는)이 뒤의 선택에 영향을 미치지 않을 때 사용 가능하다. 문..

1. 개념 정렬되어 있는 데이터에서 원하는 값을 찾을 수 있는 알고리즘. 정렬되어 있는 데이터 중 중앙값을 찾고, 그 중앙값과 내가 찾고자 하는 값을 비교해서 찾고자 하는 값이 더 작으면 중앙에서 왼쪽만 보고, 찾고자 하는 값이 더 크면 중앙에서 오른쪽만 본다. 이렇게 하면 살펴야 하는 데이터의 크기를 절반씩 줄여나갈 수 있다. 2. 예시 데이터: 3 7 13 15 23 35 38 40 찾고자 하는 데이터: 13 맨 처음 중앙값은 15, 찾고자 하는 값이 더 작으니 15보다 왼쪽만 본다. 15보다 왼쪽 중 중앙값은 7, 찾고자 하는 값이 더 크니 7보다 오른쪽만 본다. 7보다 오른쪽 중 중앙값은 13. 찾고자 하는 값을 찾았다. 3. 특징 N개의 데이터에서 logN번의 연산으로 원하는 데이터를 찾을 수 ..

1. 개념 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. BFS는 그래프를 순회하는 방법 중 하나이다. BFS는 시작 노드부터 출발해서 시작 노드와 인접한 것들을 모두 방문한다. 그리고 다음 노드를 방문하고, 그 노드와 인접한 것들을 모두 방문한다. 2. 예시 위와 같은 그래프를 BFS로 방문하면 다음과 같다. 방문 우선순위는 숫자 오름차순이다. 1 -> 2 -> 3 -> 8 -> 6 -> 5 -> 4 -> 7 3. 특징 선입선출 탐색이다 큐 자료구조를 이용한다 시간복잡도는 O(노드 수 + 에지 수)이다. 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다 4. 코드 1) 연결리스트 만들..

1. 개념 주어진 어떤 정점을 출발하여 체계적으로 그래프의 모든 정점들을 순회하는 것을 그래프 순회라고 한다. DFS는 그래프를 순회하는 방법 중 하나이다. DFS는 시작 노드부터 출발해서, 시작 노드와 인접한 것 중 하나를 방문한다. 그리고 그 방문한 것과 인접한 것을 또 방문한다. 이렇듯 시작 노드부터 인접한 것을 따라 계속 그걸 방문해나가는 방법이다. 마치 아래 방향으로 쭉 깊이있게 탐색하는 것 같다. 만약, 더 이상 방문할 것이 없다면 이전 노드로 돌아와서 이전 노드와 인접해 있지만 아직 방문하지 않은 노드를 방문해 나간다. 2. 예시 위와 같은 그래프를 DFS로 방문하면 다음과 같다. 같은 단계일 경우 오름차순으로 노드를 방문한다. 1 -> 2 -> 6 -> 8 -> 3 -> 5 -> 4 -> ..

1. 개념 일의 자리만 보고 정렬을 한다. 그 이후에 십의 자리만 보고 정렬을 한다. 즉 기수만 보고 정렬을 진행하는 것이다. 여기서 기수란 각 진수에서 표현할 수 있는 수를 말한다. 예를 들어 10진수면 기수는 0~9이다. 보통 이런 기수 정렬은 기수를 담을 큐를 만들어 놓고, 수를 기수에 맞는 큐에 넣었다 빼며 정렬을 진행한다. 예를 들어 10 32 11 25 이런 수가 있을 때, 0을 담는 큐를 만들고, 1을 담는 큐를 만들고... 9를 담는 큐를 만든다. 그리고 10의 일의자리는 0이니 0을 담는 큐에 10을 넣는다. 32의 일의자리는 2이니 2를 담는 큐에 32를 넣는다. 11의 일의자리는 1이니 1을 담는 큐에 11을 넣는다. 25의 일의자리는 5이니 5를 담는 큐에 25를 넣는다. 그리고 나..

1. 개념 하나의 배열을 크기가 같은 2개의 배열로 분할한다. 분할은 분할 대상의 배열 길이가 2이상이면 계속 반복하다 분할 대상 배열 길이가 1이하가 되면 반복을 멈춘다. 분할된 배열을 병합하는데, 정렬을 하면서 병합을 진행한다. 병합을 진행할 때는 병합 대상이 되는 2개의 배열 각각에 포인터를 두고, 포인터가 가리키는 원소 중 더 작은 것을 병합 결과 배열에 놓고, 병합 결과 배열에 놓인 원소의 포인터는 증가시킨다. 2. 특징 분할 정복 방법이 적용된다. 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 각각을 해결할 때는 재귀적으로 함수 호출을 진행하여 해결한다. 만약 배열로 데이터를 다루면 제자리 정렬이 아니다. 병합된 내용을 담을 추가 메모..

1. 개념 배열에서 피봇을 하나 정한다. 맨 왼쪽에서 시작해서 배열을 살피는 화살표가 하나 있고, 맨 오른쪽에서 시작해서 배열을 살피는 화살표가 하나 있다. 왼쪽 시작 화살표를 옮겨가며 피봇보다 크거나 같은 원소를 찾는다. 오른쪽 시작 화살표를 옮겨가며 피봇보다 작은 원소를 찾는다. - a 만약 왼쪽 시작 화살표가 원소를 하나 찾고, 오른쪽 시작 화살표가 원소를 하나 찾으면 둘을 교환한다. 교환 후 왼쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 크거나 같은 원소를 찾고, 오른쪽 시작 화살표는 아까 찾은 거 이후 부터 다시 피봇보다 작은 원소를 찾는다. - b-1 만약 왼쪽 시작 화살표와 오른쪽 시작 화살표가 만나면 만난 위치에 있는 원소와 피봇을 교환한다. 교환된 피봇은 확정된다. - b-2..