오늘 푼 문제에서는 cpp 에서 안써본 문법들을 잔뜩 썼다. 다시 쓸일이 있을지는 모르겠다만 기록으로 남겨두자!! 우선 lower_bound 이진탐색기반으로 해당하는 값보다 크거나 같은값이 제일 처음 등장하는 곳 위치를 리턴. (정렬 전제) 또 중요한 내용이이 unique 와 erase 를 사용해서 벡터에서 중복되는 값들을 없애는 것이었다. 코드로 보자! #include #include #include #include using namespace std; map ranks; int main() { int n, tmp; vector input; vector input2; cin >> n; for (int i = 0; i > tmp; input.push_back(tmp); in..

오늘은 '이분 탐색' 문제를 풀었다. 그냥 for문을 돌면서 해당 수가 있는 곳을 범위를 절반씩 줄여가며 찾았다. 반복문을 돌면서 찾으면 쉽겠지만 시간초과가 날 것이다. #include #include #include #include using namespace std; int main() { int n, m; vector arr1; vector arr2; int tmp; cin >> n; for (int i = 0; i > tmp; arr1.push_back(tmp); } cin >> m; for (int i = 0; i > tmp; arr2.push_back(tmp); } sort(arr1.begin(), arr1.end()); vector..

#include using namespace std; int main() { int n, a,b; int cnt = 0; cin>>n>>a>>b; while(1) { if (a == b) break; a -= (a/ 2); b -= (b /2 ); cnt++; } cout

강의실 배정 문제다. 그리디를 통해 구현해내면 되는데, 방법은 금방 떠올릴 수 있는데 priority queue 를 사용하는 구현에 있어서 애를 좀 먹었다. priority_queue pq; 이렇게 적는게 priority queue 를 작은 순으로 만드는 방법이다. pq.push(arr[0].second); for (int i = 1; i < n; i++) { pq.push(arr[i].second); if (pq.top()

오늘 문제는 쿼드 트리이다! 사실 구현하는거 자체는 그다지 나쁘지 않았다. 4구역을 크기별로 다 확인하면서 만약 다 같은 값으로 이루어져 있다면 출력, 그렇지 않다면 재귀로 한번 더 들어간다. 이 문제는 예외들을 생각하지 못해 오래 걸렸다. 우선, 처음부터 다 같은 값으로 들어왔다면 "(", ")" 를 써줄 필요가 없다. 그 경우를 위해 처음 입력받을 때 다른 숫자들로 이루어진 입력인가 파악하여아 한다. 끝!! #include #include #include #include using namespace std; string str; char table[65][65]; void recur(int x, int y, int leng) { if (leng == 0) return; str += "("; for (..

이번 주에는 dfs , bfs 문제들을 풀어보려고 한다. BFS 는 큐, DFS 는 스택 으로 구현하면 된다, 이 정보들을 가지고 사실 dfs 로 구현은 거의 하지 않았다. 지금까지 풀었던 문제들은 대부분 구현 방식이 다음과 같다. 1. 큐에 시작 지점을 넣고 방문 표시를 남긴다. 2. 큐에서 원소를 꺼내, 상하좌우 인접 칸을 살핀다. 3. 이전 방문 이력이 없다면 삽입하고, 방문 표시 남긴 후 큐에 삽입한다. 4. 큐가 빌 때 까지 반복한다. 이번에 푼 문제는 2차원 배열 상에서의 dfs 가 아니였다. +1, -1, x2 를 이동할 수 있는 일차원 배열 상의 문제였다. 이 경우 if 문을 3번 사용해서 각각을 확인 해 줄 수 있는데, 이 경우 continue 를 해버려서 이 후 경우를 아예 체크하지 않..