복습노트 복습노트

문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net n * n 체스판이 있을 때 한 칸씩 퀸이 들어가 n개의 퀸이 서로 공격하지 않을 경우의 수를 구하는 문제입니다. 퀸은 가로, 세로, 대각선 모두 이동 가능합니다. 이는 backtracking 기법으로 해결 가능합니다. 먼저 첫번째 칸에 퀸을 두고 두번째 칸에 체스를 두면서 서로 평행하거나 대각선에 걸리면 나머지 경우는 볼 필요가 없으므로 무시해주면 됩니다. 다음과 같은 경우는 퀸이 모두 공격하지 않으므로 가능합니다. 이는 퀸 배열을 통해서 나타낼 수 있습니다. queen..

문제 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 수열을 입력 받고 그 사이에 연산자를 끼워 넣어 계산한 값이 가장 크게 되는 수와 가장 작게 되는 수를 출력하는 문제입니다. 숫자의 갯수는 N이라 할때 연산자의 갯수는 항상 N-1 개입니다. 배열 arr는 수열의 수가 들어가는 배열입니다. 벡터 oper는 연산자가 들어가게 됩니다. 덧셈은 0, 뺄셈은 1, 곱셈은 2, 나눗셈은 3이라고 할때 예를들어 n은 6이고 덧뺄곱나 = 2 1 1 1 이라고 할떄 o..

문제 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 숫자를 입력받아 k 개의 숫자를 빼서 가장 큰 수를 출력하는 문제입니다. 문제는 간단하지만 구현하는게 생각이 많았습니다. int n, k; cin >> n >> k; string st; cin >> st; 먼저 숫자의 갯수 n 과 몇개를 빼는지 k를 입력받습니다. 숫자는 string으로 입력받는데 n의 범위가 500000까지 이기 때문입니다. vectorv; dequeq; q.push_back(st[0] - '0'); 벡터 v는 완성된 숫자를 넣어줄 공간입니다. 덱 q는 string으로 부터 숫자를 받아 저장할 임시 공간입니다. 먼저..

문제 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 친구들의 이름을 성적 순대로 입력 받고 성적 순위가 k이하로 되고 이름의 길이가 같은 친구의 수를 세는 문제입니다. 단순히 naive하게 이중 for문을 사용하면 시간복잡도가 O(n^2) 이 발생하기 때문에 다른방법을 생각해주어야 합니다. 따라서 입력받은 이름을 문자열의 길이로 변환해 QUEUE에 넣어줍니다. QUEUE는 가장 먼저 들어온게 맨 앞으로 가고 늦게 들어오면 뒤로 들어가므로 각각의 문자열의 길이에 맞는 QUEUE 배열 인덱스..

문제 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 예시의 그림처럼 각 기둥의 천장을 이어서 만든 넓이를 구하는 문제입니다. 스택을 이용하여 풀 수 도 있지만 다른 방법을 사용하여 풀어 보았습니다. 간단히 말하면 먼저 기둥 중에서 가장 높은 기둥을 구하고 그 기둥을 기준으로 양쪽으로 나누어 넓이를 따로 구해주었습니다. int n; cin >> n; vectorv(n); pair top = { 0,0 }; for (int i = 0; i > v[i].first >..

문제 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net c++ STL을 이용하면 매우 쉽게 구할 수 있지만 C언어로 구현하면 꽤 까다로운 문제 였습니다. C언어로 직접 코드를 다 구현해보는게 덱을 이해하는데 큰 도움이 되었습니다. 코드를 보겠습니다. void push_front(int a); void push_back(int b); int empty(); void pop_front(); void pop_back(); int deque[10001]; int cnt = 0; int front = 0;..

문제 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 자료구조 큐를 구현하는 문제입니다. c언어로 작성했는데 c언어로 하나하나 직접 구현해보면 큐를 이해하는데 도움이 많이 됩니다. 코드를 보겠습니다. int queue[10001]; int cnt = 0; int front = 0; int main() { int n; scanf("%d", &n); while (n--) { char ch[10]; scanf("%s", &ch); if (strcmp(ch, "push")==0) { int a; sca..

문제 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 스택을 구현하는 문제 입니다. 보통 스택은 c++ STL 로 편하게 사용가능합니다. 하지만 이번에는 C언어를 사용하여 처음 부터 끝까지 스택을 구현하는 코딩을 해봤습니다. 스택의 원리를 이해하는데 큰 도움이 되었습니다. 코드를 보겠습니다. int stack[10001]; int cnt = 0; int main() { int n; scanf("%d", &n); while (n--) { char ch[10]; scanf("%s", ch); if..