n이 최고 10^6이므로 n^2은 시간초과로 O(n)으로 풀어줘야 되는 문제이다. n=15일 때 1, 2, 3, ... ,15 를 하나씩 더하면 누적합은 1, 3, 6, 10, ... 이렇게 될 것이다. 6인 경우 1~6까지 누적합이 21이되어 15를 넘게 되면 앞에서부터 하나씩 빼준다 (연속합을 구하니깐) 21에서 1을 빼변 20, 2를 빼면 18, 3을 빼면 15가 되어 4+5+6=15 인 또 하나의 경우를 구할 수 있다. 그러니 시작이 어디부터 인지 나타내는 변수 s를 만들고 누적합이 15를 넘을 때마다 시작점을 1씩 증가시키면 된다. #define _CRT_SECURE_NO_WARNINGS #include using namespace std; int main(int argc, char** argv..
풀이 참고 https://yabmoons.tistory.com/319 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define endl "\n" #define MAX_N 10001 using namespace std; typedef struct st { int num; int parent; int child[2]; int index;//몇 번째 자식인지 판별 }Node; int v, e, a,b, ancestor, subsize; int dist[MAX_N][2]; Node tree[MAX_N]; void init() { memset(dist, 0, sizeof(dist)); for (int i = 0; i < MAX_N; i..
해시에 첫 집합의 문자열들을 저장하고 두 번째 문자열 집합을 입력받을 때 검색해서 해시에 들어있는 문자열의 개수를 세준다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int t, n, m; cin >> t; for (int tc = 1; tc > n >> m; string s; unordered_map hash; int cnt = 0; for (int i = 0; i > s; hash.insert({ s,s }); } for (int ..
뒤에서부터 한 문자씩 끊어서 vector에 저장한 다음 사전순 정렬했다 #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include using namespace std; int t,k; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> t; string s; for (int tc = 1; tc > k; cin >> s; vector list; string tmp = ""; for (int i = s.length()-1; i>=0; i--) { tmp = s[i]+tmp; list.push_back(tmp); } sort(list.begin(), list.end()); cout
연결리스트를 구현을 하면 좋으련만 c++을 다시 공부하면서 stl도 아직 모르는게 많아서 문제 많이 풀면서 익숙해지는게 먼저인 것 같다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); for (int tc = 1; tc > n; // 암호문 길이 for (int i = 0; i > x; l.push_back(x); } cin >> n; //명령어 개수 while (n--) { cin >> tmp; if (tmp == 'I') { cin >> x >> y; auto ite..
사칙연산 유효성 검사 풀고 풀었다가 완전 이진트리로 착각하여 입력을 이상하게 받아 5번 예제부터 자꾸 틀렸다. ㅠㅠ 아닌 걸 알고 입력부분 고쳐서 해결함. 연산자를 가지는 노드는 자식이 없고 연산자인 노드만 자식을 추가적으로 입력받는다. 나머지는 재귀로 중위 계산해준다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include using namespace std; double tree[1001][2]; string oper[1001]; double inorder(int num) { if (tree[num][0]) {//자식있음 double a = inorder(tree[num][0]); //왼쪽 계산 double b = inorder(tree[num][1..
왼쪽 대각선은 i==j 이고 오른쪽 대각선은 i+j=99이다. #define _CRT_SECURE_NO_DEPRECATE #include using namespace std; int arr[101][101]; int ans = 0; void go() { for (int i = 0; i ans)ans = sum; if (sum2 > ans)ans..
#define _CRT_SECURE_NO_DEPRECATE #include #include using namespace std; string arr[100]; int ans = 1; bool rowCheck(int level,int left, int right) { //행 체크 중간에 왼쪽 오른쪽 다르면 빠져나온다 while (left
행을 이동하면서 각 열에 퀸을 놔본다. #include #include using namespace std; int t,n; int col[11];// 각 행에 놓는 열의 위치를 저장한다 int cnt; bool check(int row) { for (int i = 0; i < row; i++) { if (col[i] == col[row] || abs(col[row] - col[i]) == row - i) {// 기울기가 판단 return false; } } return true; } void queen(int row) { if (row == n) {//모든 퀸 다 놓음 cnt += 1; return; } for (int j = 0; j < n; j++) {//놓을 열을 선택 col[row] = j; /..
a -> b 방향으로 화살표가 있다면 a가 작업된 후에 b를 작업할 수 있다는 이야기 edge[a]에는 b를 추가해주고 cnt[b]는 1증가시킨다. (b로 들어오는 간선개수라고 생각해준다) 사전작업(간선)이 없는 곳, 즉 cnt[해당작업번호]=0인 곳부터 출력해준다. dfs의 경우는 방문 배열 처리를 해준다. bfs는 0인 곳을 큐에 먼저 다 넣어줄 수 있어서 필요없다. 현재 방문한 곳 cur와 연결된 곳의 간선의 수를 하나 줄여주고 (사전작업이 하나 줄었으니까!) 연결된 곳의 cnt[다음정점번호]가 0이 된다면 방문할 수 있다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include #include #include using namespace std;..