public class Ex11724 {
static int N;
static int M;
static List<List<Integer>> graph;
static boolean[] visited;
static int cnt;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 인접 리스트 그래프 초기화
graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
// 방문 배열 초기화
visited = new boolean[N + 1];
cnt = 0;
}
}
[2] 문제에서 요구하는 연결망의 갯수 구하는 코드를 넣는다.
- 이 문제는 프로그래머스의 '네트워크' 문제와도 유사했는데, 분리된 연결망을 구하는 문제였다.
> 분기를 확인하기 위한 코드
// 2. dfs
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
dfs_stack(i);
cnt++;
}
}
System.out.println(cnt);
> 예외 상황 : 노드가 하나밖에 없고 간선이 없는 경우 - 네트웍은 하나다.
// 노드가 하나밖에 없고 간선이 없어도 네트웍은 하나로 치부
if (N == 1 && M == 0) {
System.out.println(1);
return;
}
[3] 본격적인 dfs를 짜기
[3-1] 재귀 방식의 dfs
public static void dfs(int root) {
// 루트 방문 체크
visited[root] = true;
// 인접한 노드들 중 방문하지 않은 곳을 방문
for (int i = 0; i < graph.get(root).size(); i++) {
int adjNode = graph.get(root).get(i);
if (!visited[adjNode]) {
dfs(adjNode);
}
}
}
[3-2] 스택 방식의 dfs
public static void dfs_stack(int start) {
Stack<Integer> stack = new Stack<>();
visited[start] = true;
stack.push(start);
while (!stack.isEmpty()) {
int curNode = stack.pop();
for (int i = 0; i < graph.get(curNode).size(); i++) {
int adjNode = graph.get(curNode).get(i);
if (!visited[adjNode]) {
stack.push(adjNode);
visited[adjNode] = true;
}
}
}
}
package graph;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
public class Ex11724 {
static int N;
static int M;
static List<List<Integer>> graph;
static boolean[] visited;
static int cnt;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
if (N == 1 && M == 0) {
System.out.println(1);
return;
}
// 1. 시작 노드를 정한 후 사용할 자료구조 초기화
// 인접 리스트 그래프 초기화
graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
graph.get(end).add(start);
}
// 방문 배열 초기화
visited = new boolean[N + 1];
cnt = 0;
// 2. dfs
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
dfs_stack(i);
cnt++;
}
}
System.out.println(cnt);
}
public static void dfs(int root) {
// 루트 방문 체크
visited[root] = true;
// 인접한 노드들 중 방문하지 않은 곳을 방문
for (int i = 0; i < graph.get(root).size(); i++) {
int adjNode = graph.get(root).get(i);
if (!visited[adjNode]) {
dfs(adjNode);
}
}
}
public static void dfs_stack(int start) {
Stack<Integer> stack = new Stack<>();
visited[start] = true;
stack.push(start);
while (!stack.isEmpty()) {
int curNode = stack.pop();
for (int i = 0; i < graph.get(curNode).size(); i++) {
int adjNode = graph.get(curNode).get(i);
if (!visited[adjNode]) {
stack.push(adjNode);
visited[adjNode] = true;
}
}
}
}
}
(2) 시간 복잡도
- DFS는 그래프의 정점의 수(V)와 간선의 수(E)를 통해 시간 복잡도를 표현하는데,
- 인접 행렬을 사용하는 경우, 행으로는 전체 정점(V)을, 열로는 인접한 정점과의 연결 여부(E)를 확인하므로,
-- O(V^2) 의 시간 복잡도를 가진다.
- 인접 리스트를 사용하는 경우, 각 정점(V)을 방문한 후, 인접 노드를 따라 하나씩 탐색하기 때문에,
-- O(V + E)의 시간 복잡도를 가진다.
- 그래프를 완전 탐색할 때에는 따라서, 간선이 적을 때에 인접 리스트를 사용하는 것이 좋다.
2. BFS (너비 우선 탐색)
bfs란, 루트에서 시작해서 인접한 노드를 먼저 탐색하는 방법
[출처] https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
- DFS의 경우, 깊이 있게 탐색했다면, BFS는 가까운 지점을 먼저 탐색하는 "넓은" 탐색이다.
- 참고한 블로그에서는, 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때에 이 방법을 쓴다고 했다.
- 안정성이라는 것은, 어떤 데이터 { 1, 2, 3, 1, 1, 1 } 을 정렬한다고 할 때,
같은 숫자 1에 대해서 {1, 1,1,1} 의 순서가 유지되도록 정렬되는 것을 '안정성이 있다'라고 한다.
- 아래의 보조 메모리는 추가적으로 드는 메모리를 이야기하는데,
버블이나 삽입, 선택의 경우 swap시에 드는 변수 1개만 필요하기 때문에 보조메모리가 1개만 소요된다.
정렬 방법
시간 복잡도
보조메모리
안정성
Ω(n)
Θ(n)
O(n)
버블 정렬
n
n^2
n^2
1
o
삽입 정렬
n
n^2
n^2
1
o
선택 정렬
n^2
n^2
n^2
1
x
합병 정렬
n logn
n logn
n logn
n
o
힙 정렬
n logn
n logn
n logn
1
x
퀵 정렬
n logn
n logn
n^2
logn
x
트리 정렬
n logn
n logn
n^2
n
x
기수 정렬
dn (*d:자릿수)
dn
dn
n+k
o
계수 정렬
n+k (*k:max)
n+k
n+k
n+k
o
셸 정렬
n logn
gap에 따라 다름
n^2
1
x
| 버블정렬 / 삽입 정렬 / 선택 정렬
// 버블 정렬
public static void bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
// 삽입 정렬
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
} else {
break;
}
}
}
}
// 선택 정렬
private static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
swap(arr, i, min);
}
}
| 합병정렬 / 힙 정렬 / 퀵 정렬 / 트리 정렬
1. 합병정렬
public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, tmp, left, mid);
mergeSort(arr, tmp, mid + 1, right);
merge(arr, tmp, left, right, mid);
}
}
public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
int lCursor = left;
int rCursor = mid + 1;
int idx = left;
while (lCursor <= mid || rCursor <= right){
if (lCursor <= mid && rCursor <= right) {
if (arr[lCursor] <= arr[rCursor]) {
tmp[idx++] = arr[lCursor++];
}else {
tmp[idx++] = arr[rCursor++];
}
} else if (lCursor <= mid && rCursor > right) {
tmp[idx++] = arr[lCursor++];
} else {
tmp[idx++] = arr[rCursor++];
}
}
for (int i = left; i <= right; i++) {
arr[i] = tmp[i];
}
}
2. 힙 정렬
public static void heapSort(int[] arr) {
// 가장 끝의 자식이 있는 부모노드를 잡아서 최대힙구조로 정렬
for (int i = arr.length / 2 - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
// 가장 앞의 노드가 최대값임을 이용하여 나머지 정렬
for (int i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
heapify(arr, 0, i);
}
}
public static void heapify(int[] arr, int parentIdx, int size) {
int leftIdx = parentIdx * 2 + 1;
int rightIdx = parentIdx * 2 + 2;
int maxIdx = parentIdx;
if (leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
maxIdx = leftIdx;
}
if (rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
maxIdx = rightIdx;
}
if (maxIdx != parentIdx) {
swap(arr, parentIdx, maxIdx);
heapify(arr, maxIdx, size);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
3. 퀵 정렬
- pivot 값은 처음값이거나 중앙값이 될 수 있다. (상황에 맞게 선택하면 된다)
- 퀵 정렬은 pivot을 기준으로 좌우 정렬을 하고, pivot의 양 옆을 다시 분할하여 정렬하는 것을 반복한다.
public static void quickSort(int[] arr, int left, int right) {
// 탈출문
if (left >= right) {
return;
}
// 피봇값 지정
int pivot = partition(arr, left, right);
// 피봇값의 좌우를 다시 퀵소트
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public static int partition(int[] arr, int left, int right) {
// 피봇값과 양 옆의 커서를 지정
int pivot = arr[left];
int lCursor = left;
int rCursor = right;
// 1. 양 끝의 커서가 서로 같기 전까지
// 우측은 피봇값보다 더 작은 값을 찾고
// 좌측은 피봇값보다 같거나 더 큰 값을 찾아 swap
// 2. 양 끝의 커서가 서로 같아지면
// 한쪽 커서와 피봇을 swap
while (lCursor < rCursor) {
while (arr[rCursor] > pivot && lCursor < rCursor) {
rCursor--;
}
while (arr[lCursor] <= pivot && lCursor < rCursor) {
lCursor++;
}
swap(arr, lCursor, rCursor);
}
swap(arr, left, lCursor);
return lCursor;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
4. 트리 정렬
- 이진탐색트리를 만들어 정렬하는 방식으로, 알고리즘 복잡도는 NlogN이다.
- 이 부분은 비선형구조 > 이진탐색트리 포스팅에 적은 AVL, Red-Black을 확인해주세요.
| 기수 정렬 / 계수 정렬 / 셸 정렬
1. 기수 정렬
- 기수 : 자릿수를 의미한다.
- 기수정렬 : 일의 자리, 십의 자리, 백의 자리.. 순으로 각 자릿수에 해당되는 수를 큐에 담은 후 기존 배열에 넣는 방식
public static void radixSort(int[] arr) {
// 각 자리에 큐를 담은 배열
ArrayList<Queue<Integer>> list = new ArrayList<>();
for (int i = 0; i < 10; i++) { // 10진수 기준으로 자리 수 0 ~ 9
list.add(new LinkedList<>());
}
// 최대 자릿수
int maxLen = getMaxLen(arr);
// 나누는 수
int div = 1;
// 배열에 넣어줄 인덱스
int idx = 0;
// 기수 정렬에 대한 반복문
for (int i = 0; i < maxLen; i++) {
// 해당 자릿수의 큐에 데이터를 추가
for (int j = 0; j < arr.length; j++) {
list.get((arr[j] / div) % 10).offer(arr[j]);
}
// 해당 자릿수의 큐를 가져와서, 기존 배열(arr)에 넣는다.
for (int j = 0; j < 10; j++) {
Queue<Integer> queue = list.get(j);
while (!queue.isEmpty()) {
arr[idx++] = queue.poll();
}
}
// 그 다음 자릿수를 위한 준비작업
idx = 0;
div *= 10;
}
}
// 데이터의 최대 자릿수 반환
public static int getMaxLen(int[] arr) {
int maxLen = 0;
for (int i = 0; i < arr.length; i++) {
int len = (int)Math.log10(arr[i]); // 자릿수
if (maxLen < len) {
maxLen = len;
}
}
return maxLen;
}
2. 계수 정렬
- 계수 : 관계가 있는 수, 상수를 의미한다.
- 계수정렬 : 상수 data 수열에서 최대값 + 1을 size로 배열에 생성해, 카운트한 후 다시 기존 배열에 넣는 방식
public static void countingSort(int[] arr) {
// 최댓값의 + 1 만큼 배열을 잡아둔다
int max = Arrays.stream(arr).max().getAsInt();
int[] cntArr = new int[max + 1];
// 숫자데이터에 해당되는 인덱스의 cnt를 하나 늘린다.
for (int i = 0; i < arr.length; i++) {
cntArr[arr[i]]++;
}
// cntArr을 한바퀴씩 돌면서 기존 배열(arr)에 해당 인덱스의 갯수만큼 삽입
int idx = 0;
for (int i = 0; i < cntArr.length; i++) {
while (cntArr[i] > 0) {
arr[idx++] = i;
cntArr[i] -= 1;
}
}
}
//최댓값 하나만 너무 크면 비효율적 -> HashMap을 통해 보완할 수 있다
public static void countingSort2(int[] arr) {
// key : data, value : 갯수
HashMap<Integer, Integer> map = new HashMap<>();
for (int item : arr) {
map.put(item, map.getOrDefault(item, 0) + 1);
}
// key를 배열에 담아서 정렬한 후, 기존 배열(arr)에 해당인덱스의 갯수만큼 다시 삽입한다.
ArrayList<Integer> keyList = new ArrayList<>(map.keySet());
Collections.sort(keyList);
int idx = 0;
for (int key : keyList) {
int cnt = map.get(key);
while (cnt > 0) {
arr[idx++] = key;
cnt--;
}
}
}
3. 셸 정렬
- 삽입 정렬을 보완한 형태로
- 삽입 정렬은 idx 1부터 arr.length-1까지 처음부터 좌측의 데이터를 확인했다면
- 셸 정렬은 간격을 두고 간격의 거리만큼 떨어진 데이터를 확인하는 것을 반복한다.
- 이렇게 하게 되면 기존의 삽입 정렬 보다는 교환 횟수가 감소할 수 있다.
public static void shellSort(int[] arr) {
// 초기 gap을 설정
int gap = arr.length / 2;
// 더 이상 간격이 없을 때까지 간격을 /2한다.
for (int g = gap; g > 0; g /= 2) {
// 초기 간격부터 간격의 길이만큼 증가하면서
for (int i = g; i < arr.length; i++) {
// 지정된 위치의 좌측 간격들의 데이터를 비교 & 교환한다.
int tmp = arr[i]; // 짚은 데이터를 tmp에 넣고
int j = 0; // 짚은 데이터의 좌측 데이터들을 확인
for (j = i - g; j >= 0; j -= g) {
// 큰 값이 나오면 좌측 데이터들을 하나씩 당긴다
if (arr[j] > arr[j + g]) {
arr[j + g] = arr[j];
} else {
break;
}
}
arr[j + g] = tmp;
}
}
}
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
| 입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
구간합 범위를 구하는 식 : S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1 - 1][y1 -1]
⌨️ 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
// 입력
int N = Integer.parseInt(st.nextToken()); // 행의 길이
int M = Integer.parseInt(st.nextToken()); // 케이스 수
// 기존 배열 D
int[][] D = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
D[i][j] = Integer.parseInt(st.nextToken());
}
}
// 구간합 배열 S
int[][] S = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + D[i][j];
}
}
// 케이스당 하나씩 처리
// 범위 (x1, y1) ~ (x2, y2)의 구간합 구하기
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
int sum = S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1 - 1][y1 -1];
sb.append(sum);
sb.append("\n");
}
System.out.println(sb.toString());
}
}
회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.
여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.
| 입력
입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.
| 출력
각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static int isPanlindrome(char[] arr, int left, int right, int delCnt){
while (left < right) {
if (arr[left] == arr[right]) {
// 회문인 경우
left++;
right--;
} else {
// 회문이 아닌 경우
int l2 = left;
int r2 = right;
// 좌측 문자를 하나 삭제 후 확인
l2 += 1;
while (l2 < r2) {
if (arr[l2] == arr[r2]){
l2++;
r2--;
} else {
delCnt++;
break;
}
}
if (delCnt == 0) { // abca와 같이 좌측 제거 후 유사회문인 경우 고려
return 1;
}
// 우측 문자를 하나 삭제 후 확인
l2 = left;
r2 = right - 1;
while (l2 < r2) {
if (arr[l2] == arr[r2]){
l2++;
r2--;
} else {
delCnt++;
break;
}
}
// 좌우축 모두 확인 후에 delCnt를 반환
return delCnt; // 반환하지 x면 무한 루프
}
}
return delCnt;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while (T --> 0) {
String s = br.readLine();
sb.append(isPanlindrome(s.toCharArray(), 0, s.length()-1,0));
sb.append("\n");
}
System.out.println(sb.toString());
}
}
⌨️ 코드2 - 재귀
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
// 재귀로 풀 경우
public static int isPanlindrome2(char[] arr, int left, int right, int delCnt){
while (left < right) {
if (arr[left] == arr[right]) {
// 회문인 경우
left++;
right--;
} else {
// 처음 불일치한 경우
if (delCnt == 0) {
// 좌우측을 하나씩 삭제한 문자열이 회문인지 확인
if (isPanlindrome2(arr, left + 1, right, 1) == 0 ||
isPanlindrome2(arr, left, right - 1, 1) == 0) {
return 1;
} else {
return 2;
}
} else {
return 2;
}
}
}
return 0;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
while (T --> 0) {
String s = br.readLine();
sb.append(isPanlindrome2(s.toCharArray(), 0, s.length()-1,0));
sb.append("\n");
}
System.out.println(sb.toString());
}
}
이 과정을 계속하다보면, 64,37,58,89,145,42,20,4,16,37,58,89,145,42.... 이 나오게 되는데요.
- 어떤 수는 14처럼 '1이 아닌 중복되는 수'를 지점으로 무한히 동일한 수열이 반복되는 반면,
- 어떤 수는 제곱합의 끝이 1이 되면서 이후에는 1이 반복되어 나옵니다.
'행복한 수'는 이처럼 제곱합의 끝이 1이 나오는 수를 이야기합니다.
[ 행복한 수를 찾는 코드 ]
public static boolean isHappy(int n) {
// 중복된 지점부터는 저장X
HashSet<Integer> set = new HashSet<>();
while (set.add(n)) { //set이 이미 해당 값을 가지고 있을 때 false --> 루프탈출
// 각 자릿수의 제곱합
int sum = 0;
while (n > 0) {
sum += (int) Math.pow(n % 10, 2);
n /= 10;
}
// 합이 1이 나오면 행복한 수, 아니면 set에 add하고 중복수 있는지 확인
if (sum == 1) {
return true;
} else {
n = sum;
}
}
return false;
}
| 소수 구하기
소수는 자연수 N을 1부터 N까지 나누었을 때 나누어떨어지는 수가 오직 1과 자기자신 뿐인 수를 말합니다.
단순 구현을 하게 되면 아래와 같이 풀 수 있는데요
// 방법1. 2부터 N - 1까지 루프를 돌려 n을 나누어 본다.
public static boolean isPrimeNumber(int n) {
for (int i = 2; i <= n - 1; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
아래의 두가지 원리를 이용해서 위를 개선하면 아래와 같았어요.
(1) 2가 아닌 짝수는 절대 소수일 수가 없다는 점 - ex. 4, 6, 8, 10.. 모두 2로 나누어떨어지죠 (2) 홀수 N을 짝수인 수로 나누면 나누어떨어지지 않는다는 점 - ex. N이 125일 때, 나누어떨어지는 수는 1, 5, 125 > 이는 짝수인 수의 구구단을 생각하면 쉬웠어요. > 예를 들어, 4의 구구단은 4x1 = 4, 4 x 2= 8, 4 x 3 = 12.... 모두 짝수가 나와요. > 결국 짝수인 수를 다른 자연수로 곱해봤자 절대 홀수가 나올 수 없다는 의미이죠.
// 방법2. 수학적 원리 사용 - 2가 아닌 짝수는 소수가 아님
public static boolean isPrimeNumber2(int n) {
// 2가 아닌 짝수 여부
if (n != 2 && n % 2 == 0) {
return false;
}
// 3부터 홀수로만 나누어본다.
for (int i = 3; i <= n - 1; i+=2) {
if (n % i == 0) {
return false;
}
}
return true;
}
🛎 10434 행복한 소수
| 문제
Q. : 아래의 수열에서 다음에 올 수를 찾으시오.
313 331 367 ...
경복 : ??
강산 : 379.
경복 : 뭐?
강산 : 행복한 소수잖아.
경복 : 행복한 뭐?
강산 : 그러니까, 자리수의 제곱의 합을 구하는 연산을 계속 반복했을 때 1이 되는 수를 행복한 수라고 하잖아. 행복한 소수는 그 중 소수인 수이고.
7은 분명 소수이다. 과연 행복할까?
7 → 72= 49
49 → 42+ 92= 97
97 → 92+ 72= 130
130 → 12+ 32+ 02= 10
10 → 12+ 02= 1
7은 행복한 수이다 ☺.
사실 7은 행복한 소수 중 가장 작은 수이다. (이 문제에서는 1을 소수가 아닌 것으로 생각한다)
어떤 수가 주어지면 이 수가 행복한 소수인지 판정해보자.
| 입력
첫 줄에 테스트 케이스의 수 P가 주어진다. (1 ≤ P ≤ 1000)
각 테스트 케이스는 테스트 케이스 번호와 행복한 소수인지 판정해야 할 정수인 M으로 이루어져 있다. (1 ≤ m ≤ 10000).
| 출력
각 테스트 케이스마다, 테스트 케이스의 번호, 입력받은 수, 만일 M이 행복한 소수라면 YES 아니라면 NO를 공백으로 각각 구분하여 출력한다.
| 예제 입력
4
1 1
2 7
3 383
4 1000
| 예제 출력
1 1 NO
2 7 YES
3 383 YES
4 1000 NO
⌨️ 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
public class Ex10434 {
// 1단계 메서드 : 소수 확인 (단, 1은 소수가 아니다)
public static boolean isPrimeNumber(int n) {
// 탈출문1 : 1은 소수X
if (n == 1) {
return false;
}
// 탈출문2 : 2가 아닌 짝수는 소수x
if (n != 2 && n % 2 == 0) {
return false;
}
// 3 ~ N 까지 홀수로 나누어떨어지지 않는지 확인
for (int i = 3; i <= n - 1; i+=2) {
if (n % i == 0) {
return false;
}
}
return true;
}
// 2단계 메서드 : 행복한 수 확인
public static boolean isHappy(int n) {
// 중복수 확인용 set
HashSet<Integer> set = new HashSet<>();
while (set.add(n)) {
// 각 자릿수의 제곱합이
int sum = 0;
while (n > 0) {
sum += (int) Math.pow(n % 10, 2);
n /= 10;
}
if (sum == 1) {
// 1이면 행복한 수
return true;
} else {
// 아니면
n = sum;
}
}
// 중복수가 나온 경우
return false;
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int P = Integer.parseInt(br.readLine()); // 케이스 수
int[] allCase = new int[P];
// 모든 케이스 입력
while (P > 0) {
st = new StringTokenizer(br.readLine());
int idx = Integer.parseInt(st.nextToken()) - 1;
int num = Integer.parseInt(st.nextToken());
allCase[idx] = num;
P--;
}
// 각 케이스별 행복한 소수여부 확인
for (int i = 0; i < allCase.length; i++) {
System.out.printf("%d %d ", i + 1, allCase[i]);
if (!isPrimeNumber(allCase[i])){
System.out.print("NO\n");
continue;
}
if (!isHappy(allCase[i])) {
System.out.print("NO\n");
continue;
}
System.out.print("YES\n");
}
}
}
>> 구하려는 값이 나오기 위해서는 실제 인덱스 범위는 결국 (x1-2, x2-1)일 것이다.
이제 위 원리는 바탕으로 코드를 만들면 다음과 같다.
⌨️ 코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Ex11659 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(st.nextToken()); //수의 개수
int M = Integer.parseInt(st.nextToken()); //합을 구해야 하는 횟수
// 입력받은 수 배열
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
int num = Integer.parseInt(st.nextToken());
arr[i] = num;
}
// 합 배열을 구한다
int[] hap = new int[N];
for (int i = 0; i < N; i++) {
if (i == 0) {
hap[i] = arr[i];
continue;
}
hap[i] = hap[i - 1] + arr[i];
}
// 구간합을 구한다.
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int sum = 0;
if (x1 == 1) {
sum = hap[x2 - 1];
}else {
sum = hap[x2 - 1] - hap[x1 - 2];
}
bw.write(String.valueOf(sum));
bw.write("\n");
}
bw.flush();
bw.close();
}
}
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때,N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
| 입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
| 출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
| 예제 입력
216
| 예제 출력
198
🔎 문제분석
어떤 수 N의 분해합을 구하는 거라면 쉬웠을 텐데, 분해합의 가장 작은 생성자(=곧, 어떤 수 N)를 찾는 문제라 난해했다.
- 이 문제는 분해합과 생성자의 관계를 파악하려 하면 더 힘들었다. * 왜냐하면 생성자->분해합은 값이 하나로 떨어지지만 * 분해합->생성자를 구하는 건 결과값이 여러 개일 수 있기 때문이다. - 여기저기 알아보다보니 어차피 O(N) 속도라면, 1부터 1000000까지 돌리면서 분해합이 N인 경우를 찾기도 한 걸 봤는데, 아무리 O(N)이라지만, 백만개를 다 돌리는 건 비효율적일 것 같아 다른 방법을 찾아보았다
(1) N의 생성자의 최대값은 N - 1이다.
주어진 분해합 값 N의 범위는 (1 ≤ N ≤ 1,000,000)
==> 그렇다면 N의 생성자의 자릿수는 최대 6개 곧, 999,999가 된다. (생성자는 분해합 보다 적어도 1만큼 적을 것)
