시작에 앞서...전체 코드는 글 최하단에 있습니다.SAT 문제란?(~A || ~B) && (B || C) && (~C) 와 같은 식을 true로 만들기 위해서는변수값AfalseBtrueCfalse 위의 표의 값이 각 변수의 값이 되어야만 한다. 이처럼 전체 식을 true로 만드는 각 절 내부의 변수값들을 찾는 것을 SAT 문제라고 한다.여기서는 minisat 프로그램을 사용할 것이며 위의 문제를 minisat 형식으로 나타내면 다음과 같다 p cnf 변수의수 절의개수 -1 -2 0 2 3 0 -3 01은 A, 2는 B, 3은 C를 나타내며 음수는 not 연산을 나타낸다.맨끝의 0은 한 절이 끝났음을 의미한다.문제 내용Einstein Riddle은 각 집에 사는 사람들의 조건이 주어졌..

이론LCS 이론 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common SubsequenceLCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.velog.io이 블로그의 글을 참고하였다코드#include #include #include #include using namespace std;int max(int a, int b){ if (a > b) { return a; } else { return b; }}int main(){ string a1; string a2; cin >> a1; cin >> a2; ve..

개요시간제한이 2초 정도면 100만번 돌려도 안걸리지 않을까.... 싶어서 그냥 전체 경우를 다 체크했다.다행히 통과완료!코드#include #include #include #include #include using namespace std;int main(){ int chn, broken_num, temp; vector brkV, numberV, allV; cin >> chn; cin >> broken_num; cin.ignore(); // 고장난 버튼을 벡터에 넣어주는 부분 if (broken_num > 0) { string tempS; getline(cin, tempS); stringstream orgNum(tempS)..

#include #include #include using namespace std;int main(){ string senten; int check_val; while (true) { stack qqq = {}; getline(cin, senten); // 문장 단위로 입력받음 if ("." == senten) { break; } for (char chr : senten) // 문장의 한 단어씩 추출 { string letter(1, chr); // string으로 변환 if (letter == "[" || lette..

문제 이해 및 시각화 (해답은 아래에)재귀를 통해 row에 행 값이 들어가고for문을 통해 column에 열 값이 들어간다 (전체를 순회하나 이후에 퀸을 놓는것이 불가능하면 회수 --> 백트래킹)아래 코드를 돌려보면 더욱 쉽게 이해할 수 있다. (line 123에 중단점 걸어 확인)#include #include #include #include #include using namespace std;int pos[8]; // 퀸들의 위치를 넣음bool left1[15]; // 왼쪽으로 내려가는 대각선 (i + j가 같으면 같은 대각선)bool right1[15]; // 오른쪽으로 내려가는 대각선 (i - j + 7이 같으면 같은 대각선), +7 해주는 이유는 인덱스 때문bool pos2[8]; // 행에서 ..