백준
-
백준 17298번 오큰수 문제 스택 활용 풀이 ( Java )Problem Solving/Java 2019. 10. 20. 21:44
17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 그 숫자의 오큰수에 해당하는 수를 구하는 것이 아닌 그 숫자가 어떤 수의 오큰수의 해당하는가로 접근하는 아이디어 자체를 생각못해서 헤맸다. 그 방법을 알게 되고도 스택에 index대신 값을 저장하는 방식을 택해 또 한참 헤맸다 여러모로 어려웠던 문제.. 나는 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 4..
-
백준 10799 쇠막대기 문제 풀이 Stack 활용 ( Java )Problem Solving/Java 2019. 10. 20. 14:53
10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과 www.acmicpc.net 괄호 대신 index를 저장할 생각을 얼른 못해서 한참 헤맸다.. 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 ..
-
백준 17413 단어 뒤집기2 문제 풀이 Stack 활용 ( Java )Problem Solving/Java 2019. 10. 19. 11:33
17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '') { // 태그 종료일 때 tag = false; // tag 안인지 확인하는 flag를 false로 바꾸고 bw.write(s.charAt(i)); // 그 단어 그대로 출력 } else if (tag) { // 태그 안일 경우 bw.write(s.charAt(i)); // 그 단어 그대로 출력 } else { // 태그 바깥일 경우 if(s.charAt(i)..
-
다이나믹 프로그래밍 ( 동적 계획법 )Knowledge/Algorithm 2019. 9. 6. 16:38
- 다이나믹 프로그래밍이란 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 당연히 큰 문제를 작은 문제를 나누는 것과 다이나믹은 아무런 관련이 없다 이 용어를 처음 사용한 Richard Bellman은 그냥 '다이나믹'이 멋있어 보여서 사용했다고..ㅋ 다이나믹 프로그래밍으로 풀 수 있는 문제는 두가지 속성을 만족해야 한다. 1. Overlapping Subproblem ( 겹치는 부분 문제 ) : 큰 문제를 여러개의 부분 문제로 나누어서 풀 때 부분 문제간의 중복이 발생 가능해야 한다. 2. Optimal Substructure ( 최적 부분 구조 ) : 문제의 정답을 작은 문제의 정답을 통해 구할 수 있어야 한다. 예를 들어 대전에서 부산을 갈 때 최적의 루트가 대구를 거치는 거..
-
팩토리얼Knowledge/Math 2019. 9. 6. 14:40
팩토리얼은 1부터 그 수보다 작거나 같은 수를 모두 곱한 값이다 예를 들어 5의 팩토리얼은 5! 라 표시하고 1 * 2 * 3* 4* 5 해서 120이 된다. 즉 팩토리얼은 매우 큰 값이 나오게 되어 있어서 팩토리얼 자체를 구하는 문제보단 팩토리얼 값에 있는 0의 갯수를 정하는 식의 문제가 나온다. 근데 물론 팩토리얼 값을 구하고 거기서 0의 갯수를 새는 건 의미가 없으니 다음과 같은 방법을 사용할 수 있다 팩토리얼 값을 소인수 분해해봤을 때 0이 나오는 건 10 그러니까 2와 5를 곱했을 경우에만 가능하기 때문에 소인수 분해했을 때 나오는 5의 갯수가 곧 팩토리얼 값의 0의 갯수와 같다. 이걸 구현할 때는 물론 팩토리얼 값을 구해서 소인수분해를 직접해보는 건 이렇게 값을 우회해서 구하는 의미가 없는 일..
-
백준 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..