Algorithm Cinema

6588번: 골드바흐의 추측 (acmicpc.net) 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 주어진 짝수를 소수의 합으로 표현하는 문제이다. 1. 시간 제한 0.5 매우빡시다. 일단 test case는 10만번 이하이고 짝수는 100만이하이다. 2. 가장 효율적인 알고리즘 > 에리토스테네스.. 이를 활용하고 플러스 메모이제이션을 활용해서 배열을 하나만 만들것이다. 즉, 짝수의 max범위가 100만이니 우리는 100만까지만 관찰하면 된다. 따라서 100만짜리의 크기의 소수판별 배..

1929번: 소수 구하기 (acmicpc.net) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net m 이상 n이하의 소수를 출력해야함 range는 100만 이하. 시간 제한은 2초이다. 1. 소수를 판별하는 알고리즘 뭐 냅다 i=2부터 몇까지 나머지 있으면 false이런식으로 하는것도 있지만 시간적으로 효율적이지 않아서 웬만하면 에라스토텔레스의 체라는 알고리즘을 활용한다. i=2부터 n까지가 아닌 n의 제곱근까지만 search 해도 괜찮다. public static boolean isPrime(int num) { if(num 제곱근까지만 검..

11656번: 접미사 배열 (acmicpc.net) 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다. 얘를 사전순으로. 1. 인덱싱으로 잘라서 배열에 넣은 다음 (ArrayList)활용 2. sort하면 끝날거같다. 3. 부분 문자열 >> 웬만하면 자바의 편한 substring 메소드를 활용하자 import java.io.*;..

11655번: ROT13 (acmicpc.net) 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다. 1. 알파벳은 13개씩 밀어서 출력하고 나머지 알파벳이 아닌 녀석들은 그대로 출력 2. 아스키코드로 필터링하고 조건문으로 13개씩 미는것을 다뤄야한다. 당연하겠지만 알파벳은 26가지 인데, 만약 A라는 녀석은 13번째 뒤인 알파벳이 있지만 Z는 없고 그 전 껄로 돌아간다. 따라서 해당 문자..

10809번: 알파벳 찾기 (acmicpc.net) 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. 알파벳이 나타남에 따라 문자열 내에서 처음 등장하는 위치(인덱스)를 a b c d e f .. 순으로 표기하는 알고리즘이다. ..

17298번: 오큰수 (acmicpc.net) 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4,..

10799번: 쇠막대기 (acmicpc.net) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 닫는 괄호와 여는 괄호를 중심으로 문제를 해결해야하는 문제. - 이 괄호 꺾쇠를 보면 이젠 습관적으로 스택을 떠올리게 된다. 이 문제 역시 스택으로 풀었어야했다. 난 처음에 어느 괄호를 기준으로 잡아야할지 감이 안와서 잘 못 풀었었다. 뭐 크게 경우는 두가지 이지만, 연속될 경우를 잘봐야 한다. 접근. 1. (( / () / )) / )( / 총 4가지의 연속경우가 있으니 이를 잘 참고해야겠다. ()인 경우 레이저를 표시하기에..

17413번: 단어 뒤집기 2 (acmicpc.net) 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, ''일때 닫는 꺾쇠이기에, tag type > false & >도 ..

1158번: 요세푸스 문제 (acmicpc.net) 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)- 요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램. 1. 원을 이루면서 앉..

1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 명령어 4가지를 통해 문자열을 control해보는 문제. 커서를 활용하는 특이한 문제다. 특이한 점은 시간제한이 빡세다 0.3초.. 첫번째 접근. 그냥 stringBuilder와 인덱싱 활용해서 풀기, - 답은 맞게나오나, 성능이 o(n)으로 낫배드나, 0.3초라 시간제한에 걸렸다 두번째 접근 커서 활용 >> LinkedList의 ListIterator로 문제 해결하기. 얘는 시간제한에 안걸리고 풀었다 iterator의..