나그네

3111번: 검열 문제 https://www.acmicpc.net/problem/3111 3111번: 검열 첫째 줄에 단어 A가, 둘째 줄에 텍스트 T가 주어진다. A와 T는 알파벳 소문자로만 이루어져 있고, A는 최대 25자, T는 최대 300,000자이다. www.acmicpc.net 풀이 문자열 T의 왼쪽에서부터 탐색해 문자열 A가 있으면 제거하고, 오른쪽부터 탐색해서 또 있으면 제거, 또다시 왼쪽, 오른쪽,... 반복하며 더 이상 그 문자열 A를 찾을 수 없을 때 남아있는 문자열을 출력하는 문제다. front, back이라는 덱을 2개 사용했다. front는 문자열 T의 앞에서부터 차례대로 넣는 컨테이너고, back은 뒤에서부터 넣는 컨테이너다. 즉, front는 push_back와 pop_bac..

14941번: 호기심 문제 https://www.acmicpc.net/problem/14941 14941번: 호기심 첫 줄에는 질문의 개수 n이 주어진다. 다음 줄 부터 차례대로 함수의 입력 a, b가 주어진다. (1 ≤ a ≤ b ≤ 105) 또한 남규는 호기심이 많기 때문에 매우 많은 질문을 한다. 따라서 질문의 수 n은 최 www.acmicpc.net 풀이 a 이상 b 이하의 소수를 규칙에 따라 계산하는 간단한 문제다. 먼저 에라토스테네스의 체를 사용해 10^5보다 작은 소수를 걸러낸다. 소수를 하나하나 a보다 큰지 비교하다는 방법은 시간복잡도가 O(N)이고 10^5 이하의 소수는 약 41,000개 이상이고 테스트케이스의 수 N이 10^5이기 때문에 시간초과가 난다. 따라서 prime 배열은 이미 ..

17215번: 볼링 점수 계산 문제 https://www.acmicpc.net/problem/17215 17215번: 볼링 점수 계산 첫째 줄에 각 기회마다 소현이가 쓰러뜨린 볼링핀의 개수가 공백없이 주어진다. 이때 스트라이크는 S, 스페어는 P, 핀을 하나도 못 쓰러뜨린 것은 -으로 주어진다. www.acmicpc.net 풀이 시키는 대로 구현하는 문제다. 볼링에 대한 규칙을 아는 사람이라면 문제도 안 읽고 쉽게 풀 수 있을 것 같다. 문자열의 각 문자를 탐색하며 숫자일 경우 점수를 더하고, P(스페어)인 경우 (10 - 이전 투구에서 친 점수)를 추가하고 다음 투구의 점수도 더해준다. S(스트라이크)인 경우 10점을 추가하고 다음 두 번의 투구 점수를 함께 더해준다. 여기서 주의할 점은 10프레임에 ..

17071번: 숨바꼭질 5 문제 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 수빈이(편의상 누나)는 다른 숨바꼭질 문제들처럼 +1, -1, ×2로 이동 가능하고 시간은 1초 걸린다. 대신 동생이 1초에 1칸, 2초에 2칸,... N초에 N칸씩 움직인다. 따라서 BFS 알고리즘을 사용해서 풀 수 있다. 처음 접근 방식은 각각에 대해 BFS를 하며 (동생은 사실 하나만 이동하지만) 시간 단위로 이동하고..

1543번: 문서 검색 문제 https://www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 풀이 문서와 단어를 입력받아 문서 내에 단어를 중복되지 않게 몇 개 셀 수 있는지 구하는 문제다. 문서의 가장 처음 인덱스(0)부터 단어와 비교를 하고 다르면 다음 index로 넘어간다. 만약 단어를 찾으면 카운트를 증가시키고 다음 탐색할 문서의 위치를 현재 위치에서 단어의 길이만큼 더해준다. 코드 #include using namespace std; int main() {..

1463번: 1로 만들기 문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍(DP)으로 해결할 수 있는 문제다. 할 수 있는 연산은 아래와 같다. 3으로 나누어 떨어지면 3으로 나누기 2로 나누어떨어지면 2로 나누기 1 빼기 bottom-up 방식으로 구현했다. 1은 0번의 연산으로 1을 만들 수 있다. 2 이상의 수는 기본적으로 i번째 수는 이전 수에서 1을 더한 수이므로 dp[i] = dp[i-1] + 1이다. 만약, i번째 수가 3의 배수라면 i/3에서 3을 곱한 수일 것이다. 따라서 dp[i] = dp[i/3] + 1일 '수..

1456번: 거의 소수 문제 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 풀이 거의 소수는 소수의 N제곱 형태인 수를 말한다. 범위 내 거의 소수의 개수를 구하는 문제다. 수의 범위가 10^14이고 N제곱 형태를 구하므로 에라토스테네스의 체를 사용해 10^7까지의 소수만 구해준다. 소수를 i라고 한다면 i^2 = i × i부터 범위에 포함된다면 카운트를 증가시켜 주면 된다. 단, 범위 판단에 주의해야한다. 현재 수의 +1승이 범위 내인지 확인하려면 (..

1436번: 영화감독 숌 문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 풀이 666이 들어간 수를 종말의 숫자라 한다. 수를 증가시켜 가며 수에 종말의 숫자인지 확인한다. N번째 종말의 숫자를 출력하는 문제다. 1000으로 나눈 나머지가 666이면 카운트를 증가시키고 다음 수를 확인한다. 666이 아니라면 10으로 나눠주어 마지막 자리 수를 버리고 다시 탐색한다. 이를 0이 될 때까지 반복해 종말의 숫자인지 확인한다. 코드 #inclu..

27648번: 증가 배열 만들기 문제 https://www.acmicpc.net/problem/27648 27648번: 증가 배열 만들기 첫째 줄에 $N$, $M$, $K$가 주어진다. $\left(1 \le N , M \le 1\,000,1 \le K \le 100\,000 \right)$ www.acmicpc.net 풀이 맨 왼쪽 위부터 맨 오른쪽 아래 칸까지 이동하는데 각 칸의 수가 증가하도록 구성해야 한다. 이 배열을 만들 수 있는지 여부와 만들 수 있다면 가능한 것 중 하나를 출력하면 된다. 대각선을 왼쪽 위부터 오른쪽으로 차례대로 1, 2, 3,...으로 증가시키도록 구성하면 된다. ex) 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 실제 배열을 만들 필요도 없이 출력할 수 있다. 맨..

12020번: LU 분해 문제 https://www.acmicpc.net/problem/12020 12020번: LU 분해 \(N \times N\) Matrix A가 주어진다. LU 분해란 \(A = LU\)꼴의 Matrix 곱로 분해하는 것이다. (단, \(L\)은 Lower Triangular Matrix, \(U\)는 Upper Triangular Matrix) Lower Triangular Matrix란 \(L_{ij} = 0 \text{ (if }i < j\text{)}\) Upper www.acmicpc.net 풀이 선형대수학에서 배우는 LU 분해를 구현하는 문제다. 구현 자체는 LU 분해를 하는 방식대로 하면 된다. LU 분해에 대해선 설명 잘해놓은 다른 블로그를 참고하는 게 좋을 것 같다..