아네스의 공부일지

아이디어 일단 문제를 보고 가중치도 없고, 최단거리를 찾길레 bfs를 사용했다. 그런데 벽을 부수고 안부수고의 상태를 저장하는 변수를 추가했고, 거리를 저장할 변수를 추가했다. 문제는 visited배열에서 생겼는데, 단순히 visited[x][y] 로는 풀리지 않고, visited[x][y][방문여부]를 추가해줘야한다. 이렇게 바꾸고나면 방문을 했느냐/안했느냐 이지선다가 아니라 아래와 같이 경우가 더 생긴다. 1. 벽을 부수지 않은 상태로 방문한경우 / 방문안한경우 2. 벽을 부순 상태로 방문한 경우 / 방문 안한경우 현재좌표 x,y에서 nx,ny(n : new) 로 이동하는데, 현재 x,y까지 오는데 벽을 부순적이 있는지 없는지에 따라 방문여부를 다르게 체크해주는 것이다. 왜냐하면 벽을 안부수고 nx,..

아이디어 항상 존재하는 루트노드(1번노드)에서 시작해서 가장 먼 곳을 찾고, 그 가장 먼 곳에서 다시 가장 먼곳을 찾으면 지름이 된다. C++풀이 #include using namespace std; //다익스트라를 2번 쓰면 해결되는 문제아닐까. priority_queue pq; // weight, nextnode vector v[10001]; // next node, weight. bool visited[10001]; int dist[10001]; int n; int dijkstra(int s) { //두번 돌릴꺼라 초기화 해주고 시작. memset(visited,false,sizeof(visited)); memset(dist, 0, sizeof(dist)); //시작노드 푸쉬해주고, 방문처리 및 시..

C++ 풀이 #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); string input; vector result; vector op; cin >> input; for(int i = 0; i='A' && input[i]

C++ 시간초과 코드 문제를 보고, 아 음의 싸이클이 있으면 YES로 출력하면 되나보다 하고 풀었다. DFS를 사용해서 start지점과 똑같은 now에 도착하면 cycle이 있으며, sum값이 음수면 음의 싸이클이라 판단하고 return true 약 50%쯤에서 시간초과가 났다. #include using namespace std; //싸이클이 있는가. //음의 싸이클인가. vector v[501]; //index = 출발지점, first = 도착지점, second = 가중치. vector Visit; bool visited[501]; int N,M,W; // 각각 지점의 수, 도로의 개수, 웜홀의 개수. bool dfs(int start,int now,int sum) { if((int)Visit.siz..

처음엔 priority_queue의 pair.first 기준으로만 정렬하면 되는줄알구 -weight로 넣었는데, 뒤에꺼까지 정렬해야해서 struct cmp를 만들어서 정렬시켰는데, 최대힙을 기준으로 만들어져 있어서 그런가, 부등호 방향을 반대로 해야 제대로 둘다 오름차순으로 정렬되었다. C++풀이 #include using namespace std; bool visited[100001]; int N,K; //음.. 부등호가 왜 반대가 되야할까 // priority_queue가 기본적으로 최대힙으로 되어있어서 그런걸까 struct cmp{ bool operator()(pair& a, pair& b) { if(a.first == b.first) { return a.second > b.second; }else..

이런 경우도 마찬가지. 이런식으로 완전탐색으로 d를 하나씩 증가시키면서 row가 바뀌고, 이에따라 board의 상태가 바뀐다. 다음 depth에서 놓을 수 있는 위치에 Q를 위치시키고 보드의 상태를 바꾸며, 갈곳이 없으면 return 하고 위의경우세어 d==4가 되면 d==3위치에까지 Q가 자리했다는 의미이므로 count를 1증가시키고 종료한다. C++ 풀이 #include using namespace std; int board[16][16]; int cnt = 0; int N; void dfs(int d){ vector toClear; //종료조건, 보드크기가 0~N-1이니, N까지 들어가면 종료. if(d ==N){ cnt++; return; } for(int i = 0 ; i< N;i++) { //..

dp문제가 왜이렇게 많아.... 아이디어 각 string(A,B)에 맞는 dp배열을 생성하고 각 (i,j)칸은 A[i-1] , B[j-1] 까지의 string을 비교한 것이다. ex) dp[3][4] = ACA * CAPC 비교해서 만들어진 칸. 아 설명 못하겠당.. C++풀이 #include using namespace std; string A,B; int dp[1001][1001]; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> A >> B; int result = INT_MIN; for(int i = 1 ; i

아이디어 ㅠㅠㅠㅠ.. 처음엔 완전탐색으로 풀었었고(시간초과), 두번쨰는 bfs로 각각 dp를 만들어서 풀었고(시간초과) 마지막으로 입력과 동시에 dp를 만들어버리면서 풀었다.아래 3개 코드 모두 올리겠습니다.1. 완전탐색2. bfs + dp3. dp 바쁘신분은 3번 풀이만 보면 되겠습니다. dp의 아이디어만 소개하겠습니다. 처음 dp는 빨간 동그라미까지의 합을 구하기 위해서는 세모(주황색), 네모(초록색)는 더하고 X(파란색)는 두번 더해졌기 때문에 빼준다. 구간합을 구할떄는 x2,y2까지의 합(주황색)에서 초록색과 파란색 영역을 빼주면 보라색 구간은 두번 빼졌기 때문에 다시 더해준다. 1. C++ 풀이 ( 완전탐색 ) #include using namespace std; struct x_y{ int x..

아이디어 char로 들어오는 것을 받고, int로 변환하여 .은 -1로 넣고, 나머지는 숫자에 맞게 넣는다. (A= 0, B=1,C=2 ... Z = 25) 각 벡터에 처음[0]은 왼쪽 노드고, 각벡터에 두번쨰[1]은 오른쪽 노드가 된다. 포인터로 보면 NULL노드겠지만 빈 노드를 -1로 표현했으니, -1이 ㅇ니면 travel을 계속한다.travel(int a, int type)의 type은 0,1,2로 각각 전위, 중위, 후위 순회이다. C++ 풀이 #include using namespace std; vector v[26]; int N; void travel(int a,int type){ int p = a +'A'; switch(type){ case 0: //전위(preorder) cout a >> ..

아이디어 일단 dp인건 알것이고, 1,2,3으로 3가지 경우의수로 나눠서 풀었다. 1. 가장 왼쪽 노드 = 이전 층의 가장 왼쪽 노드 dp값 + 가장왼쪽 노드의 board값 2. 중간에 껴있는 노드 = max(자신이 받을 수 있는 이전 층 노드dp값) + 자신의 노드 board값 3. 가장 오른쪽 노드 = 이전층의 가장 오른쪽 노드 dp값 + 자신의 노드 board값 C++풀이 #include using namespace std; int board[501][501]; int dp[501][501]; int N; int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cin >> N; for(int i = 0 ; i< N; i++) { for(int j..