복습노트 복습노트

문제 2026번: 소풍 만약 K명의 친구 관계인 학생들이 존재하지 않는다면 -1을 출력한다. 그 외의 경우에는, K개의 줄에 학생들의 번호를 증가하는 순서로 한 줄에 한 개씩 출력한다. 여러 경우가 존재한다면 첫 번째 www.acmicpc.net 총 학생수 n명 중에서 f개의 친구관계를 바탕으로 k명의 학생을 뽑아 소풍을 데려가는 문제입니다. 1. 먼저 한 학생을 대상으로 그 친구관계를 살펴봅니다. 2. 대상 학생의 친구의 친구 관계를 살펴보고 대상 학생과 친구가 될 수 있는지 살펴 봅니다. 2를 반복하다가 조건이 안맞으면 1의 대상학생을 다시 선택해 반복해 주면 됩니다. 여기서 friend_num[] 이라는 배열을 설정해줄건데 friend_num[3] = 4 라는 의미는 3번 학생이 4명의 친구를 가진..

문제 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 주어진 스도쿠를 완성시키는 문제입니다. 들어갈 수 의 가로와 세로 그리고 포함된 미니 박스에 중복된 수가 없어야 합니다. 이를 위해서 boolean 형으로 체크할 필요가 있습니다. 그래서 총 3개의 불린형 2차원 배열을 설정해줍니다. ex) garo[5][8] = true : 가로 5번째 줄에 8이 존재 sero[5][8] = false : 세로 5번째 줄에 8이 존재하지 않음 box[5][8] = false : 5번째 미니 박스에 8이 존재하지 않음..

문제 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제의 관건은 팀을 2개로 나누는 여러가지 조합에대해서 처리해주어야하는 것입니다. 여기서 포인트는 중복이 아니라 조합이라는 것입니다. 1, 2, 3, 4 중에서 start 팀 = (1, 2) link 팀 =(3, 4) 과 start 팀 = (3, 4), link 팀 =(1, 2) 는 2가지가 아니라 1가지로 취급하는 것입니다. int n; int arr[21][21]; bool check[21]; int ans = INT_MAX; void dfs(int cur, int nex..

문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 수열의 갯수 n과 부분수열의 합 s가 주어지면 수열의 부분수열의 합이 s가 되는 경우의 수를 모두 구하는 문제입니다. 예를 들어 수열이 {-2, 5, -3} 인경우 부분수열의 갯수는 총 8개 입니다. {-2}, {5}, {-3}, {-2, 5}, {-2, -3}, {5, -3}, {-2, 5, -3}, ⊙(공집합) 따라서 모든 부분집합에 대해서 각 부분집합의 합이 s와 같은지 보면 됩니다. 부분수열을 이루는 경우는 1) ..

문제 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..

Brute Force 가능한 모든 해의 후보를 체계적으로 나열한 뒤, 각각의 후보가 진짜 답인지를 차례대로 확인하는 방법 예를 들어 어떤 수 N을 소인수분해 하는 과정을 모두 출력하는 프로그램을 구현한다고 가정하면 다음과 같은 코드를 짤 수 있습니다. int N; void chk(int i); int main() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); cin >> N; for (int i = 2; i

Latch latch는 일시적인 저장 장치 입니다. (2가지 상태로 되어있습니다) 출력이 반대쪽 입력으로 연결되어 있습니다. 왼쪽의 latch는 input이 active-HIGH (SET-RESET) Latch 입니다. NOR gate로 이루어져 있습니다. 오른쪽의 latch는 input이 active-LOW (SET-RESET) Latch 입니다. NAND gate로 이루어져 있습니다. 각 게이트의 출력이 반대쪽 게이트의 입력에 연결됩니다. 이것은 입력과 출력이 연결되어있어 연속 을 가지고 있습니다. 1. input들과 Q 출력 둘다 HIGH 이면 기본상태입니다. 2. Q 출력으로 부터 R' 인풋이 HIGH이면 G2의 출력은 LOW 입니다. 3. G2 의 출력이 LOW가 G1의 입력으로 들어가므로 G1..