알고리즘22 [알고리즘] 조합(Combination), 조합 점화식 🟡 조합(Combination) - 조합은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 의미 - 조합의 수학적 공식 nCr = n! / (n-r)! r! - 조합은 '동적 계획법'의 시작, 알고리즘에서 조합을 구현할 때는 위의 수학 공식을 코드화하지 않고 점화식을 사용해 표현 🟡 조합 점화식 다음 3단계로 점화식을 세워보겠다. ① 특정 문제를 가정하기 서로 다른 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정 ② 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기 - 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정하고, 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다. 1) 만약 마지막 데이터를 포함해 총 3개의 데이터를 .. 2023. 5. 22. [알고리즘] 유클리드 호제법(Euclidean algorithm), 최대공약수 최소공배수 구하기 🟡 유클리드 호제법(Euclidean algorithm) - 두 수의 최대 공약수를 구하는 알고리즘 🟡 유클리드 호제법 - 핵심 이론 - 먼저 MOD(나머지) 연산을 이해해야 한다. ex) 10 % 4 = 2 - MOD 연산으로 구현하는 유클리드 호제법 ① 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. ② 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다. ③ 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다. 🟡 유클리드 호제법 - 예시 - 270과 192의 최대 공약수를 유클리드 호제법으로 구하는 예시 🟡 최소 공배수 구하는 법 - 두 수 m, n이 있을 때, m * n = 최대 공약수 * 최소 공배수 이다. 그러므로 두 수의 곱을 최대 공약수로 나누면 .. 2023. 5. 19. [알고리즘] 소수(prime number) 구하기, 에라토스테네스의 체 🟡 소수(prime number) - 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수 - 1과 자기 자신 외에 약수가 존재하지 않는 수 🟡 대량의 수의 소수 판별 - 핵심 이론 - 대표적인 판별법: 에라토스테네스의 체 - 에라토스테네스의 체 알고리즘 ① 구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다. ② 2부터 시작하고 현재 숫자가 지워지지 않았을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다. ③ 배열의 끝까지 ②를 반복한 후(가장 큰 수의 제곱근까지만 연산하면 된다.) 배열에서 남아 있는 모든 수를 출력합니다. - 예시 1에서 30까지의 수 중 소수 구하기 1. 배열 생성하기 1 2 3 4 .. 2023. 2. 20. [알고리즘] 그리디 알고리즘(Greedy Algorithm, 탐욕 알고리즘) 🟡 그리디 알고리즘(Greedy Algorithm) - 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 - 그러므로 전체적으로 봤을 때, 최적해가 아닐 수도 있다. - 선택 기준을 적절히 설정하는 것이 중요 🟡 그리디 알고리즘의 핵심 이론 - 그리디 알고리즘은 아래 3단계를 반복하면서 문제를 해결한다. ① 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. ② 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. ③ 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 ①로 돌아가 같은 과정을 반복한다. 🟡 그리디 알고리즘 적용 예시 - 거스름돈 문제 - .. 2023. 2. 17. [알고리즘] 이진 탐색/이분 탐색(Binary Search) 🟡 이진 탐색/이분 탐색(Binary Search) - 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 - 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾아낸다. - 시간 복잡도: O(logN) - 구현 및 원리가 비교적 간단 🟡 이진 탐색의 핵심 이론 - 데이터가 오름차순으로 정렬된 상태 ① 현재 데이터셋의 중앙값을 선택한다. ② 중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. ③ 중앙값 < 타킷 데이터 일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다. ④ 과정 ①~③을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. (내림차순이라면 조건을 반대로 하여 과정 반복) 2023. 2. 14. [알고리즘] 너비 우선 탐색(BFS) 🟡 너비 우선 탐색(BFS: breadth-first search) - 그래프 완전 탐색 기법 중 하나 - 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 - 선입선출 방식으로 탐색하므로 큐 자료구조 이용 - 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장 🟡 너비 우선 탐색의 핵심 이론 - BFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요 - 그래프는 인접 리스트로 표현(예시 한정) - 큐를 사용 ① BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 ② 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 ③ 큐 자료구조에 값이 없.. 2023. 2. 8. 이전 1 2 3 4 다음
