아네스의 공부일지

아이디어 처음엔 뭔문제인가 했다. 그냥 노드 1번부터 DFS하면 DFS들어가기 전 노드N은 DFS들어간 노드 N+1의 부모가 되는 논리 C++풀이 #include using namespace std; vector v[100001]; bool visited[100001]; int parent[100001]; int N; void dfs(int node, int prev) { parent[node] = prev; // 해당 단계로 넘어오면 이전 노드는 부모이므로. for(int i = 0 ; i< v[node].size(); i++) { if(visited[v[node][i]] == false){ //방문하지 않은 노드 방문. visited[v[node][i]]=true; dfs(v[node][i],node..

아이디어 그림으로 보면 약간 이런느낌으로 풀었다. v[0]는 당연히 1일거고. v[1]부터 앞을 탐색해서 자신보다 작은걸 찾아야하고( 증가하는 수열이므로 ) 그중에서 dp값이 가장 높은걸 찾아야한다. ( 30을 예로들면 ( 20, dp=2) , (10, dp=1)을 찾을 수 있으니,(10,dp=1)은 무시해야한다는 의미. 2+1이 되야지 1+1이 되면 안되니까.) C++ 풀이 #include using namespace std; vector v; int dp[1001]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int N; int result=1; cin >> N; for(int i = 0 ; i< N; i++) { int tmp; ci..

아이디어 이전에 RGB라고 비슷한 문제를 푼적이 있어서 한번에 통과가 됐다. 위가 dp보드일때, 빨간V위치에 올 수 있는 경우는 1과 2에서 올 수 있다. 2'도 가능하지만, 점수는 양수이므로 2'에서 온다면 2'-2-v로 올때보다 무조건 작은 경우 이므로 고려하지 않는다. [ ( 2- V ) 경로와 (2'-2-V)는 2에 2'에서 오는 경로를 포함하고 있으므로. ] C++ 풀이 #include using namespace std; int board[2][100001]; int dp[2][100003]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int T; cin >> T; for(int i = 0 ; i < T; i++) { memse..

permutation을 만들 때, 섞어야하는 배열이 있다면, 그 배열의 index를 섞는다 라고 생각하면 편하다. 하나를 여러번 뽑을 순 없으므로 visited[] bool 배열로 한 index가 두번 선택되게 하지 않게끔 막는다. 출력 조건이 사전순으로 증가하는(오름차순) 순서로 출력해야 하기 때문에 permutation을 실행하기 전에 sort후 실행한다. C++ 풀이 #include using namespace std; vector v; vector permu; bool visited[9]; int M, N; void print_permu() { for (int i = 0; i M; for (int i = 1; i > temp; v.push_ba..

단순했다. N개 중에 M개를 뽑아 조합을 만드는 문제. C++은 재귀로 풀고, python은 itertools의 combinations를 제공해준다. C++ 풀이 dfs의 for문은 그림과 같은 방식 #include using namespace std; vector v; vector comb; vector res; int M, N; void print_comb() { for (int i = 0; i < comb.size(); i++) { cout M; //1부터 시작. dfs(1); } Python 풀이 python 개사기.. import sys from itertools import combinations input = sys.stdin.readline N, M = list(map(int,input()..

아이디어 다익스트라 알고리즘을 사용하는데, Priority_queue를 이용해서 풀어야했다. 내가 자꾸 틀렸던건 if(visited[nn] ==false && dist[nn] > dist[node]+nw) { dist[nn] = dist[node] +nw; //값을 갱신한다. pq.push({-(dist[node] +nw),nn}); // 이렇게 하면 맞습니다. //pq.push({-nw, nn}); //이렇게 하면 틀리고 } 이부분인데 왜 누적합을 보내야하는지 의문이였다. 그런데, 찾고찾다가 아래와같은 반례를 볼 수 있었다. (좌) : priority_queue에 간선 비용순으로 push했을 때 (우) : priority_queue에 간선 누적합 순으로 push했을 때 C++ 풀이 #include us..

아.. 결국 혼자서 못풀고, 다른사람들의 풀이법을 보고 풀었다. 아이디어 얻고나서 무릎을 탁! 쳐버렸ㄷ. 아이디어 대충 아래와같은 트리가 있고, 임의의 노드(여기서 1번 노드)에서 출발해서 가장 길이가 긴 노드를 찾는다. (5번 노드) 그럼 5번 노드부터 가장 길이가 긴 트리길이를 찾으면 그것이 트리의 지름이 된다. C++ 풀이 #include using namespace std; vector v[100001]; bool visited[100001]; int maxidx = 0; int maxvalue = 0; void dfs(int node, int sum) { if( maxvalue < sum) // 가장 먼 node찾기. { maxvalue = sum; maxidx = node; } for(int ..

코드보면 dp가 참 짧은 라인 수인데,, 생각해 내기가 너무 힘들더라. 맨처음엔 그리디인 것 같아서 풀었는데, 반례가 있어서 납득했다. 예를들어 극단적으로 2 1 10 100 1 100 200 이런 경우만 따져봐도 1번 집에서 Greedy하게 비용 1을 선택하면 2번 집에서 101, 201을 가지게 되는 반면 1번 집에서 10을 선택하면 2번집에서 1을 선택해서 11의 비용을 가질 수 있다. 그러므로 그리디는 이러한 경우때문에 성립이 불가하다. 아래 코드에서는 dp배열을 ary와 동일한 사이즈로 만들어두고 채워나간다. 그림으로 따지면 이렇다. i번째 집에 칠할 수 있는 비용은 이전까지 칠해온 비용 + 현재 집에서 칠하는 비용(Ri, Gi, Bi)인데, R-R , G-G, B-B를 연속으로 칠하는 것은 불..

아이디어 vector에 3개의 값을 유지한다. v(입력값, 기존 index, 정렬후 index). 1. 입력을 다 받고 입력값 기준으로 sort를 실시 한 뒤 2. 각 entry들이 몇번째 숫자인지 순서를 매긴 후 (정렬 후index) 3. 기존 index를 기준으로 원상 복구 시켜서 정렬 후 index를 출력한다. C++ 풀이 #include using namespace std; vector v; bool compare(pair& a, pair& b) { return a.second.first > N; for(int i = 0 ; i< N;..

예제 1번에서 이런 모습이 된다. 사실 bfs를 써도 되고 , dfs를 써도 상관없다. C++풀이 #include using namespace std; vector v[1001]; queue q; bool visited[1001]; int cnt = 0; void bfs(){ while(!q.empty()) { int node = q.front(); q.pop(); for(int i = 0; i> N >> M; for(int i = 0 ; i> s >> e; v[s].push_back(e); v[e].push_back(s); } for(int i = 1 ; i