알고리즘
-
팩토리얼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. 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..
-
백준 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..
-
백준 9012번 괄호 문제 풀이 Stack 활용 ( Java )Problem Solving/Java 2019. 9. 5. 11:03
9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc 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 4..
-
더 빠르게 입력받고 출력해보자 BufferedReader/BufferedWriterKnowledge/Java 2019. 9. 4. 22:11
알고리즘 문제를 풀 때 가장 좋은 입출력 방법은? (C, C++, Java ) ( https://takeknowledge.tistory.com/43 )에도 포스팅했지만 java에서 가장 빠르게 입벽받고 출력할 수 있는 방법은 BufferedReader 와 BufferedWriter를 사용하는거다. 입력 속도 비교 ( https://www.acmicpc.net/blog/view/56 ) 에 따르면 첫째 줄에 정수의 개수 N (= 10,000,000) 둘째 줄부터 N개의 줄에 한 개의 자연수(10,000 이하)가 적힌 파일을 입력받는데 java에서 무언가를 입력받을 때 주로 쓰는 Scanner는 4.8448초가 걸렸지만 BufferedReader, Integer.parseInt 를 활용했을 때는 0.6585..