궤도

문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근데 dfs를 많이 사용해봤다면 이런 생각이 들 수 있다. dfs는 가능한 정점을 찾을 때 visited를 체크하는데 그럼 2가 이미 visited 였을테니 4->2가 될리 없지 않나? 그래서 연결된 정점을 찾고 dfs를 실행할 때는 visited를 체크하지 않는다. 근데 이러면 또 이런 생각이 들 수 있다. 그럼 1->2를 가고도 2->1이 탐색 가능해지는거고 이럼 무한루프가 되는거 아닐까? 그렇기 때문에 dfs의 현재 정점과 더불어 이 정점이 어떤 정점에서 이어져온 것인지 직전 정점도 저장한다. 소스코드 #include..

문제 풀이 inorder는 (왼쪽 트리)(루트)(오른쪽 트리) 순서로 탐색한다. postorder는 (왼쪽 트리)(오른쪽 트리)(루트) 순서로 탐색한다. 1991번의 이 트리를 숫자로 바꿔보자. inorder 순회는 4 2 1 5 3 6 7 이고 postorder 순회는 4 2 5 7 6 3 1 이다. postorder 순회의 맨 마지막 값인 1(=A)가 트리의 최상위 root 노드인 것을 확인할 수 있다. 1을 기준으로 inorder를 나눠보면 (4 2)(1)(5 3 6 7)이 된다. 4(=D), 2(=B)는 A의 왼쪽 트리 요소이고, 5(=E), 3(=C), 6(=F), 7(=G)는 A의 오른쪽 트리 요소다. 루트노드를 기준으로 왼쪽, 오른쪽 트리로 분할해나가며 트리를 구하면 된다. 사실 preord..

문제 풀이 그림에 답이 있다. 오른쪽 그림의 회색 점들 중에서 아무거나 하나를 찍어보자. 그리고 그 회색점에서 가장 멀리있는 점을 찾아보자. 어떤 회색점을 골라도 두 개의 파란점 중 하나가 선택될 것이다. 그렇다면 아무 점이나 하나 고르고, 그 점과 가장 먼 점을 고르면 그건 지름을 구성하는 2개의 점 중 하나인 것이다. 그러면 이렇게 구한 점 하나에 대해 또 가장 멀리 있는 점을 고르면 그 점은 지름을 구성하는 또다른 점인 것이다. 그 둘 사이의 거리가 지름이다. 이걸 구현하기 위해 dfs를 2번 사용할 것이다. 첫번째 dfs로 지름을 구성하는 점 중 하나를 찾고, 두번째 dfs로 트리의 지름을 찾는다. 거리를 dfs로 구해도 되는지 걱정될 수도 있다. 근데 트리의 특징 중 하나는 특정 정점 2개를 연..

문제 풀이 굳이 안그래도 될걸 억지로 어렵게 만들었다는 느낌이 드는 문제다. myunji.tistory.com/345 [백준] 1504번 : 특정한 최단 경로 문제 풀이 반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는 1->B->C->N 또는 1->C->B->N일 것이다. 이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다. 1에 대하여 실행 myunji.tistory.com 논리는 이 문제랑 같다. 일단 s->t 최단 거리를 구한다. 만약 s->g->h->t 또는 s->h->g->t 의 최단거리와 s->t와 같다면 목적지가 될 수 있다. 소스코드 #include #include #include #include #include #include using namespace..

문제 풀이 반드시 거쳐야 하는 정점이 B, C라고 하자. 이 둘을 거친 최단 경로는 1->B->C->N 또는 1->C->B->N일 것이다. 이걸 구하기 위해선 다익스트라 알고리즘을 3번 실행해야 한다. 1에 대하여 실행해 1->B, 1->C의 최단 거리를 알아야 하고 B에 대하여 실행해 B->C, B->N의 최단 거리를 알아야 하고 C에 대하여 실행해 C->B, C->N의 최단 거리를 알아야 한다. N까지 가는 두가지 경로 중 작은 것을 택하면 된다. 다익스트라 알고리즘의 자세한 구현 설명은 myunji.tistory.com/344 [백준] 1753번 : 최단경로 문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없..

문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없이 다익스트라 알고리즘을 구현해야 했던 것이다. 심지어 최단 거리만 출력하는게 아니라 경로도 출력해야 했다. c로 구현해야 했기 때문에 스택, 우선순위 큐 기타 등등을 스스로 구현해야 했다. 하지만 난 이제 라이브러리를 마음껏 사용할 수 있기 때문에 용기를 내보려 한다. 다익스트라 알고리즘은 특정한 출발 노드에서 모든 노드로 가는 최단거리를 구하는 알고리즘이다. 힙을 사용했을 때의 시간복잡도는 O(|E|log|V|)라고 한다. log의 밑은 2다. ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B..

문제 풀이 솔직히 어려워서 힌트를 봤다. 난 절대 떠올리지 못했을 방법이었다. 일단 이 문제는 비트마스크이다. 2차원 배열에 어떻게 비트마스크를? 싶을 수도 있겠지만 0~(1 tmp; for (int j = 0; j < M; j++) matrix[i][j] = tmp[j] - '0'; } for (int i = 0; i < (1 tmp; for (int j = 0; j < M; j++) matrix[i][j] = tmp[j] - '0'; } for (int i = 0; i < (1

문제 풀이 문제가 참 긴데 사실 마지막 문단을 빼곤 쓸데없는 말이다. 입력값 처리의 벽만 넘으면 아주 못 풀 문제는 아니다. 일단 한줄로 들어온 저 input을 예쁘게 정리하면 - + 0 + + + + - - + 이렇게 된다. S[i][j] = A[i]+A[i+1]+...+A[j]라고 했다. 그럼 S[0][0] = A[i]인 것이고 S[i][i]에는 A[i]의 부호가 있는 것이다. 나름 괜찮은 정보인데 다 풀고보니 난 이 정보를 사용하지 않았다. A[0]부터 A[3]까지의 순서로 값을 구할 것이다. A[0]은 A[0]0, A[1]>0이어야 한다. (0, 1), (1, 1) A[2]은 여기에 또 추가로 A[0]+A[1]+A[2]=0, A[1]+A[2]>0, A[2]> input; int pos = 0; f..