노는 게 제일 좋아

어떠한 값을 찾을 때 정렬이 되어있는 데이터들 안에서(이게 핵심이다) 정렬하는데 시간이 더 걸린다면 그냥 이진탐색 사용하지 않는게 낫다. 선형 탐색보다 훨씬 빠른 탐색속도를 가진 이진탐색이다. 일반적으로 Array가 이용된다. 우선보자 23을 찾기 위해서 중앙값을 조사한다. 중앙값보다 크기에 이번에는 중앙값으로 나눠진 오른쪽 그룹에 대해 중앙값을 조사한다. 그 나눠진 그룹의 중앙값보다는 작기에 다시 왼쪽 그룹을 만들어 조사한다. 나올 때까지 조사한다. 만약 값이 없다면 값이 없는 것은 어떻게 판단할 수 있을까?? 다시 보자 이번엔 24를 찾는다고 해보자 0-9까지 10개의 원소가 있다. 4번 인덱스를 조사했고 해당 값이 더 커서 5번부터 9번까지 사이의 중앙값인 7번을 조사했다. 7번보다는 작아서 5번과..

이 문제 처음에 당연히 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