프로그래밍 공부 노트

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2차원 배열의 특정 성분을 재귀를 통해 접근하는 문제이다. N * N 크기의 배열을 (N / 2) * (N / 2) 크기의 네 배열로 쪼개서 위치에 따라 값을 더하는 과정을 N이 1이 될 때까지 반복하면 쉽게 해결할 수 있다. #include int main() { // r, c: Z수의 좌표, quat: 가중치를 설정할 변수 int r, c, quat; // N: Z수 배열의 크기, a..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 한 자리 수와 두 자리 수는 각 자리 수의 차가 일정하므로 반드시 한수이다. 또 세 자리 수는 브루트포스로 판정이 가능하고, 1000은 한수가 아님이 자명하므로 입력이 두 자리 수 이상이라면 브루트포스로 정답을 출력할 수 있다. #include int main() { // input: 한수의 개수를 계산할 범위, ans: 범위 내의 한수의 개수 int input, ans = 99; scanf("%d"..

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 기타줄을 구매하는 방법은 세 개가 있다. 기타줄 팩만 구매하는 방법, 낱개 기타줄만 구매하는 방법, 낱개 기타줄은 5개 이하로 구매하고 나머지는 팩으로 구매하는 방법. 이 이외의 방법은 효율이 떨어지므로 이 세 방법을 모두 계산해 최솟값을 출력하면 된다. #include #define MAX 0x3f3f3f3f int min(int a, int b) { return a < b ? a : b; ..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 각 파티를 그래프, 파티에 참여하는 사람을 노드, 서로 만난 사람의 관계를 에지, 처음에 진실을 아는 사람을 탐색 시작 노드로 치환하면 이 문제는 그래프 탐색 문제가 된다. 우선 진실을 아는 사람, 그러니까 탐색을 시작할 노드 번호를 입력받고 파티, 그러니까 연결되지 않은 그래프를 입력받아 저장한다. 그리고 탐색 시작 노드로부터 각 그래프에 대해 탐색을 진행하면 탐색한 그래프와 탐색하지 않은 그래프로 나뉘게..

https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 정육면체를 만들었을 때, N이 1이라면 모든 면의 수 중 가장 큰 수를 제외한 면이 모두 드러나므로 드러난 면의 수를 모두 더해 출력하면 된다. N이 1보다 크다면, 주사위에서 실질적으로 쓰이는 면은 세 종류이므로 서로 마주한 면 중 더 작은 면만 사용하면 된다. 또한 정육면체의 각 면을 다음과 같이 구분하면, 주사위의 종류를 면을 이루는 주사위, 모서리를 이루는 주사위, ..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 배열 A = B = [1, 2, ... , 10]에 대해 배열곱을 진행해 보자. A와 B 둘 다 오름차순으로 정렬되어 있다면 결과는 1 + 4 + 9 + .. + 100 = 385가 될 것이고, A와 B가 각각 오름차순 / 내림차순으로 정렬되어 있다면 결과는 10 + 18 + ... + 18 + 10 = 220이 될 것이다. 이처럼 배열곱을 최소화하기 위해선, 두 배열 A와 B를 서로 다른..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 주어진 문제에서 2번 연산을 k번 하는 것은 3번 연산을 N - k번 하는 것과 같다. 또 2번 연산은 큐의 맨 앞 원소를 push한 뒤 큐에서 원소를 pop하는 것으로 볼 수 있기 때문에, 이 문제는 큐를 이용해서 간단하게 풀 수 있다. #include #include using namespace std; int min(int a, int b) { return a < b ? a : b; } ..

https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 입력의 범위가 1부터 10^9이므로, 1부터 N까지 모든 수를 하나하나 세어가면서 진행하면 시간 초과가 발생하게 된다. 따라서 이 문제는 N을 (10 ^ k)의 자리에 대해 해당 자리의 수 mid와 mid의 좌우에 있는 두 수 left와 right를 이용해서 해답을 찾아내야 한다. 해답만 먼저 말하자면, (10 ^ k)의 자리에 임의의 수 i가 올 수 있는 경우의 수는 다음과 같다. i (left + 1 - (i == 0)) * log i == mid => (le..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 잠시 체스판의 색 배치를 보자. 이미지의 a~h를 1~8로 치환해서 보면, 이미지의 i번째 행 / j번째 열의 색은 i + j가 홀수인지 짝수인지에 따라 결정된다. 따라서 체스보드 판의 색을 칠하기 위해선, 체스판의 i번째 행 / j번째 열의 색을 i + j에 따라 흰색 혹은 검은색으로 칠하면 된다. #include #define MAX 50 // board[i][j]: (i, j) 칸이 ..

https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 제곱ㄴㄴ수가 몇 www.acmicpc.net 에라토스테네스의 체를 응용한 문제이다. 에라토스테네스의 체는 1차원 배열의 모든 인덱스에 대해, 소수임을 나타내는 값을 발견하면 그 인덱스에 정수배를 한 모든 인덱스의 값에 소수가 아님을 나타내는 값을 할당한다. 마찬가지로, 이 문제에서는 모든 인덱스에 대해 제곱 ㄴㄴ 수임을 나타내는 값을 발견하면, 그 인덱스에 정수배를 한 모든 인덱스의 값에 제곱 ㄴㄴ 수가 아님을 나타내는 값을..