전체 글 161

[알고리즘] 유클리드 호제법

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..

알고리즘 2023.04.13

[알고리즘] 오일러 피 함수

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

알고리즘 2023.04.12

[알고리즘] 에라토스테네스의 체

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

알고리즘 2023.04.10

[자바 개념] Comparable과 Comparator

1. 필요 이유 학생이라는 객체를 만들고, 해당 객체의 속성으로 나이, 성적 평균이 있다고 하자. 학생A와 학생B를 비교하고자 할 때 어떻게 비교를 해야 할까? 사용자가 기준을 정해주지 않으면 뭐로 비교를 해야 하는지 알 수가 없다. 이럴 때 Comparable 혹은 Comparator 인터페이스의 비교 메서드를 사용해야 한다. 2. Comparable 1) 개념 객체를 비교하는데 사용하는 인터페이스. 자기 자신과 매개변수로 들어오는 객체를 비교한다. 2) 메서드 compareTo(T o) 3) 구현 class Student implements Comparable { int age; int score; Student(int age, int score) { this.age = age; this.score ..

자바 2023.04.10

[스프링] 의존성 주입

1. 개념 어떤 서비스를 개발한다고 생각해보자. 특정 서비스에는 다양한 기능들이 있고, 다양한 기능을 개발하기 위해서는 다양한 클래스가 필요하다. 기능 별로(로그인, 회원가입, 글 작성 등) 클래스가 분류될 것이고, 그 기능 안에서 service, controller, repository, entity 등 세부 기능으로 또 클래스가 분류된다. 이렇듯 우리는 스프링으로 서비스를 개발할 때 아주아주 다양한 클래스를 접하게 된다. 나는 앞으로 class 하나 하나를 컴포넌트라고 이야기 하려고 한다. 예를 들어 회원가입 기능을 생각해보자. 이를 위해서는 controller, service, repository, passwordEncoder 등의 컴포넌트가 필요하다. controller는 service컴포넌트가 ..

Spring/spring 2023.04.07

[알고리즘] 그리디 알고리즘

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

알고리즘 2023.04.07

[알고리즘] 이진 탐색

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

알고리즘 2023.04.05

[알고리즘] BFS(너비 우선 탐색)

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

알고리즘 2023.04.04

[알고리즘] DFS(깊이 우선 탐색)

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

알고리즘 2023.04.03

[알고리즘] 정렬 - 기수 정렬

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를 넣는다. 그리고 나..

알고리즘 2023.03.31