본문 바로가기

알고리즘

[개념] 에라토스테네스의 체 에라토스테네스의 체는 가장 대표적인 소수(Prime Number) 판별 알고리즘이다. 소수란 '양의 약수를 두 개만 가지는 자연수'를 의미하며 그 말은 결국 1과 자기자신만을 약수로 가지는 자연수이다. #include bool isPrimeNumber(int x) { for(int i=2; i 더보기
[개념] 조합, 순열 + DFS,BFS [순열, 조합] 순열이라는 것은 주어진 수열에서 순서에 따라 결과가 달라지는 방식을 순열이라고 한다. 말 그대로, 순서가 존재하는 열 이라는 것이다. 즉 순열에서 { 1, 2, 3 } 과 { 1, 3, 2 } , { 2, 1, 3 } 등.. 모두 다른 결과를 가져온다. 순서가 다르기 때문이다. 조합은 순서가 상관이 없는 모임을 의미한다. 순서가 상관 없기 때문에 { 1, 2, 3 }, { 1, 3, 2 } , { 2, 1, 3} 모두 같은것으로 취급을 한다. 순서가 상관없기 때문에 1, 2, 3 이라는 3개의 숫자로 이루어져있다는 점에서 똑같은 취급을 하는 것이 조합이다. 1. 조합이용 - 5개중 3개 뽑아보기 #include #define MAX 5 using namespace std; int Arr[.. 더보기
[개념] 그래프 이론 (무방향) 그래프 G=(V,E) - V: 노드(node) 혹은 정점(vertex) - E: 노드쌍을 연결하는 에지(edge) 혹은 링크(link) - 개체(object)들 간의 이진관계를 표현 - n=|V|, m=|E| - 어떤 노드 v에 인접한 노드를 찾으려면 결국 해당 v의 한 행을 봐야하므로 O(n) 시간이 걸린다. - 어떤 에지 (u,v) 검사 -> 배열의 (u,v) 만 찾으면 되므로 O(1) 시간 - 어떤 노드 v에 인접한 모든 노드 찾으려면 결국 v의 연결리스트들의 길이를 구하면 되고 그것은 인접한 노드의 수와 동일하다. degree(v) = v에 인접한 노드의 갯수 (인접행렬보다 유리) - 어떤 에지 (u,v) 가 존재하는지 검사 - 연결리스트의 길이에 비례하는 시간이 걸린다. (인접행렬보다.. 더보기
[개념] 버블정렬, 선택정렬 선택정렬 (Selection Sort) 선택정렬은 배열중에 가장 작은 원소들을 왼쪽부터 채워나가면서 숫자를 정렬하는 방법입니다. 최소원소를 찾은 후 => 최소원소를 맨 왼쪽원소와 교환(즉, 왼쪽부터 정렬된 원소로 채워집니다.) => 왼쪽원소를 제외하고 원소가 하나남을때 까지 이단계를 반복 선택정렬의 비교횟수를 구해보면 1단계 => n개의 원소 비교 2단계 => n-1 개의 원소 비교 3단계 => n-2 개의 원소 비교 .... 를 하여 비교 횟수는 n(n-1) /2 가 됩니다. 즉, 시간복잡도는 O(n^2)이 됩니다. for(i=0; i arr[j+1]) { int temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } } } 출처 https://cornswro.. 더보기
[개념] 피보나치 수열 알고리즘 피보나치 수열 알고리즘 (1) 재귀(recursion) (2) 동적 프로그래밍(Dynamic Programming) (3) 반복(For문) 피보나치 수열의 BigO()는 방식에 따라 다름. (1) 재귀: BigO(2^n) (2) 동적: BigO(n^2) (3) 반복: BigO(n) 안정성 문제로 가장 좋은 방법은 바로 반복이다. import java.util.Scanner; public class Pibo { Scanner s = new Scanner(System.in); System.out.print("정수 입력 : "); int j=s.nextInt(); int num1,num2,sum; num1=0; // 첫번째와 두번째 값이 1이어야 하므로 초기값을 0과 num2=1; // 1로 준다 sum=1;.. 더보기
Comparator<T> 인터페이스 - 정렬문제에서 자주 쓰이는 기법 Comparator 인터페이스 이용 만약 알파벳의 사전편찬 순이라던가 숫자 오름차순 같이 natural order 대로의 정렬 말고 사용자가 원하는 임의의 정렬 기준(가령 이름의 문자열 길이 순서)대로 정렬하고 싶으면 어떻게 해야할까? 이럴땐 정렬이 되는 기준을 개발자가 직접 정의해주어야 한다. 이때 기준이 되는 것이 Comparator 인터페이스를 구현하는 것이다. 즉, compare() 메소드를 오버라이딩 해주는 것이다. Comparator 인터페이스는 compare() 메소드와 equals() 메소드 두 가지를 갖고 있지만 사실 이를 구현 하는 모든 클래스는 Object클래스를 상속한다. 그런데 Object클래스에서 equals() 메소드를 구현하고 있기 때문에, Comparator 인터페이스를 구.. 더보기
[개념] KMP 알고리즘 KMP 알고리즘은 문자열 A와 문자열 B가 있을 때, 문자열 A에서 문자열 B를 찾아주는 알고리즘 입니다. KMP는 KMP를 만든 사람의 이름인 Knuth, Morris, Prett 세 사람의 앞 글자를 따서 KMP 알고리즘이라고 불립니다. 1) 모든 경우를 다 탐색할 경우 문자열 A의 길이가 N,문자열 B의 길이가 M이라면 O(N*M)의 시간 복잡도를 가지게 됩니다. 만약 N,M이 10만인 문제가 주어진다면 시간 초과를 보게 됩니다. 2) KMP 알고리즘을 사용할 경우 놀랍게도 O(N+M)의 시간복잡도만에 문자열 A에서 문자열 B를 검색 할 수 있습니다. 그러면 AKAKA라는 문자의 pi[4]는 1일까요? 아닙니다 절반을 넘는경우도 세줍니다. AKA==AKA이기 때문에 pi[4]는 3이되겠군요. fai.. 더보기
백준 1052. 물병 (C++) https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다. 물은 다음과 같이 재분배 한다. 먼저 같은 양의 www.acmicpc.net 여기서 POINT는, a. while문 안에서 계속 N/2를 한다 (조건: N의 몫이 0이 될 때 까지) b. N%2 == 1 or 0 이므.. 더보기

티스토리툴바