문제 접근 트리 만들어서 노드1 부터 탐색하고, 연결되어있는 노드가 부모가 아니라면 해당 노드를 연결되어있는 노드의 부모로 설정하는 방식으로 풀었다. 분명 제대로 풀고, 머리 속에서 여러번 돌려봤는데 출력이 안 돼서 뭐가 문제인지 확인해보니까, while(--N) 으로 구현해서 for(int i=2; i
개발
문제 접근 1. 가장 큰 가중치를 지닌 노드부터 탐색하는 방법. -> 무조건 쓰이지는 않는다. ex) 1+10 < 3+8 2. 각 노드 별로 서브 트리에 대해 최대 지름을 구하는 함수를 만들어서 재귀로 푸는 방법. 문제 코드 #include #include #include using namespace std; int n, ans=0; vector tree(10000); int diameter(int n) { // tree[n] 이 비었으면, 잘못된 접근을 방지하기 위해 return. if(tree[n].empty()) return 0; // 해당 노드부터 시작하는 간선들의 합을 저장하는 벡터 vector inner_max; // 해당 노드부터 모든 간선의 합을 inner_max 에 push for(int..
문제 접근 inorder 의 첫번째 원소가 가장 왼쪽에 있는 노드를 가리키듯이, postorder 의 마지막 원소는 root 를 가리킨다. 이를 이용해서 inorder 에서 root 를 찾고, 왼쪽, 오른쪽을 나눠서 재귀로 찾고 preorder 에 끼워 넣는 방식을 생각했다. 처음에 함수의 인자는 4개 였는데, 코드를 작성하다보니 변수가 무슨 역할을 하는지도 헷갈리고, 코드가 복잡해졌다. 그래서 틀만 남긴 뒤 다 지우고, 각 변수의 역할을 지정한 뒤 깔끔하게 코드를 구현했다. AC 되고 다른 코드들을 보니, 내 코드보다 빠르게 돌아가서 확인해봤다. 다른 코드들은 이진 트리의 정점에 1 부터 n 까지 중복 없이 매겨져있다는 것을 이용해서 'arr[정점번호] = 순서' 와 같이 배열을 만들어 find 할 필..
문제 접근 연구소 문제처럼 브루트 포스를 통해 BFS 로 풀면 시간복잡도가 O(N^2*M^2) 이 나오고, 범위로 계산해봤을 때 1,000,000,000,000 이 나와서 이렇게 풀면 안 된다. 고민해보다가 경로 별로 isbroken 이라는 변수를 주어서 딱 한 번 막혔을 때 부수고 true 로 바뀌도록 구현해봤다. 처음에 메모리 초과가 계속 나서 q 에 넣어줄 때 visited 를 true 로 설정하니 중복이 없어져 해결되었고, 이후에는 틀렸습니다가 계속 나왔다. 확인해보니 시작 부분이 1이어도 벽을 부수지 않았다고 넣어주는 경우가 있어 고쳤다. 하지만 조건 보니 시작이랑 끝은 항상 0이어서 소용이 없다.. 저번에 종만북에서 읽었던 스캐폴딩이 생각나서 파일 입출력으로 N=M=1000 일 때를 확인해봤는..
저번 휴가 때 (20.07.22 ~ 20.07.28) 플래너 하나가 눈에 띄어서 구매했다. 120일을 기록할 수 있는 D-Day 플래너였는데, CodeForce Blue Rating 을 목표로 계획을 세우고, D-100 일 때 Class3 은장을 달성할 수 있었다. 시작할 때는 IT 특성화고를 나왔다고 하지만 코딩에 큰 자신감도 없었고, 잘하는 주변 친구들을 보면서 난 고등학교때 뭐했는지 고민하고는 했다. 그래서 호승심에 CodeForce 한 번 해본적도 없고, 어느 수준인지 감도 안오는 뉴비가 Blue Rating 을 목표로 했다. 하면 할수록 그 수준이 짐작이 되면서도 따라잡을 수 있을 거 같기도 한데 아직까지는 애매하다. Class3 까지는 크게 어려운 게 없어서Class4 부터 본격적으로 골드 문..
문제 접근 처음에 set 으로 풀었는데 제출할 때 시간 초과 나올 거 같은 느낌이 강하게 들었다. 역시나 시간초과! 알고리즘 분류를 보니까 비트마스킹이라고 되어있었고, bool 배열 만들어서 하면 될 것 같아서 만들어서 간단하게 풀었다. 다양한 알고리즘에 익숙해지기 전까지 알고리즘 분류를 보면서 풀기로 했는데, 너무 생각없이 안 되면 그냥 보는 것 같다. 가능하면 안 보고, 보더라도 고민해보고 보자. 문제 코드 #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int M, x; bool S[21] = {false,}; string com; cin>>M; while(M-..
문제 접근 일단은 구현부터 해보자고 생각했다. 완전탐색으로 3 군데에 0을 1로 바꿔 놓은 뒤, 2 위치 좌표 기억해뒀다가 DFS 로 안전 구역 크기를 계산하게 구현하고자 했다. 0 개수를 count 했다가 DFS 에서 0 만나면 -1 하도록 했다. 일단 수도 코드 간략하게 작성해보고, 시간 복잡도 계산해보니까 N,M 이 8 이하이므로 완전 탐색하는 경우는 최악의 경우 64C3 이었고, DFS 의 경우 map 크기 + map 크기 였다. ( V+E 인데 이웃과 다 연결되어있다고 생각하므로 ) 따라서 64C3 * (64+64) 였고, 계산해보니 5,332,992 가 나와 충분히 가능할 거라고 생각했다. 시간 복잡도는 O((N*M)^4) 이지만 N, M 의 입력 범위가 적어 가능했다. 주의할 것! 1. 전역..
문제 접근 입력 받은 것들을 인접 행렬로 구현하고, 1번에 대해 DFS 한 뒤 탐색하는 것들의 수를 cnt 변수에 기록해 반환하여 풀었다. 간단한 문제! 문제 코드 #include using namespace std; int v,e; bool adj[101][101] = {false}; bool visited[101] = {false}; int dfs(int n) { int cnt=0; visited[n] = true; for(int i=1; i>v>>e; for(int i=0; i>in>>out; adj[in][out]=adj[out][in]=true; } cout
