아네스의 공부일지

아이디어 presum을 미리 구해두고 (나는 dp라고 명명) 빨간색 구역의 합은 dp[r2][c2]에서 주황색 두부분을 빼고, 초록색 영역을 다시 더해줌으로써 구할 수 있다. C++풀이 #include using namespace std; typedef long long int ll; int R,C,Q; int board[1000][1000]; int dp[1001][1001]; int r1,c1,r2,c2; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> R >> C >> Q; for(int i = 0 ; i> tmp; board[..

아이디어 맨처음엔 visited를 bool타입으로만 풀려고해서 한번 실패하고, 백트래킹 해두고 visited를 다른 숫자로 바꾸는 방식으로 해서 차이를 두려고 했더니 시간초과가 나서 아예 매 bfs마다 다른숫자를 사용하는 것으로 고쳤다. 기존 문제점 위에꺼 처럼 visited true로만 처리하게 되면 아래 그림에서 2,3,4일때 visited true인걸 계속 만나서 count가 증가하기 때문에 구분해줬다. C++ 풀이 #include using namespace std; int N,M; int board[1000][1000]; int visited[1000][1000]; int dx[4] = {-1, 0 , 1 , 0}; // U, R, D , L; int dy[4] = {0, 1, 0, -1 }; ..

아이디어 일단 입력을 받은 후에 , 오름차순 정렬을 해둔다. 정렬 후 dfs(0)으로 배열의 첫부분부터 dfs를 시작해서 dfs들어갈 때마다 vector res에 push_back을 하며 진행한다. vector에 L개 만큼의 charater가 들어오면 자음 모음의 수를 체크하고 조건에 맞다면 출력한다. C++풀이 #include using namespace std; typedef long long int ll; int L,C; vector v; vector res; bool check() { int moum = 0; for(int i = 0 ; i< L ; i++) { if(res[i] == 'a' || res[i] == 'e' || res[i] == 'i' || res[i] == 'o' || res[i..

아이디어 solve함수에서 1인 곳을 찾고 bfs탐색하여 visited=true로 만들어주며 탐색한다. C++풀이 #include using namespace std; //input변수 int N; int board[25][25]; bool visited[25][25]; int cnt = 0; // 단지 수 카운트 int dx[4] = {-1,0,1,0}; //시계방향 탐색 int dy[4] = {0,1,0,-1}; queue q; // {x,y}값 넣을 큐 vector res; // 각 단지마다 개수 저장 vector void bfs(void) { int cnt = 0; while(!q.empty()){ int x = q.front().first; int y = q.front().second; cnt+..

아이디어 일단 오름차순 정렬시키고 for문으로 하나를 픽하고 2개를 찾는 것은 투포인터로 구한다. C++ 풀이 #include using namespace std; typedef long long int ll; int N; ll arr[5001]; pair plll; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); //input cin >> N; for(int i = 0 ; i> temp; arr[i] = temp; } //정렬하고 시작 sort(arr, arr+N); ll mini = LLONG_MAX; //최소값 찾을 변수 for(int i = 0 ; i< N-1; i++) { int lef..

아이디어 위 처럼 K번째 moo string에는 K-1번째 moo string이 앞뒤로 붙고 가운데에 mo...o( o의 개수는 k+2만큼 붙는)string이 추가된다. 일단 input N에 따라 적당한 K값을 구해두고 시작하기 위해 K에 따른 moo string 길이에 대한 점화식은 dp[k-1]*2 +(k+3)이다. 그래서 구해보면 이런식이 나오게 되는데, 이는 pow(10,9)까지만 했던거고 이후 제출땐 10^10까지 구해지도록 했다. 이 범위에 따라 N의 적절한 K값을 구하고 dfs로 들어간다. dfs의 베이스 조건은 K==0일때이고, S(k=0)일때로 보면 되겠다(moo) moo string에서 빨간 mooo... 를 기준으로 좌 / 우로 나눴다. 빨간 moo string영역일때의 첫글자라면 m..

문제 요약 array를 3분할 (left, mid, right) left의 sum [1,3,6,10,15] 이런식으로. 처음에 그냥 탐색으로 풀었다가 Timeout났었고, binary search로 접근하다가 조건이 뭔지 몰라서 한참 헤맸다. 결국 유튜브에 설명한번 보고 binary search로 해결했다. python 치트키인 bisect로 풀었길레, C++로 재구현해서 C++/python모두 제출했다. C++(시간초과 코드) class Solution { public: int dp[100001]; int waysToSplit(vector& nums) { int left,right; int last = nums.size()-1; left = 0; //dp계산. dp[0] = nums[0]; for(in..

일단 자꾸 틀리게 되는 원인이였던, 각 테스트 케이스마다 블록 list인 L을 초기화 안해주고 사용했던거랑, 테스트 케이스 수를 주지 않고 while(cin.eof() != EOF)로 했는데 제대로 작동하지 않았던 점. 위 2개의 원인이 시간을 엄청나게 잡아먹었다. 찾느라 애먹음 ㅠ; 아이디어 1. 투포인터 투포인터는 블록 list L을 일단 정렬 후, 양 끝점에서부터 시작해서 두개의 합이 구멍의 크기와 같으면 결과값을 찾은 것이니 즉각 리턴, 구멍의 크기(target)보다 작다면 head index를 1증가해서 다시 한번 테스트. 크다면 반대로 tail값 -1. 2. 이분탐색 투포인터로 풀었는데, 이분탐색으로도 풀길레 나도 풀어봤다. 마찬가지로 search로 들어가서 둘간의 head, tail간의 합 ..

문제를 간단히 요약하면 공유기를 설치할건데, 가능한 서로 떨어뜨려서 놓고싶다는 문제이다. 그 중 가장 가까운 공유기간의 거리를 최대로 하고싶다. 아이디어 문제를 보고 N은 최대 20만, C는 N에 속해있으며, 집의 위치는 10억이다. 대략 1초의 연산속도를 1억번이라고 봤을 때, O(N)의 속도로 찾는다고 해도 좌표를 통해서 찾으면 10초가 소모되어 timeout이 날것이 분명하다. 그래서 처음엔 집위치 list N은 20만개이므로 이를 일단 정렬하고 가운데 집을 기준으로 어떻게 해보려고 갖은 방법을 시도하다가 결국 아래와 같은 풀이로 접근하게 되었다. 이진탐색 문제들을 풀다보면 이걸 이진탐색으로 어떻게 풀어야하지? 에서 꽉꽉막힌다. 답답하기 그지 없는데, '무엇을 이진탐색 할것인가'에서 무엇을 빠르게 ..