분류 전체보기19 [백준] 3584 가장 가까운 공통 조상 [백준 3584 가장 가까운 공통 조상] 문제 보러가기 노드 연결 정보가 나오고 순서가 보장되기 때문에 일단 전부 받아서 트리를 그려주었다! 이때 부모 정보와 자식 정보를 노드 별로 다 저장해 준다. 그리고 root를 찾아 아래로 내려오면서 각 노드의 depth를 찾는다. 그리고 입력 받은 2개의 노드에서 더 깊은 depth를 더 얕은 depth로 바꿔서 확인하는 시작점을 맞춰주고, 그 뒤로 depth를 하나씩 올리면서 같은 부모가 될때까지 탐색한다! #include #include #include #include using namespace std; int n, t, n1, n2, root; struct NODE { vector child; int parent; int depth; }; bool che.. 2021. 10. 14. [백준] 9466 텀 프로젝트 [백준 9466 텀 프로젝트] 문제 보러가기 n명 학생의 팀이 되고 싶은 리스트를 받으면서 자기 자신을 희망한 학생을 제외하고 모두 탐색의 대상으로서 queue에 넣어준다! 그 후, queue에서 학생 목록을 하나씩 빼면서 그 학생으로 부터 서로 팀이 되고 싶은 애들을 쭉 훑는다. 이때 check 배열에 현재 탐색의 시작이 되는 학생을 넣어주는 방식으로, 이미 거쳐간 학생을 체크한다. 이렇게 쭉 돌다가 시작 학생이 같은 학생을 만난다면 돌다가 cycle이 생긴 경우이므로, 해당 학생은 팀이 있는 것이므로 자기 자신을 선택하는 것으로 바꿔서 이미 팀이 생겨 다시 볼 필요 없는 경우로 만들어 주었다. 이렇게 모든 유효한 queue에 있던 경우를 돌았을 때 member 배열에서 본인을 가리키고 있는 것을 세어.. 2021. 10. 14. [백준] 14916 거스름돈 가장 기본적인 그리디 문제이다! 처음에 일단 거스롬돈을 최대한 5원으로 줘야지 거스롬돈 동전 수가 적어지므로 5원을 가능한 만큼 쓴다. 하지만 이후에 2원으로만 거스름돈을 줘야하기에 5원으로 채워진 돈 외에 남은 거스름돈은 짝수가 되어야한다! 만약 짝수가 아니라면 채웠던 5원을 하나 빼준다. 그 후 남은 거스롬돈을 2원으로 가능한 만큼 채운다!! 이때 남은 거스름돈이 0원으로 딱 떨어지면 동전을 count한 값을 출력하고, 아닌 경우 -1을 출력한다. #include using namespace std; int n, cnt = 0; int main() { scanf("%d", &n); while (n - 5 >= 0) cnt++, n -= 5; if (cnt && n % 2 == 1) cnt--, n +.. 2021. 9. 2. [백준] 11725 트리의 부모 찾기 입력이 들어올 때, 연결된 간선이 레벨 순서대로 들어오지 않기 때문에 다 받고 트리를 그려봐야 구조를 알 수 있다!! 그래서 각각의 노드에 대해서 연결된 다른 노드 목록들을 리스트에 먼저 저장해준다. 이때 한쪽 방향이 아닌 양쪽으로 연결된 관계를 모두 저장해준다. → 이게 v 배열! 다음으로 root인 1번 노드부터 연결되어 있는 노드들을 bfs로 돈다!! 이때 p배열에다가 연결되어 있는 노드들이 어디로 부터 왔는지 저장을 해줘서 후에 부모를 출력할 수 있도록 한다! 이미 p 배열에 값이 있는 노드라면 이미 더 상위 레벨에서 탐색하고 온 것이므로 더이상 queue에 넣지 않는다! #include #include #include using namespace std; int n; int p[100002]; .. 2021. 9. 2. 이전 1 2 3 4 5 다음
