본문 바로가기

전체보기

 (256)
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 10. Tree 말단노드까지의 까장 짧은 경로(BFS) 문제 아래 그림과 같은 이진트리에서 루트 노드 1에서 말단 노드 까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요. 각 경로의 길이는 루트도느에서 말단노드까지 가는데 디동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다. 입력 생략 출력 3번 노드까지의 길이인 1 입출력 예제 생략 풀이방식 이번 문제는 이진트리, 재귀함수를(을) 사용하여 푸는 문제이다. 더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다. 섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS) 설계과정 1. 맨 처음에 발견되는 말단 노드가 가장 짧은 거리에 있는 말단 노드이므로 그대로 출력한다. 2. 말단 노드가 아니라면 자식 노드들을 큐에 넣는다. 3. 레벨을 증..
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 9. Tree 말단노드까지의 가장 짧은 경로(DFS) 문제 아래 그림과 같은 이진트리에서 루트 노드 1에서 말단 노드 까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하세요. 각 경로의 길이는 루트도느에서 말단노드까지 가는데 디동하는 횟수를 즉 간선(에지)의 개수를 길이로 하겠습니다. 입력 생략 출력 3번 노드까지의 길이인 1 입출력 예제 생략 풀이방식 이번 문제는 이진트리, 재귀함수를(을) 사용하여 푸는 문제이다. 더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다. 섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS) 설계과정 1. 해당 노드가 말단 노드임을 확인하고, 말단 노드라면 레벨 값을 바로 리턴한다. 2. 말단 노드가 아니라면 자식 노드들 중에 더 작은 레벨값을 리턴받는다. * 주..
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 8. 송아지 찾기1(BFS) 문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 입력 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 출력 점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다. 입출력 예제 풀이방식 이번 문제는 이진트리, 큐, 재귀함수를(을) 사용하여 푸는 문제..
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 7. 이진트리 레벨탐색(BFS : Breadth-First Search) 문제 아래 그림과 같은 이진트리를 레벨탐색 연습하세요. 입력 생략 출력 레벨 탐색 순회 출력 : 1 2 3 4 5 6 7 입출력 예제 생략 풀이방식 이번 문제는 이진트리, 큐, 재귀함수를(을) 사용하여 푸는 문제이다. 더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다. 섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS) 설계과정 1. 큐에 노드들을 저장한다. 2. 트리에 레벨을 설정하여 각 레벨에 해당하는 노드들을 확인한다. 3. 해당 레벨에 해당하는 모든 노드들을 큐에서 꺼내고 출력한다. 풀이과정 1. NodeTwo 클래스를 생성하고, 각 변수들을 선언 및 초기화한다. data : 각 트리의 값이 들어갈 변수이다. lt, rt : 각각 왼쪽과..
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS) 문제 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 입력 첫 줄에 총 항수 N(1
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 5. 이진트리순회(DFS : Depth-First Search) 문제 아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요. 전위순회 출력 : 1 2 4 5 3 6 7 중위순회 출력 : 4 2 5 1 6 3 7 후위순회 출력 : 4 5 2 6 7 3 1 풀이방식 이번 문제는 이진트라와 재귀함수를(을) 사용하여 푸는 문제이다. 더 자세한 설명은 아래 글을 참조해서 확인해보기 바랍니다. 섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 6. 부분집합 구하기(DFS) 설계과정 1. 노드에 값이 없으면 말단 노드임을 의미하므로 바로 리턴한다. 2. 왼쪽과 오른쪽을 나누어서 각각의 노드를 생성한다. 아래 이미지를 통해 자세히 알아보자. 코드중에 tree.root.lt = new Node(2) 가 수행되면 주소값이 200인 lt를 생성하고, 그..
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 4. 피보나치 재귀(메모이제이션) 문제 피보나치 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다. 입력은 피보나치 수열의 총 항의 수이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다. 입력 첫 줄에 총 항수 N(3
섹션 7. Recursive, Tree, Graph(DFS, BFS 기초) 3. 팩토리얼 문제 자연수 N이 입력되면 N!를 구하는 프로그램을 작성하세요. 예를 들어 5! = 5 * 4 * 3 * 2 * 1 = 120 입니다. 입력 첫 번째 줄에 자연수 N(1

티스토리툴바