나 요리학원 출신임

전에 공장 문제에서 iarr[j]인 수를 찾는 것을 했다.이 문제는 i arr[k] 이므로 j를 기준으로1. i arr[j]2. j 0; i -= (i&-i)) ret += arr[i]; return ret;}int sum(vector&arr, int s, int e) { return _sum(arr, e) - _sum(arr, s - 1);}void update(vector&arr, int x, int val) { for (int i = x; i

각 작업을 1번부터 N번까지 한번에 1초씩 실행시킬 때, 각 작업이 언제 완료되는지 구하는 문제다.이 문제는 작업의 양이 적은 순으로 보면 된다. 직접 써보면 규칙을 찾을 수 있다.총 걸린 시간 - 내 뒤에 남은 작업을 하면 내가 끝나는 시간을 알 수 있다..! 이 때 총 걸린 시간은 if(현재 작업 시간 != 이전 작업 시간)==> 이전에 총 걸린 시간 + 남은 작업*(현재 작업의시간 - 이전 작업의 시간)이다 이것만 안다면 인덱스 트리로 문제를 풀 수있다..! 소스코드123456789101112131415161718192021222324252627282930313233#include #include using namespace std;#define ll long long#define MAXN 1000..

2차원 펜윅트리로 풀 수 있는 문제다.펜윅트리를 2차원으로 생각하면 x축으로 펜윅트리가 있고 그 x축을 가진 y축 펜윅트리가 있다고 생각하면 편하다 업데이트와 합을 구할 때는 2중 포문으로 x축을 먼저 업데이트 해주고 그에 맞게 y축을 업데이트 해주면 된다 (a,b) ~ (x,y) 에 대한 합을 구하는건 그림을 그려보면 이해하기 쉽다(x,y) 까지의 합에서 - (a-1,y) - (x,b-1) + (a-1,b-1)을 하면 원하는 구간이 나온다! 그림으로 색칠해보는 것이 이해하기 쉬운 것 같다 소스코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #inc..

문제를 읽고 해석해보면 사이클이 아닌 정점을 찾는 문제다SCC를 이용해서 풀었다. 처음 입력 받을 때 자기자신으로 간선이 있으면 self배열을 통해 체크했다SCC를 찾는 dfs를 돌면서 scc크기가 1이고 !self[x]면 답이다~! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #include #include #include using namespace std;#define MAXN 100010stack ST;int t, n, low[MAXN], num[MAXN],..

문제가 처음에 이해하기 어려웠다3과목을 시험보는데 A가 B보다 모든과목을 잘보면 '대단한 학생'C라는 학생보다 '대단한 학생'이 한명도 없다면 '굉장한 학생' 이다 처음에 세그먼트 트리를 2개 만들어서 비교하려했는데 실패했다 ㅎㅎ 3과목이라 조건이 3가지이기 때문에 아이디어를 잘 떠올려야 한다 문제를 푸는 방법은1. 첫번째 등수 기준으로 정렬을 한다2. 세그먼트 트리를 만든다. 이 때 트리는 최소값 트리다3. 트리의 i번째에는 두번째 과목을 i등한 사람의 3번째 과목 등수를 넣는다4. 0~n-1까지 for문을 돌며 두번째 과목 등수까지의 값이 3번째 등수 값보다 크다면 이학생은 굉장한 학생이다! 이렇게 3가지 조건을 다 만족시켜주게 트리를 만들면 되는데.... 어렵다! 소스코드123456789101112..

N 개의 정점이 있고 0번에서 1번 까지의 최단거리를 구하는 문제다이 때 가 간선은 가중치를 2개 가진다.최단거리는 0번부터 1번 까지의 1번가중치 합 X 2번가중치 합 이다. 처음에 완탐인줄알고 백트래킹했는데 생각해보니 최악일 때 20!이다..! 문제를 푸는방법은 그냥 다익스트라를 쓰면 된다 ㅋㅋpq에 (가중치1의 합, 가중치2의 합)을 추가로 넣어가면 쉽게 풀 수 있다! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include #include #include using namespace std;int n, ans = 1e9;bool check[22]..

X에서 출발해 X로 돌아올 수 있는지 없는지 판단하는 문제다Cycle이 있으면 안되는 문제다.하지만 양방향 간선끼리의 Cycle은 방향을 알아서 지정하면 되므로 문제가 안된다..! 따라서 양방향인 간선들은 무시하고 단방향인 간선들로 그래프를 그린다그리고 Cycle을 찾으면 된다! Cycle을 찾는 함수를 사용해도 괜찮고 플로이드를 써도 괜찮다! 소스코드(Cycle detect)12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include using namespace std;int n, arr[111][111], check[111];vector Graph;bool isCycle(int..

더 게임 오브 데.. 스.. 어렵다...K개 간선을 지나서 A->B로 갈 수 있다면 death 아니면 life다.생각이 안나서 폭풍도움을 받고 A^k을 하고 A[i][j]가 1이라면i->j라는 사실을 알았따... 생각해보니까 이산수학에서 transitive closure로 나온 것 같다.길이가 n인 path가 있으려면 A^n해서 확인했었다...!잘 기억해둬야겠다.. 행렬곱 n^3 * K(1,000,000) 이니까 정직하게 곱하면 시간안에 못푼다..!그래서 A^k를 log만에 구하는 방법으로 구현해야한다! 하지만 내 소스는 결국 틀렸다 ㅎㅎ..60..%..백준의 코드를 보며 공..부..하고.. 풀었다..!코드 깨끗하게 잘짜는 연습 해야겠다 ㅎㅎ 소스코드123456789101112131415161718192..

방학에 못풀어서 넘어간 문제다다익스트라로 풀면 되는데 K개의 도로를 포장한다는게 굉장히 걸린다 다익스트라를 돌리면서 dp를 사용하여 풀 수 있다.d[here][cnt] 테이블을 잡고 here까지 오는데 cnt개의 도로를 포장했을 때로 생각하면 된다 기존 다익스트라 +만약 cnt d[here][cnt] 라면 도로를 포장해준다 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include #include #include #include using namespace std;int n, m, k;vector Graph;int d[10010][..

영우는 바쁘다. 기숙사 청소를 해야하는지 알려줘야 한다BFS 그냥 돌리면 시간초과가 난다..!그냥 돌리면 방문한 곳을 다음에 다시 또 방문하게된다! 방법은 바로 이전에 방문한 곳을 체크해 두고 방문 안했을 경우에만 큐에 넣는다! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include #include using namespace std;int arr[333][333];bool check[333][333][2];int n, m, k, t;int dx[8] = { -1,-2,-2,-1,1,2,2,1 };in..