코딩 테스트24 백준 2252번: 줄 세우기 (C++) 문제링크 https://www.acmicpc.net/problem/2252 풀이방법 해당 문제는 기본적으로 위상 정렬 알고리즘을 이용하여 쉽게 해결하였다. 학생 A가 학생 B앞의 서야 한다는 것은 A노드가 B노드를 가르키고 있다고 생각하여 그림을 그려보면 쉽게 이해가 갈 것이다. 그렇게 그린 그래프를 바탕으로 위상 정렬 알고리즘을 구현하면 된다. 위상 정렬 알고리즘에 대한 개념이 없다면 아래 영상을 참고하자 https://www.youtube.com/watch?v=Th-gLZUrd04&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=27 해답 코드는 다음과 같다. 코드 #include using namespace std; vector adj[32005]; int deg[.. 2024. 2. 2. 백준 1240번: 노드사이의 거리 (C++) 문제링크 https://www.acmicpc.net/problem/15681 풀이방법 해당 문제를 해결한 sequence는 다음과 같다. 기본적으로 bfs를 사용했고 bfs를 통해서 각 노드를 탐색해 나가면서 시작 노드로부터의 거리를 전부 구하면 된다. vector adj[1005]; 변수를 통해서 특정 두 노드의 번호와 거리를 입력받는다. int bfs(int start, int end) 함수를 통해서 말그대로 start지점을 트리의 루트로 생각하고 탐색을 시작하여 end 지점까지의 거리를 구하기 위해서 dist 배열을 통해서 탐색해나가는 노드와의 거리를 계산해나간다. 최종적으로 dist[end]를 return하여 입력받은 두 노드 사이의 거리를 출력한다. 코드 #include using namespa.. 2024. 2. 2. 백준 15681번: 트리와 쿼리 (C++) https://www.acmicpc.net/problem/15681 풀이방법 해당 문제는 아래 설명되어있는 힌트를 토대로 문제를 해결하였다. 문제를 해결한 sequence는 다음과 같다. 우선 입력 받은 r값을 루트로 하는 트리를 구현한다. 이때 탐색하는 현재 노드의 자식 노드를 child변수를 이용하여 저장해 둔다. countSubtreeNodes함수를 사용하여 r기준으로 만들어지는 트리를 바탕으로 각 노드별로 만들 수 있는 서브 트리의 개수를 구하여 treeSize 배열 변수에 저장한다. 최종적으로 입력 받은 UTree를 treeSize배열 인덱스로 사용하여 원하는 출력 값을 얻어낸다. 코드 #include using namespace std; int n, r, q, u, v; vector adj[1.. 2024. 2. 2. 백준 1991번: 트리 순회 (C++) https://www.acmicpc.net/problem/1991 풀이방법 해당 문제는 트리 탐색 방법 중에서 재귀를 활용한 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)를 코드로 구현하는 방법을 물어보는 문제다. 순회에 대한 3가지 개념을 이론적으로만 알고 있어도 특별히 어려움은 없으나, 문자열을 숫자로 변환해서 생각 하는게 조금, 아주조금 헷갈릴 수 있는 문제다. 허나 A=1이라는 가정하고 문제를 풀면 굉장히 쉽게 풀 수 있다. 해설 풀이는 아래와 같다. 코드 #include using namespace std; int p[100'005]; vector adj[100'005]; int n; void dfs.. 2024. 2. 2. 이전 1 2 3 4 5 6 다음