JUINTINATION

문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리일 때 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 출력해야하는 문제입니다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 접근 전위 순회의 경우 처음 출..

문제 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 풀이 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 이진트리를 그릴 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 구하는 문제입니다. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트..

문제 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 루트 없는 트리가 주어진다. 트리의 루트를 1이라고 정했을 때 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력하는 문제입니다. 접근 이진트리라는 조건도 없고 자식노드가 부모노드보다 숫자가 크거나 작다는 조건이 없기 때문에 일반적인 이진탐색트리 관련 알고리즘으로는 문제를 해결할 수 없었습니다. 그래서 DFS와 BFS를 이용하여 그래프를 순회하며..

문제 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 화면에 이모티콘 1개가 입력되어 있는 상태인 영선이가 효빈이에게 다음 규칙에 맞춰 이모티콘을 s개 보내야 하는 문제입니다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸리고 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 됩니다. 클..

트리란? 계층적(Hierarchical)인 구조를 나타내는 비선형 자료구조 나무를 뒤집어놓은 모양과 닮았다고 해서 붙여진 이름 부모-자식 관계의 노드들로 이루어진다. ex) Decision Tree(의사 결정 트리) in AI 리스트, 스택, 큐 등은 선형 구조 트리 용어 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A) 서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리 단말노드(terminal node): 자식이 없는 노드 비단말노드(leaf node): 적어도 하나의 자식을 가지는 노드 레벨(level): 트리의 각층의 번호 높이(height): 트리의 최대 레벨 차수(degree): 노드가 가지고 있는 자식 노드의 개수 A는 루트 노드이다. B는 ..

그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 그래프 G는 (V, E)로 표시 정점(vertices) 여러 가지 특성을 가질 수 있는 객체 노드(node)라고도 불림 간선(edge) 정점들 간의 관계 링크(link)라고도 불림 DFS란? 깊이 우선 탐색(depth-first search)한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 스택(Stack)을 사용하거나 재귀함수 사용 # 재귀함수를 사용한 DFS depth_first_search(v): v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then depth_first_..