전체 글
-
팩토리얼Knowledge/Math 2019. 9. 6. 14:40
팩토리얼은 1부터 그 수보다 작거나 같은 수를 모두 곱한 값이다 예를 들어 5의 팩토리얼은 5! 라 표시하고 1 * 2 * 3* 4* 5 해서 120이 된다. 즉 팩토리얼은 매우 큰 값이 나오게 되어 있어서 팩토리얼 자체를 구하는 문제보단 팩토리얼 값에 있는 0의 갯수를 정하는 식의 문제가 나온다. 근데 물론 팩토리얼 값을 구하고 거기서 0의 갯수를 새는 건 의미가 없으니 다음과 같은 방법을 사용할 수 있다 팩토리얼 값을 소인수 분해해봤을 때 0이 나오는 건 10 그러니까 2와 5를 곱했을 경우에만 가능하기 때문에 소인수 분해했을 때 나오는 5의 갯수가 곧 팩토리얼 값의 0의 갯수와 같다. 이걸 구현할 때는 물론 팩토리얼 값을 구해서 소인수분해를 직접해보는 건 이렇게 값을 우회해서 구하는 의미가 없는 일..
-
소수Knowledge/Math 2019. 9. 6. 13:23
소수란? 소수란 약수가 1과 자기 자신 밖에 없는 수다 소수와 관련된 알고리즘은 두가지가 있다 1. 어떤 수 N이 소수인지 아닌지 판별하는 방법 2. N 이하의 모든 자연수 중에서 소수를 찾아내는 방법 나누어서 알아보자 1. 어떤 수 N이 소수인지 아닌지 판별하는 방법 소수란 약수가 1과 자기 자신 밖에 없는 수니 2 이상이고 자기 자신보다 작은 수로 나누어 떨어지면 안된다. 이런 특성을 코드로 표현하면 아래와 같다 1 2 3 4 5 6 7 8 9 10 11 12 bool prime(int n) { if (n
-
나머지 연산Knowledge/Math 2019. 9. 5. 20:54
알고리즘 문제를 풀다보면 정수형으로 표현하기엔 너무 큰 값이 나올 때가 있다. 이럴 경우엔 크기를 줄이기 위해 특정 숫자로 나눈 나머지를 출력하라는 식으로 답을 요구하곤 한다. 이럴 때는 답을 다 구하고 나머지 연산을 수행하는 게 아니고 정답을 갱신할 때 마다 나머지 연산을 수행해 줘야 한다. ( A + B ) % M 은 ( ( A % M ) + ( B % M ) ) % M 과 같기 때문 이는 곱셈에서도 ( A X B ) % M 은 ( ( A % M ) X ( B % M ) ) % M 이와 같이 성립한다. 다만 나누기의 경우엔 성립하지 않고 뺄셈의 경우엔 주의해야 하는 부분이 있다. 예를 들어 (6 - 5) % 3 은 1. 즉, 1 % 3은 1이 나오지만 (6%3 - 5%3) % 3 은 (0-2) % 3..
-
큐에 대해 알아보자Knowledge/Data Structure 2019. 9. 5. 18:24
- 큐란? 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 구조 먼저 넣은 것이 가장 먼저 나오기 때문에 FIFO ( First In First Out) 라고도 한다 - 주로 사용하는 메소드 ( Java ) push, pop, front, back, empty, size가 있다고 하는데 그건 C나 C++ 얘기인 것 같고 자바에서 LinkedList로 큐를 구현했을 경우는 - isEmpty() : 비어있는지 확인 - offer() : 큐의 뒤에 값을 입력한다 - poll() : 큐의 가장 앞에 있는 값을 꺼내고 반환한다 - peek() : 큐의 가장 앞에 있는 값을 확인만 한다 - 구현 이 역시도 백준 큐 구현 문제 ( https://www.acmicpc.net/problem/10845 ) 에 ..
-
백준 1158번 조세퍼스 문제 큐 활용 풀이 ( Java )Problem Solving/Java 2019. 9. 5. 18:11
1158번: 조세퍼스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 import java.io.*; import java.util.LinkedList; import java.util.Queue; public class Main { public stat..
-
백준 1406번 에디터 문제 Stack 활용 풀이 ( Java )Problem Solving/Java 2019. 9. 5. 15:46
1406번: 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 www.acmicpc.net 처음엔 ArrayList를 활용해서 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..
-
백준 1874번 스택 수열 문제 풀이 Stack 활용 ( Java )Problem Solving/Java 2019. 9. 5. 12:40
1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394import java.io.*;import java.util.S..