나그네

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 분해에 대해선 설명 잘해놓은 다른 블로그를 참고하는 게 좋을 것 같다..

4179번: 불! 문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 풀이 재민이가 불을 피해 가장자리로 가서 탈출할 수 있으면 탈출하는 최단 시간을, 탈출할 수 없으면 IMPOSSIBLE을 출력하는 문제다. 틀린 풀이 BFS를 시작할 때 재민이는 1부터 시작하고 불은 1001부터 시작하도록 해서 재민이 먼저 이동, 그다음 불이 이동하도록 했다. 이동할 때마다 visited 배열 값이 1씩 증가하도록 해서 시간을 계산했다. 큐..

5719번: 거의 최단 경로 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 정점의 수와 단방향 간선들이 주어지고 시작점, 도착점이 주어질 때 최단 경로가 아닌 경로들 중 가장 짧은 경로의 길이를 구하는 문제다. 다익스트라 알고리즘을 주로 사용한다. [다익스트라 알고리즘 알아보기] 먼저 다익스트라 알고리즘으로 최단 경로를 구해준다. 이 경우 시작점부터 각 정점까지의 최단경로가 모두 구할 수 있다. 이제 ..

1188번: 음식 평론가 문제 https://www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 풀이 소시지의 개수 N과 평론가의 수 M을 입력받고 소시지 N개를 모두 균등하게 나누어 평론가 M명에게 같은 양을 나누어 준다. 이때 소시지를 자르는 횟수를 구하는 문제다. 소시지를 일자로 세우고 M등분하면 된다. 이때 칼질의 횟수는 M-1번이 된다. 그러나 이미 소시지는 N개를 일자로 나열한 것이므로 N등분되어있다. 따라서 중복으로 잘리는 횟수를 구해 빼주면 된다. 중복인 칼질의 수는 (N과 M의 최대공약수) - 1 이므로 정답은 M - gcd(N, M)이다. 코드 #..

2660번: 회장뽑기 문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 어느 회원이 다른 모든 회원과 연결연결되어 있으면서 점수가 가장 작으면 회장 후보가 된다. 회장 후보가 되기 위한 점수와 회장 후보의 수, 그리고 누가 회장 후보인지 구하는 문제다. 각 회원 간 관계를 구해야 하므로 플로이드-워셜 알고리즘을 사용해 가장 친구의 친구의 친구의... 인 관계를 구한다. 각 친구 관계를 입력받아 양방향 간선 형태로 연결해 준다. 각 회원..

4716번: 풍선 문제 https://www.acmicpc.net/problem/4716 4716번: 풍선 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 다음 N개 www.acmicpc.net 풀이 각 팀에 필요한 풍선의 개수와 창고 A, B까지의 거리가 주어지면, 가장 효율적으로 창고에서 꺼내서 전달할 때 이동 거리를 구하는 문제다. 처음엔 각 팀이 주어질 때마다 A가 더 가까우면 A에서 양만큼 꺼내주고 충분하지 않으면 B에서 더 꺼내주도록 했다. 반대로 B가 더 가까울 때도 마찬가지. 그러나 틀렸습니다를 받았다. 다음으로 접근한 방..

2617번: 구슬 찾기 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 풀이 N개의 구슬들의 무게를 비교한 정보가 M개 있을 때, 이를 가지고 무게가 중간일 수 없는 구슬의 수를 구하는 문제다. 기본적인 개념은 i번 구슬보다 무거운 구슬의 수나 가벼운 구슬의 수가 N/2보다 크면 그 구슬은 중간일 수 없다. 따라서 각 구슬 간의 무게를 모두 비교하기 위해 플로이드-워셜 알고리즘을 사용했다. 무게 관계 a, b는 a가 b보..