본문 바로가기

백준189

백준 1991 c++ "트리 순회" -PlusUltraCode- https://www.acmicpc.net/submit/1991   [필자 사고] 전위순회, 중위순회, 후위순회를 묻는 문제이다.전위 순회는 현재 노드부터 왼쪽 자식끝으로 이동후 더이상 이동할 수 없으면 자신과 형제노드를 탐방하고 다시 부모를 탐방하는 방식이다. 중위 순회는 이진 트리 형태로 되어있을 때 줄자를 이용하여 왼쪽부터 이동하여 먼저 줄자에 닿게 되는 부분으로 탐방하는 순서다. 후위 순회는 맨 왼쪽 노드의 형제노드를 탐방 후 그의 왼쪽 노드 와 부모노드를 탐방하는 순서이다. 이 문제에서 핵심은 재귀함수 형태로 왼쪽 끝 노드를 탐방 할 수 있냐 없느냐가 키 포인트이다.필자는 재귀함수구현에 있어서 출력 부분의 위치를 햇갈려 다소 시간이 걸렸다. 아래는 코드 해설이다.  validateAlpha 함수.. 2024. 9. 23.
백준 1068 c++ "트리" -PlusUltraCode- https://www.acmicpc.net/problem/1068  [필자 사고]트리의 리프노드를 구하라는 문제이다.마지막에 특정 노드를 삭제할 경우 밑의 자식 노느들 또한 삭제된다. 필자는 리스트형태 및 DFS알고리즘을 통해 트리의 리프 노드를 구하는 식으로 문제를 해결했다. 다만 여기서 조심해야 될 점은 루트노드가 반드시 0이라는 보장이 없다는 점이다.-1의 입력이 1번 2번 idx 3번 idx 일지는 아무도 모르기 때문에 이 부분 실수 없길 바란다. 또한 트리의 계층구조가 있기 때문에 양방향이아닌 단방향으로 리스트를 만들어줘야 된다.아래는 소스코드 해설이다. 1. Input 함수:여기서 목표 노드에서 출발하기 전에 트리의 구조를 큐(arr)에 저장합니다. 각 노드는 부모 노드와 연결된 자식 노드의 .. 2024. 9. 20.
백준 1414 c++ "블우이웃돕기" -PlusUltraCode- https://www.acmicpc.net/problem/1414   [필자 사고] 최소 스패닝 트리 알고리즘을 이용하여 푸는 문제이다. 알고리즘을 알고 문제를 풀면 쉽게 해결 하지만... 스패닝 트리라는걸 알기까지 과정이 힘들었따. 문제에서 핵심은 모든 컴퓨터가 랜선으로 서로서로 연결되어야 한다는 말이 있다. 이 부분을 Union 알고리즘을 이용하여 해결해 나갔다. 나머지 부분들은 랜선 길이를 기준으로 오름차순으로 정렬한뒤 스패팅 트리 알고리즘을 이용하여 해결했다.실수할 부분은 start지점하고 end지점이 같을 경우 제외해야 된다는 점이다. 아래는 코드 해설이다 1. Input 함수:먼저 Input 함수에서, 우리는 목표 노드에서 출발하여 네트워크를 스캔합니다. 여기서 각 노드는 출발점이며, 그 노드.. 2024. 9. 20.
백준 1389 c++ "케빈 베이컨의 6단계 법칙" -PlusUltraCode- https://www.acmicpc.net/problem/1389  [필자 사고]문제를 읽고 이해를 해보면 다음과 같다.1. 얼만큼의 친구들이 건너건너 있냐 => 모든 경로의 최단경로를 구한뒤 합을 구하면 케빈 베이컨법칙의 합이 만들어진다.2. 모든 경로를 구하기 위해 플로이드 와샬 알고리즘이 재격이다. 이 문제에서 조심해야 될 점은 가중치 값을 1로 설정하고 se만 설장할게 아니라 es도 양방향 선택해서 주입해야된다. 아래는 소스코드 해설이다.  Input() 함수Input() 함수는 먼저 사용자로부터 노드의 수 N과 간선의 수 M을 입력받는다.그런 다음, 2차원 벡터 arr를 노드의 개수에 맞춰 초기화한다. 각 노드 간의 초기값은 매우 큰 수인 99999로 설정되며, 자기 자신으로의 경로(arr[i].. 2024. 9. 6.

티스토리툴바