개인적으로 공부한 내용을 정리중입니다.

음 이렇게 생각했다. 일단 A에 대해서 투포인터로 부분합을 좀 구하다가 , B에 대해서도 투포인터로 연산하면 된다고 생각했는데 틀린 부분이 A에 대해 경우가 다 나오지 않는다. #define _CRT_SECURE_NO_WARNINGS #define debug 0 #include #include #include #include using namespace std; #define NUM 100001 #define MAXV 987654321 long long int N, M,S; int arr[NUM],brr[NUM]; long long int T, A, B; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freope..

음 leet code trapping rain drop 문제가 이중포인터 카테고리에 있길래 이중 포인터 문제를 더 풀어본다. 첫번째 그냥 시간 복잡도 무시하고 생각해보면 왼쪽에서부터 쭉 가면서 거기서 부터 주어진 합을 만들 수 있는 부분 수열인지 알아 보면 된다. 근데 이러면 시간이 너무 오래걸린다. 그냥 여기서는 이중포인터로 하래서 생각난 방법인데 어떻게 떠오른지도 모르겠고, 검증을 못하겠다. 좌우끝에서 해당 배열의 총합을 구해놓고 하나씩 빼면서 좌우로 좁혀나가는 것이다. 일단 이렇게 좌우로 뺄 수 있으면 막 빼니까 원하는 S가 안만들어진다. #define _CRT_SECURE_NO_WARNINGS #define debug 0 #include #include #include #include using ..

