알고리즘

[알고리즘] 약수 알고리즘

A와 B라는 숫자가 있을 때 A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 이런 약수를 구하는 방법은 3가지가 있다. 모든 자연수로 나누는 방법 : O(n) 말 그래도 1부터 N까지 모든 수로 나누어 보는 방법이다. 10이라는 숫자의 약수를 알기 위해 10번의 나눗셈 연산이 필요하다. 약수가 되는 성질을 이용한 방법 : O(√n) C가 A의 약수라면, A/C도 A의 약수가 된다. 즉 1 ~ √n 까지 구하면 된다. 배수의 성질을 이용한 방법 약수인 수보다 약수가 아닌 수가 더 많이 존재한다. 따라서 배수의 성질을 이용하면 약수만 빠르게 구할 수 있다. 알고리즘 문제 풀이에서는 주로 이 알고리즘이 사용된다. 다음 그림과 함께 6을 기준으로 어떤 성질을 가지고 있는지 확인해보자. 6이하의 자연수 ..

[Baekjoon] 10815 숫자 카드

✉️문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 📝 접근 이분 탐색을 이용한다. 이분 탐색의 핵심은 left point와 right point를 선언한다음 이를 계속 업데이트하는 것이다. 🗝 문제풀이 package baekjoon; import java.util.Arrays; import java.util.Scanner; public class B10815 { static int n,m; static in..

[백준] 2501 약수 구하기 (JAVA)

✉️문제 https://www.acmicpc.net/problem/2501 2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net 📝 접근 브루트 포스 알고리즘, 즉 완전탐색 알고리즘을 이용한다. 🗝 문제풀이 import java.util.Scanner; public class B2501 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int cnt = 0; int answer = 0; for(int i = 1; i

[백준] 2573 빙산 (JAVA)

✉️문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 📝 접근 이 문제를 위해서 필요한 기능은 크게 2가지이며, BFS와 DFS를 모두 이용한다. 1. 빙산의 개수를 확인하는 코드 (DFS) 2. 빙하를 녹이는 메소드 (BFS) TIP ! 배열을 선언할 때 x,y 변수명을 이용하면 더 헷갈리는 것 같다. 이 때는 row와 col 변수명을 이용하는 것이 더 편하다. 🗝 문제풀이 1. 빙산의 개수를 확인하는 코드 (두개의 메소드로 분리하였..

[백준] 2468 안전 영역 (JAVA)

✉️문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 📝 접근 DFS, BFS를 이용하여 문제 풀이가 가능하다. 필자는 DFS를 이용했다. (미로 찾기처럼 뻗어나가는 문제는 DFS를 이용한 풀이를 좋아하는 편이다) 🗝 문제풀이 1. 높이가 0 ~ 100 범위일 때 안전한 지역을 찾고, DFS를 이용하여 안전 지역의 범위를 체크한다. ⚠️ 높이가 1 ~ 100 범위이기 때문에 h를 1로 둘 수 있는데 1부터 시작하게 되면 아무 지역도 물에 잠기지 않..