DFS로 25개 중 7개를 고르는 조합을 만든다. 7개 원소를 골랐으면 그 중에 4명 이상이 이다솜파인지, 인접한지 확인한 후 ans를 올려준다. 번호를 0~24번까지 붙이면 y좌표는 해당 번호/5, x좌표는 해당 번호%5로 검사하면 된다. 복사 배열을 하나 더만들어서 조합으로 뽑은 위치에는 Z로 표시해줬다. 뽑은 수 중 하나 아무거나 넣은 후 근접 BFS를 돌렸을 때 Z의 총 개수가 7이 나오면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; string student[5][5]; string carr[5][5]; bool visit[5][5]; int ypos[] = ..
하루 종일 디버깅 못해 쩔쩔맸지만 양질의 문제다 차이를 mid로 둬서 이분탐색하는 건 알았지만 업데이트를 O(n^2)이 아닌 방법을 못 떠올렸다 100점이 안나오길래 다름 사람 코드 붙여넣어봤는데도 100이 안나와서 그냥 부분 성공했다 현재 위치 i를 업데이트 하면 이전 위치도 변경이 되는데 for문안에서 이중 포문 돌리는 것이 아니라 다시 반대 방향으로 for문을 돌리며 다시 업데이트 하면 된다. #define _CRT_SECURE_NO_WARNINGS #include using namespace std; #define MAX_N 100001 #define MAX_K 1000000001 int n, k; int arr[MAX_N]; int carr[MAX_N]; int ans[MAX_N]; int ma..
여러 번 공부하고도 이해못했는데 결국 피하지 못해 풀었다 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int ans = 0; //aabaa의 경우 a, aa, aab, aaba, aabaa 로 보는데 한글자인 a는 접두사,접미사가 같은걸로 보지 않음 // 따라서 i는 1부터 시작한다. vector makeTable(string p) {// 패턴문자의 접두사 접미사 구하기 int psize = p.length(); vector table(psize, 0); int j = 0; for (int i = 1; i 0 && p[i] != p[j]) { j..
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..
단어가 들어오면 구조체 형태로 배열에 저장하는데, 배열의 접근 인덱스를 hash에 저장한다 만약 cat이라는 단어가 들어오면 hash['cat']=2 (cat이라는 단어의 배열의 인덱스가 2라는 뜻) 형태로 저장하는 것이다. hash에 해당하는 문자열이 없으면 0을 반환하기 때문에 배열 인덱스 0에는 저장하면 안되서 인덱스는 1부터 시작한다. 해당하는 조건에 따라서 정렬해줄때도 배열+1의 위치부터 정렬해주고 출력하면 된다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; #define endl "\n" typedef struct st { string word; int cnt; }..
풀이 참고 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_WARNINGS #include #include #include #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); unordered_map member; unordered_map group; int n, m; string team,name; int cnt; cin >> n >> m; for (register int i = 0; i > team >> cnt; vector temp; for (register in..
C++이 문자열 기준으로 스플릿 해주는 함수가 없어서 스스로 분리해야 되길래 ㅠㅠㅋㅋㅋ 어떻게 분리하는지 찾아보았다. for문 돌려서 스스로 특정 문자열 기준으로 잘라줄거 아니면 strtok함수를 쓰는 것 같다. string을 char배열로 변환해서 strtok으로 분리한 후 다시 string형태로 저장하는데 외우면 편할거 같고 귀찮으면 안쓸거 같기도.. ㅎㅎ javascript으로 split()쓰다가 c++ 내장함수 없어서 당황했네 string str_arr[1000]; string a = "test is good and life is goood"; char str_buff[1000]; strcpy(str_buff, a.c_str()); char *tok = strtok(str_buff, " "); i..
정렬 혹은 이분탐색으로 많이 풀던데 나는 내림차순 정렬해놓고 i, j 를 모두 0으로 초기화한 다음 a가 더 작으면 i를 증가, b가 크면 j를 증가시키는 방식으로 비교해줬다 O(n+m) 이라고 생각됨 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int a[20000]; int b[20000]; int n, m; cin >> n >> m; for (register int i = 0; i > a[i];..
#define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; struct Student { string name; int kor, eng, math; }; Student s[100001]; bool comp(Student &a, Student &b) { if (a.kor == b.kor) { if (a.eng == b.eng) { if (a.math == b.math) { return a.name b.math; } else return a.eng b.kor; } int main(void) { ios::sy..