알고리즘 문제풀이/인프런45 [알고리즘] 7-9 Tree 말단 노드까지의 가장 짧은 경로 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이를 정리하고 있습니다. 문제 설명 : 주어진 이진트리의 루트 노드1에서 말단 노드까지의 길이 중 가장 짧은 길이(간선의 개수가 적은)를 구하는 문제 풀이 넓이우선탐색(BFS)을 진행하다가 자식이 없는 말단 노드를 만나면 해당 노드의 레벨을 반환한다. package inflearn.recursive_tree_graph; import java.util.LinkedList; import java.util.Queue; //Tree 말단 노드까지의 가장 짧은 경로 public class Main7_9 { public static int bfs(Node root) { Queue q = new LinkedList(); q.offer(r.. 2021. 6. 17. [알고리즘] 7-8 송아지 찾기 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 수직선상 좌표에서 현수의 위치에서 송아지의 위치까지 갈 수 있는 최소한의 점프 횟수를 구하는 문제(한 번의 점프로 앞으로 1 or 뒤로 1 or 앞으로 5 이동 가능) 문제 링크 : https://cote.inflearn.com/contest/10/problem/07-08 풀이 최단 경로를 구하는 문제이기 때문에 BFS(넓이우선탐색)을 사용한다. 풀이 과정을 트리 그림으로 나타내면 다음과 같다. 노드의 숫자는 좌표 위치를 뜻하고 간선 위의 숫자는 한번의 점프로 이동하는 거리를 나타낸다(불필요한 중복 좌표는 생략). 즉, 트리의 레벨이 점프 횟수를 나타내고 최초로 송아지의 위치가 발.. 2021. 6. 16. [알고리즘] 7-7 이진트리 순회 - BFS(넓이우선탐색)(인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 이진트리를 넓이우선탐색(BFS)하는 문제 넓이우선탐색(BFS)란 시작 정점으로부터 가까운 정점을 우선적으로 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법으로 다음과 같은 순서로 탐색이 진행된다. 시작 정점으로부터 가까운 정점을 우선적으로 방문한다는 것은 시작 정점과 연결된 간선의 수가 적다는 것을 의미하기 때문에, 트리의 낮은 레벨부터 마지막 레벨까지 순차적으로 정점을 방문하며 탐색을 진행하게 된다. 코드 깊이 우선 탐색과 달리 재귀적으로 구현하지 않음 Queue 자료구조를 이용해서 구현한다. 어떤 정점을 방문했을 때, 자신을 출력하고, 자식이 있다면 큐에 넣는다. .. 2021. 6. 15. [알고리즘] 7-6 부분집합 구하기 - DFS(깊이우선탐색) (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 자연수 n이 입력되면 1~n까지의 원소를 갖는 집합의 부분집합을 출력하는 문제(단, 공집합은 제외) 풀이 {1, 2, 3} 3개의 원소로 이루어진 집합의 부분 집합의 개수를 구하는 방법은 원소 1이 있는경우, 없는 경우 -> 2가지 원소 2가 있는 경우, 없는 경우 -> 2가지 원소 3이 있는 경우, 없는 경우 -> 2가지 2 * 2 * 2 = 8 로 8개의 부분집합을 가지게 된다. (즉, n개의 원소를 가진 집합의 부분 집합의 개수는 2n) 집합의 각 원소를 트리의 노드로, 부분 집합에 포함된다 안된다를 간선으로 표현해 이진트리를 만들어보면 DFS(깊이 우선 탐색)을 진행하여 .. 2021. 6. 15. [알고리즘] 7-4 피보나치 수열 - 재귀함수, 메모이제이션 (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : n이 입력되면 피보나치 수열 n개의 항을 출력 피보나치수열 : 앞의 2개의 수를 합하여 다음 숫자가 되는 수열(첫 번째와 두 번째 항은 1) 자료 구조 책에서 재귀를 설명할 때 흔히 볼 수 있는 문제로 보통 반복문 또는 재귀 두 가지 방법으로 풀이하는데 이번 문제에서는 재귀와 메모이제이션을 사용하여 풀이한다.(물론 속도는 반복문을 사용하는 쪽이 더 빠르다) 참고 : 반복문으로 푸는 방법 재귀를 사용한 풀이 package inflearn; import java.io.BufferedReader; import java.io.IOException; import java.io.InputSt.. 2021. 6. 13. [알고리즘] 7-3 팩토리얼 - 재귀함수 (인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의) 인프런의 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 강의를 수강하며 풀이 코드를 정리하고 있습니다. 문제 설명 : 자연수 n이 입력되면 n! 을 구하는 문제 자료구조 책과 같은 곳에서 재귀함수를 설명할 때 흔히 볼 수 있는 문제이다. 풀이 재귀를 사용하여 풀이 n이 5일때, 메서드의 호출과 반환 과정은 다음과 같다.(->는 메서드 호출 순서, 2021. 6. 13. 이전 1 2 3 4 5 ··· 8 다음