내가 전에 면접 문제로 풀어본 문제다 난 히스토그램 문제랑 비슷하게 생각해서 했는데 탈락했다 ㅋㅋ 다시 풀어보자 여러 방법으로 과연 내가 왜 틀렸던 것인가 풀이가 틀린게 아니라면 내가 못알아 듣게 말한게 큰거 같다. 면접에서 일단 첫구현인 내가 생각했던 방법이다. 틀렸따. ㅋㅋ class Solution { public: int trap(vector& height) { int cur; int sum=0; for(int i=0;i=0 && height[left-1] > height[left]){ left -= 1; } while(right+1 < height.size() && height[right] < height[right+1]){ right += 1; } cout

달리기 *일단 나는 머지소트로 했는데 [https://justicehui.github.io/koi/2019/03/03/BOJ2517/] 여기보면 세그먼트 트리도 된다 함 아직 안해봤다 난 그리고 비슷한 문제로 [https://www.acmicpc.net/problem/10090] 앞에 자기보다 큰게 몇개 있느냐는 문제이다. 2 8 10 7 1 9 4 15 최악의 시간 복잡도로라도 생각하면 그냥 하나씩 고르고 그 앞을 쭉 보면서 자기보다 큰게 몇개인지 세어보면 된다. 근데 그러면 O(n^2)이겠지.... 음 이런식으로 고르고 오름차순 정렬이되 도록 올려주면 결국 되긴한다. 근데 문제가 그러면 효율적으로 올려서 정렬되는게 아니라는거. 여기서 방법으로 머지소트 방식을 떠올릴 수 있겠다. 근데 구현했는데 틀렸다..

스도쿠 ( 백트레킹 문제를 더 고민해보자!!, 이전에 백트레킹인줄 몰라서 틀린게 좀 있는거 같다. 카카오 원판 순회?) 음 완전탐색해야 될거 같다. 가능한 놈들을 추려서 결국에 가능한 한가지 경우만 도출하면 될거같은데 구현 방법이 떠오르지 않는다. 후보를 어떻게 저장해야 될까, 각 칸마다 저장하는건 올바르지 못한거 같다. 각 행,열 마다 후보들을 저장해놓자. 그리고 3x3 그리드 마다 가능한 후보들을 저장해 놓자. 그리고 각 칸마다 가능한 놈들을 행,열,그리드에서 공통인 것을 찾으면 될거 같다. 일단 테스트 케이스는 맞았는데 처음에는 틀렸었다. 틀린 이유는 행,열,그리드 모두를 만족하는 숫자를 넣어줘야 하는데 그걸 구현을 잘못했었다. 다시 한 방법은 bool num_r[10] = { 0 }; bool n..

아이디어는 dp[i][j] : 현재 도시i , 지금까지 방문한 도시가 j인걸로 설정은 했는데 구현을 못하겠다. 탑다운인지 바텀업인지;; 뭐 둘다 되겠지만 구현을 둘다 못하겠다;; dfs인지 반복문으로하는게 쉬운건지도;; 9251번 일단 첫 구현이 틀렸다; dp 갱신 방법을 나는 그냥 위 왼쪽 ㄳ중 큰거 가져오면 된다 했다. 근데 하다보니 에러임을 발견했다; 왜냐면 같을때 위아래에서 기록이 잘못 되서 대신 int tmp; tmp = max(dp[i - 1][j], dp[i][j - 1]); if (tmp > dp[i][j]) { tmp++; if (maxv < tmp) { maxv = tmp; ans[tmp] = a[i]; dp[i][j] = tmp; } } 이렇게 구현했는데 위와 왼쪽에서 가져온건 부분 ..

못 풀면 풀이를 보고 습득하는 능력을 키워보자..... 1915번 가장 큰 정사각형 1. 왜 dp[i][j]를 i,j를 포함하는 가장 큰 정사각형의 길이로 잡았을까? 방법과 구하는것(정사각형의 넓이) 사이에 연결 고리가 있을 텐데. 정사각형을 구하려고 생각해 보면 매우 추상적이다. -> 이것을 i,j를 끝으로 하는 정사각형으로 잡아 주므로서 해결된다? 2. 작은 정사각형들로 부터 큰 정사각형이 만들어지는지? 즉 아래 dp로 부터 dp[i][j]를 어떻게 형성하는지 제대로 몰랐다. 틀린 이유 배열 사이즈를 NM으로 안하고 NN으로 했다. 그리고 dp가 dp[i-1] 같이 계산되는 부분이 있는데 인덱스가 0부터 시작해서 끝까지 확인하지 못한거 같다. 고칠점 - 명시적; i-1이 들어가면 그냥 배열을 1부터 ..

3176번 https://m.blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221339300027&proxyReferer=https%3A%2F%2Fwww.google.com%2F LCA(Lowest Common Ancestor) 최소 공통 조상 알고리즘 LCA알고리즘은 트리에서 두 개의 노드를 선택했을 때 최소 공통 조상을 구해주는 알고리즘입니다. 예를 ... blog.naver.com 위 블로그를 참고했다.ㅍ 문제 추가. https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LnipaDvwDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는..

음 dfs를 아직도 잘 이해하지 못한거같다. 두가지가 중요 포인트였다. 1. 해당 노드에서 이동 횟수를 어떻게 저장할 것이냐 2. 무한 루프를 도는지 어떻게 알것인가. 1번은 그럭저럭 생각했는데. 2번이 문제였다. 근데 방향을 포함해서 dp를 하려했던 내 생각이 틀린것이 그렇게 할 필요가 없는게 해당 지점에서 이동한다 생각하고, dfs가 가장 깊이 갔다가 그 다음 지점들(4방향을 차례로 방문한다) 생각하면 방향을 포함 시킬 필요가 없었다. 아래 블로그를 참고 했다... 혼자 도저히 오래걸려서 https://lcs11244.tistory.com/63 [백준] 1103 - 게임 https://www.acmicpc.net/problem/17070 이 문제와 상당히 유사하고, 2019/10/13 - [Algor..

2504번 괄호의 값. 내 코드 #include #include #include #include #include using namespace std; using li = long long int; string str = ""; int idx = 0; stack st; bool flag =true; void pushStack(char x) { if (x == ')') { if (st.size() > 0) { if (st.top() == '(') { st.pop(); } else { flag = false; } } else { flag = false; } } else if(x==']'){ if (st.size() > 0) { if (st.top() == '[') { st.pop(); } else { flag..