프로그래밍 공부 노트

https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net 각 칸에 상어가 있는지 여부를 입력받으며 각 상어의 좌표를 저장한 뒤, 상어가 없는 칸에 대해 상어와의 거리의 최솟값을 계산해 각 최솟값의 최댓값을 출력한다. #include #define INF 0x3f3f3f3f #define MAX_N 50 struct coord { int _y = 0, _x = 0; }; int abs(int n) { return n < 0 ?..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 괄호를 중첩해서 사용할 수 없으므로, 각 연산에서 괄호를 사용할 경우 다음 연산에서는 괄호를 사용할 수 없다. 따라서 각 연산자에 대해, 해당 연산자에서 괄호를 사용한 경우와 사용하지 않은 경우를 재귀를 통해 계산해 각 계산의 최댓값을 구한 뒤 출력한다. #include // method[i]: i번째로 나온 연산자 char method[9]; // N: 수식의 길이, val[i]..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨집을 m개 골랐을 때 도시의 치킨 거리가 dist_m이라면, 여기서 치킨집을 하나 더 추가했을 때 도시의 치킨 거리 dist_(m + 1)은 dist_m보다 작거나 같다. 따라서 구하고자 하는 값은 치킨집을 M개 골랐을 때의 도시의 치킨 거리의 최솟값이다. 도시의 치킨 거리를 최소화하기 위해 치킨집을 고르는 방법은 특별히 알려진 게 없으므로, 가능한 경우를 모두 확인해보아..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 연구소의 빈 칸과 벽, 바이러스가 있는 칸을 노드로, 상하좌우로 인접한 노드 사이의 관계를 에지로 보면 이 문제는 그래프 탐색 문제로 볼 수 있다. 이 때 벽을 세 칸 세워야 하므로 브루트포스를 이용해 각 빈 칸에 벽을 세 개 세운 뒤 그래프 탐색을 실행해야 한다. #include #include using namespace std; typedef pair coord; #define MAX_N 8 #defin..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 별다른 테크닉 없이 순수 구현만으로 해결하는 문제이다. #include using namespace std; #define MAX_N 500 int N, M; short t[MAX_N + 1][MAX_N + 1]; // cmp3의 이름이 max일 때 ‘__comp’ cannot be used as a function 에러 발생 int cmp2(int a, int b) { return a > b ?..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 보드의 각 상태를 클래스의 형태로 저장한 뒤, 보드를 5회 이동시켜 얻을 수 있는 모든 상태를 탐색해야 한다. 이 때 가능한 블록의 최댓값은 초기 상태의 최댓값 혹은 블록이 합쳐져서 만들어진 블록의 최댓값이므로, 최댓값 계산은 보드의 초기 상태를 입력받을 때와 블록이 합쳐질 때만 실행하면 된다. #include #define MAX_N 20 #define init(i,..

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net algorithm에 있는 next_permutation을 이용해 모든 순열을 출력한다. #include #include using namespace std; int main() { // 입출력 속도 향상 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // N: 배열의 크기, arr: 미리 초기화한 배열 int N, arr[8] = { 1, 2, 3, 4, 5, 6, 7, 8 }; // N을 입력받은 뒤 next_permutat..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 체스에서 퀸은 상하좌우 혹은 대각선에 존재하는 모든 칸으로 움직일 수 있다. 따라서 체스판에 퀸 하나가 존재할 경우, 같은 행/열/대각선에는 퀸이 존재할 수 없다. 재귀를 이용해 퀸을 각 행마다 하나씩 차례로 놓는다고 하자. 퀸을 놓거나 없앨 때마다 해당 칸이 위치한 열/대각선에 퀸이 존재하는지 여부를 표시하고, 다음 행에 퀸을 둘 때 각 칸에 대해 열/대각선에 퀸이 없는 칸에만 퀸을 두고, 이 과정을 모든 행에..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 사람의 키와 몸무게를 저장할 클래스 person을 만든 뒤, person의 배열을 만들어 입력받은 각 사람의 정보를 배열에 저장한다. 이후 각 사람을 다른 사람과 비교해 그 순위를 출력하면 된다. 순서를 출력하는 문제이므로 정렬을 사용해도 될 거라 생각할 수 있지만, person a, b에 대해 a의 몸무게가 b보다 크고 a의 키가 b의 키보다 작을 경우, 정렬했을 때 인덱스에는 차이..

https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 1부터 10000까지 안의 모든 수 n에 대해, n이 범위를 벗어날 때까지 d(n)을 만들어 해당 수가 셀프 넘버가 아님을 표시한 뒤 n에 d(n)을 저장한다. 이후 생성자가 존재하지 않는 모든 수를 출력하면 된다. #include #define MAX 10000 int main() { // chk[i]: d(x) = i인 x가 존재한다면 true..