곽로그

문제 www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net check * 두번째 풀이 외우기 1. 처음 푼 풀이 (단순재귀) - 모든 경우의 수를 재귀를 이용해서 풀었다. - 이때의 시간 복잡도는 모든 수가 3, 2로 나누어 떨어진다고 했을때 하나의 함수가 3개의 함수를 호출하게 된다. 따라서 3의 N-1 제곱이 되고 입력의 최대는 10의 6제곱이니까 시간초과가 나게 된다. check - 위 문제는 최소의 값을 구하는 거다. 따라서 함수를 호출하였을때 연산횟수가 이전에 호출했던 함수의 연산횟수보다 크면 다시 호출할 필요가 없다. 위의 경우에 (2,1)을 호출했으면 (2,3)을 ..

문제 www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 풀이 1. 1부터 1,000,000까지 소수를 구한다(에라토스테네스의 체 이용) 2. 입력(num)으로 0이 나오기 전까지 반복문을 수행한다 2-1 1번에서 구한 소수배열(isPrimeNum)을 순회(n)하면서 n, num-n이 모두 소수일때 반복문을 종료한다 check 1. 에라토스테네스의 체의 시간복잡도는 nlog(log n)이다. 따라서 1,000,000인경우 근사값 778,1..

문제 www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net check 1. 소수의 정의를 이용하여 3가지로 풀 수 있다. 2. isPrimeNum3에서 두번째 for문에 n

문제 www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net check 1. 어렵게 보인다, 복잡해 보인다 라는 생각이 들면 어짜피 못풀거다 라는 생각에 생각하기를 멈춘다. 따지고 보면 그렇게 어려운게 아닌데 지레짐작해서 포기해버린다. 2. 예전 코드를 보니 '소수는 귀찮다'라는 생각에 풀다 안 푼 흔적이 있다. 3. 막상 해보면 별거 아니다. 소스코드 package november.first; import java.io.BufferedReader; import java.io.BufferedWri..

문제 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 1. 순회 (시간초과) - 오큰수를 순회로 풀면 시간 초과가 난다. 즉 수열을 순회하면서 index번째 수의 오큰수를 구할 때, 다시 index+1 부터 순회를 하게되면 시간 복잡도는 N제곱이 되어서 시간초과가 난다. 2. 스택이용 - A의 오큰수 B를 구하는 게 아닌, B가 어떤 수의 오큰수가 되는지를 역으로 구해야한다. - B가 A의 오큰수이면 A와 B사이의 수 중에서 B가 가장 큰 수인 것을 이용한다. - 스..

문제 www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net check 1. 천천히 꾸준히 2020년 1월에 푼 쇠막대기를 보니 이 문제를 왜 어려워했나 하는 생각이 든다. 천천히 꾸준히 하다보면 지금 어려워 하는 문제도 언젠간 쉬워지겠지 2. 구분 같은 괄호라도 상황에 따라 역할이 다르다. )의 경우 바로 앞 괄호가 (이면 레이저이고 아닌 경우 나무의 끝이다. )의 두가지 상태에 따라 구현을 다르게 하면 된다. 3. 다시풀기 종종 예전에 풀었던 문제를 다시 풀어야겠다. 얼만..

문제 www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net check 1. String과 StringBuilder - 처음에는 String을 사용해서 구현을 했는데 시간초과가 났다. 시간복잡도를 계산했을 때, 모든 문자열이 스택에 push 되었다가 pop되니까 O(2N)이라고 생각했다. 그래서 시간초과가 나는게 의아했다. - String을 사용했을때에 문제는 String을 이용한 연산때문에 시간초과가 난다는 거다. String에대한..

문제 www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net check 1. 배열을 이용한 풀이에서 시간 초과가 나는이유 - 배열을 이용하게 되면 수정과 삭제를 할때 배열의 최악의 경우 길이만큼의 시간이 필요하다. (맨 앞요소를 삭제하는 경우, 인덱스 1부터 N-1까지를 0부터 N-2 까지 옮겨야 한다) - 문제의 최대 입력(N)은 100,000 이고 수행 명령(M)은 최대 500,000이다. - 따라서 시간 복잡도는 NM = 50,000,000,000 500억인데 ..