전체 글 (59) 썸네일형 리스트형 유클리드 호제법 유클리드 호제법두 수의 최대 공약수를 구하는 알고리즘. 일반적으로 최대 공약수를 구하는 방법은 소인수 분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시. 핵심 이론유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야 함. MOD 연산이 최대 공약수를 구하는 데 사용하는 핵심 연산이기 때문.연산기능예제MOD두 값을 나눈 나머지를 구하는 연산10 MOD 4 = 2 # 10 % 4 = 2 MOD 연산으로 구현하는 유클리드 호제법큰 수를 작은 수로 나누는 MOD 연산을 수행앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)으로 MOD 연산을 수행'단계 2'를 반복하다가 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택유클리드 호제법의 원리 이.. 오일러 피 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻함. 오일러 피의 함수의 원리구하고자 하는 오일러 피의 범위만큼 배열을 자기 자신의 인덱스 값으로 초기화.'2'부터 시작해 현재 배열의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 배열에 끝까지 탐색하여 P[i] = P[i] - P[i]/K 연산을 수행(i의 K의 배수)배열의 끝까지 2번을 반복하여 오일러 피 함수를 완성오일러 피 함수 예시구하고자 하는 범위까지 배열을 생성한 후 2를 선택2의 모든 배수마다 P[i] = P[i] - P[i]/2 연산을 수행해 값을 갱신. 예를 들어 8 = 8 - (8 / 2)를 통해 4를 계산.소수 구하기에서 배수를 지우는 부분만 P[i] = .. 소수 구하기 - 에라토스테네스의 체 소수소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 의미. 이와 같은 의미로 1과 자기 자신 외에 약수가 존재하지 않는 수를 의미. 핵심 이론소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있음. 에라토스테네스의 체구하고자 하는 소수의 범위만큼 1차원 배열을 생성'2'부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지움. 이때 처음으로 선택된 숫자는 지우지 않음.배열의 끝까지 2번을 반복한 후 배열에서 남아 있는 모든 수를 출력.에라토스테네스의 체 예시- 1부터 30까지의 수 중 소수를 구하기먼저 주어진 범위까지 배열을 생성. 1은 소수가 아니므로 삭제하고, 배열은 2부터 시작선택한 수의 배수를.. 그리디 알고리즘 그리디 알고리즘현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘. 그리디 알고리즘 수행 과정해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다. 탐색 DFS(깊이 우선 탐색)깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘.기능특징시간 복잡도(노드 수: V, 에지 수: E)그래프 완전 탐색- 재귀 함수로 구현- 스택 자료구조 이용(FILO)O(V + E) ** 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 '스택 오버플로(stack overflow)'에 유의해야 함. 깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있음. 핵심 이론한 번 방문한 노드를 다시 방문하면 안되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프.. 정렬 버블(Bubble) 정렬데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 핵심 이론두 인접한 데이터의 크기를 비교해 정렬하는 방법. 간단하게 구현할 수 있지만, 시간 복잡도는 O(n2)으로 다른 정렬 알고리즘보다 속도가 느린 편. 루프(loop)를 돌면서 인접한 데이터 간의 swap 연산으로 정렬. 버블 정렬 과정비교 연산이 필요한 루프 범위를 설정한다.인접한 데이터 값을 비교한다.swap 조건에 부합하면 swap 연산을 수행한다.루프 범위가 끝날 때까지 2~3을 반복한다.정렬된 영역을 설정. 다음 루프를 실행할 때는 이 영역을 제외한다.비교 대상이 없을 때까지 1~5를 반복한다.-> 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이.. 스택과 큐 스택스택은 삽입과 삭제 연산이 후입선출(LIFO, Last in First out)로 이뤄지는 자료구조. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있음.스택에 들어가면 top이 새 값을 가리킴. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 됨. 스택 용어 - 위치top : 삽입과 삭제가 일어나는 위치를 뜻한다. - 연산push : top 위치에 새로운 데이터를 삽입하는 연산.pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산.peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산.** 스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에서 필요 , 후입선출은 개념 자체가.. 투 포인터(Two Pointers)와 슬라이딩 윈도우(Sliding Window) 투 포인터- 투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘- 구간을 비교하면서 원하는 조건에 달성할 때까지 먼저 end를 움직인 다음, start를 하나씩 이동하여 구간을 좁혀가며 조건을 확인 1. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.2. 현재 부분 합이 M과 같다면 카운트한다.3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.4. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.5. 모든 경우를 확인할 때까지 2~4번 과정을 반복 슬라이딩 윈도우- 2개의 포인터로 범위를 지정한 다음 범위(window)를 유지한 채로 이동(sliding)하며 문제를 해결 1... 이전 1 2 3 4 ··· 8 다음
