노는 게 제일 좋아

사실 쉬워서 안넣으려다가 26등 했길래 넣었다. https://www.acmicpc.net/problem/10816 딱 생각나는 그대로 옮겨넣었다. #include using namespace std; int N, M; int arr[20000002]; // 2천만 가량 int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i = 0; i> a; a += 10000000; arr[a] += 1; } cin >> M; for(int i = 0; i> b; b += 10000000; cout

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 문자열 정수 변환 string to int, int to string [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 배열을 초기화시키는 여러가지 방법 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - vector에서 iterator 활용 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 컨테이너 원소들의 최대, 최소 그리고 최대 최소 비교 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 입출력이 많음으로 인해 시간초과나는 것 해결 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - C++에서의..

어떠한 값을 찾을 때 정렬이 되어있는 데이터들 안에서(이게 핵심이다) 정렬하는데 시간이 더 걸린다면 그냥 이진탐색 사용하지 않는게 낫다. 선형 탐색보다 훨씬 빠른 탐색속도를 가진 이진탐색이다. 일반적으로 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

C++에서는array도 제공하지만 vector도 제공한다. 왜 우리는 vector를 쓰는가? 우선 array는 컴파일할 때 크기가 결정된다. 즉, 미리 알고 선언해야한다는 말이다. 크기가 고정되어있으므로 원소의 데이터는 바꿀 수 있어도 원소를 추가하거나 삭제하는 일은 불가능하다. 또한 컴파일할 때 크기가 결정되므로 무조건 스택 메모리를 사용한다. 솔직히 거의 모든 응용프로그램에서는 데이터가 동적이며 크기도 고정되어 있지 않은 게 현실이다. 때문에 데이터의 크기를 미리 알고 있는 것은 어렵다 **다만 메모리가 많다면 미리 선언하는 것도 나쁘지는 않다고 본다. 하지만 효율적인 활용을 위해선, 위 상황을 제외하면 가변 크기의 데이터 컨테이너가 있었으면 좋겠다고 생각한다. 바로 그것이 vector이다. //1...

아.. 자그마한 문제가 큰 에러를 만든다. 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; //숫자가 입력됐는지 확인 !!!!!!! 중요 /..