노는 게 제일 좋아

이 문제 처음에 당연히 for문으로 쉽게 하려다가 입력 숫자보고 바로 접었다. https://www.acmicpc.net/problem/1920 #맞은 풀이 #include #include #include using namespace std; int N,M; //vector vec; int num[100001]; void binarySearch(int n, int arr[]){ int low = 0; int high = N-1; int mid; while(low > M; for(int i = 0; i> b; binarySearch(b, num); } } 이 문제는 탐색횟수를, 시간복잡도를 줄여야 했다. 그래서 탐색방법을 생각해봤다. 선형탐색은 시간이 많이 걸리고 어떠한 숫자를 찾는 것은 이진탐색이 O(l..

쉬운 문제지만 이러한 문자 비교문제가 많을 것 같아서 내 접근방법을 좀 분석하기 위해 써봤다. https://www.acmicpc.net/problem/1259 #맞은 풀이 #include #include #include using namespace std; int main(){ while(1){ string s; cin >> s; string scmp = s; reverse(scmp.begin(), scmp.end()); if(stoi(s) == 0)break; if(s.compare(scmp) == 0){ cout

아.. 자그마한 문제가 큰 에러를 만든다. https://www.acmicpc.net/problem/16236 #맞는 풀이 #include #include #include #include #define X first #define Y second using namespace std; // 위, 왼, 아, 오 순 int dx[4] = { 0,-1,0,1 }; int dy[4] = { 1,0,-1,0 }; struct Fish { int x; int y; int value; }; int N; int map[21][21]; // 맵 int visited[21][21]; // 방문(초기값 -1) int x, y; // 아기상어 초기 위치 int mag = 2; // 아기상어 초기 크기 int bite = 0; ..

음 처음은 헤맸던 문제다. BFS를 너무 많이써서 이번엔 DFS로 해결하였다. 시간도 메모리도 충분하다 음,,3초면 연산이 15번정도면 되려나...? O(N^2)도 통과될 느낌이다. https://www.acmicpc.net/problem/11724 #틀린 풀이와 맞은 풀이를 같이 두었다. #include #include #include using namespace std; int N, M ; // 노드, 간선 vector node[1001]; // 노드에 연결된 노드의 정보를 담는 배열 ex) 1번 노드에 연결된 정보를 가리키는 벡터가 있음 int visited[1001]; int cnt = 0; stack stk; //DFS를 위함 int main(){ ios::sync_with_stdio(0); c..

음.. 입력과 출력이 많은 문제다. 그냥 풀자. 그렇다면 검색이 빠른 BST로 구성된 자료구조를 쓰는 것이 유리하다. 오늘은 map이 그것이다. 사실 시간은 충분한 것 같다만 https://www.acmicpc.net/problem/1764 #맞는 풀이 #include #include #include using namespace std; int N,M; int cnt = 0; //N과 M이 큰 숫자이기 때문에 검색이 빠르려면 map? //또 이름이 중복이 없단다. int main(){ ios::sync_with_stdio(0); cin.tie(0); map donthear; map dontsee; cin >> N >> M; for(int i = 0; i> s; donthear.insert(make_pai..

쉽지만 손이 좀 가는 문제다. 입력이 매우 많기 때문에.. 시간초과가 나기 십상이다. https://www.acmicpc.net/problem/1620 #맞은 풀이 #include #include #include #include using namespace std; int N,M; string name[100001]; // 해당 번호에 이름 저장해놓음 map m; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N >> M; for(int i = 1; i> s; name[i] = s; //-> 해당 번호에 이름을 입력 m.insert(make_pair(s,i)); } for(int i = 1; i> s; //숫자가 입력됐는지 확인 !!!!!!! 중요 /..

음... 실수가 제일 많았던 문제다. 이게 어려운거겠지... 시간이 매우 없다. 재귀라도 적당히 재귀하라는 거겠지..? https://www.acmicpc.net/problem/1074 #맞은 풀이 #include #include using namespace std; int N; int r, c; int cnt = -1; // 방문을 0부터 시작함*** ////////////////// //++아래와 같이하면 무조건 처음부터 끝까지 돌아야함... void func(int N, int a, int b) { //최소 N 길이가 2임. if (N == 2) { for (int i = 0; i < 2; i++) { for (int j = 0; j < 2; j++) { cnt++; int x = a+i; // a..

이것 또한 분할 정복 Z자로 진행하는 방식이다. 더 어려워졌다면 9개로 늘어난거..? 시간도 많다 https://www.acmicpc.net/problem/1780 #맞은 풀이 틀린 부분에 대해서는 내가 주석을 좀 달아놨다. #include #include #define X first #define Y second using namespace std; int N; int map[2200][2200]; int mm = 0; int zz = 0; int pp = 0; void func(int N, int a, int b) { if (N == 1) { int std = map[a][b]; if (std == 1) { pp++; } else if (std == 0) { zz++; } else { mm++; } ..

이것 또한 분할 정복 Z자로 진행하는 방식이다. 더 어려워진다면 Z자가 아니라 새롭게 진행하는 방식이겠지 시간도 많다 https://www.acmicpc.net/problem/1992 #맞은 풀이 틀린 부분에 대해서는 내가 주석을 좀 달아놨다. #include #include #include #define X first #define Y second using namespace std; int N; int pic[65][65]; //N의 크기를 가지고 왼쪽 위 좌표가 a,b인 정사각형 void func(int N, int a, int b) { //가장 잘게 쪼갰을 때 if (N == 1) { //구현 //해당 값 출력 cout

이런 문제는 쉽게 짜면 쉽게 풀리지만 순서를 허투루 적었다간 나처럼 30분 날린다. https://www.acmicpc.net/problem/2630 나의 첫번째풀이... (틀림) -> 전체를 검사하지 않음. (즉, 전체는 틀렸다고 가정하고 품) #include #include #define X first #define Y second using namespace std; int N; int sample[129][129]; int white = 0; int blue = 0; //N사각형 크기, a,b해당 사각형의 왼쪽 위 좌표 void func(int N, int a, int b) { if (N == 1) { if (sample[a][b] == 1) { blue++; } else { white++; } ..