IT세상

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 해결 방법 k를 차례로 증가시키면서 k번째 원소를 합하거나 합하지 않는 두가지 경우로 백트래킹을 한다 #include using namespace std; int n, s; int arr[21]; int result = 0; void backtrack(int k, int tot){ if(k == n){ if(tot == s) result++; return;..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 방법 백트래킹을 사용하여 풀수있다 퀸은 상, 하, 좌, 우, 대각선으로 움질일 수 있고 시간을 줄이기 위해 세가지 조건을 검사할 수 있다 우선 퀸이 좌우로 움질일 수 있기 때문에 한 행에는 하나의 퀸 만 놓을 수 있다는 것을 전제로 두고 시작한다 1번 조건 (상하로 움직일 수 있기 때문에 같은 열에 있는지 확인하는 조건) : i의 값이 같으면 continue 해준다 2번 조건 ( / 모양 대각선 위에 ..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 해결 방법 백트래킹을 사용하여 가능한 수열을 모두 만들고 각각 주어진 식의 최대값을 구해 제일 큰 값을 찾는다 #include using namespace std; int n; int arr[10]; // 만든 수열을 담을 배열 int num[10]; // 입력받을 배열 bool isused[10]; // 사용했는지 체크 int result = 0; void solve(){ // 주어진 식을 이용하여 최대..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 알고리즘을 사용하는 문제이다 #include using namespace std; int n, m; int arr[10]; bool isused[10]; void backtrack(int k){ if(k==m){ for(int i=0; i

내장함수 isalpha 사용 isalpha 직접 구현 #include using namespace std; vector v; bool isalpha(char c){ if(c >= 'A' && c ='a' && c> str; int number = 0; for(char c : str){ if(isalpha(c)) v.push_back(c); else{ number += c - '0'; } } sort(v.begin(), v.end()); string result; for(int i=0; i

#include using namespace std; char col[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'}; int dx[] = {2, 2, -2, -2, 1, 1, -1, -1}; int dy[] = {1, -1, 1, -1, 2, -2, 2, -2}; bool check(int x, int y) { if (x >= 1 && x = 1 && y > str; int x; int y = str[1] - '0'; for (int i = 0; i < 8; i++) { if (str[0] == col[i]) { x = i + 1; break; } } int result = 0; for (int i = 0; i < 8; i++) { if (check(x + dx[i], ..

#include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int result = 0; for(int h=1; h

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 문제 해결 방법 1부터 1씩 증가시키면서 조건에 맞는 수를 찾는다 #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int e, s, m; cin >> e >> s >> m; int result = 1; while(1){ if((result-e)%15==0 && (result-s)%28==0 && (re..

주의사항 몇번 이동하는지 정해지지 않았기 때문에 string으로 받는다 n을 입력받고string을 이어서 받기 전에 버퍼를 비워준다 L, R, U, D를 미리 정해두고 그 인덱스에 맞춰 여행가A를 옮긴다 #include using namespace std; int n; string plans; int dx[] = {-1, 1, 0, 0}; //L, R, U, D int dy[] = {0, 0, 1, -1}; char moveTypes[4] = {'L', 'R', 'U', 'D'}; int main() { ios::sync_with_stdio(0); cin.tie(0); //속도 가속화 cin >> n; cin.ignore(); // 버퍼 비우기 getline(cin, plans); int x = 1, y..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제가 처음에는 이해가 안됐는데 아래처럼 풀면 된다 분할정복을 사용하면 된다 #include using namespace std; int n; string mapp[64]; bool check(int x, int y, int n){ for(int i=0; i