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

내가 전에 면접 문제로 풀어본 문제다 난 히스토그램 문제랑 비슷하게 생각해서 했는데 탈락했다 ㅋㅋ 다시 풀어보자 여러 방법으로 과연 내가 왜 틀렸던 것인가 풀이가 틀린게 아니라면 내가 못알아 듣게 말한게 큰거 같다. 면접에서 일단 첫구현인 내가 생각했던 방법이다. 틀렸따. ㅋㅋ 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; } } 이렇게 구현했는데 위와 왼쪽에서 가져온건 부분 ..

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..

1517번 각 숫자 보다 오른쪽에 큰 숫자가 몇개있는지 구해서 다 더하면 될거 같다. 생각 나는 방법1. 그냥 오른쪽으로 쭉 가면서 갯수를 다 세어본다. -> 이건 시간초과; 문제 카테고리상 세그먼트 트리이다. 세그먼트 트리는 분할 정복의 느낌이 조금 있는거 같다. 음 모르겠다. 노드 두개를 병합해서 새로운 노드를 만들때 어떠한 정보를 저장해야 답을 구할 수 있을 텐데 그것을 모르겠다. 12015번 : LIS 방법 6 10 20 10 30 20 15 1 2 1 2 1 1 1 2 1 3 2 2 dp[n] : n번째까지 가장 긴 부분 수열의 길이. dp[n] = (이전에 가장 긴 부분 수열의 연장됨(가장 긴 수열의 마지막 위치와 수를 저장하자) , 현재의 n번째가 처음 시작 수열로 한다) dp에 도대체 무슨..

4358번 생태학 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include using namespace std; map m; //종의 갯수를 빠르게 세기위한 트라이 struct Trie { bool finish; int cnt = 0; Trie* next[200]; Trie() : finish(false) { memset(next, 0, sizeof next); } ~Trie() { for (int i = 0; i < 200; i++) { if (next[i]) delete next[i]; } } void insert(const char* key) { if (*key == '\0') { fin..

가장 먼 노드. #include #include #include #include #include #define N 20001 using namespace std; bool visit[N] = { 0 }; vector adj[N]; //stack st; int maxv = 0; vector ans; queue q; queue dep; void dfs(int cur,int depth) { if (depth == maxv) { ans.push_back(cur); } if (depth > maxv) { maxv = depth; ans.clear(); ans.push_back(cur); } for (int i = 0; i < adj[cur].size(); i++) { if (visit[i] == 0) { visi..