분류 전체보기

문제설명입력 & 출력 나의 풀이 이번 문제는 피보나치 N에서 0과 1의 개수를 출력하는 문제입니다. 피보나치수열은 워낙 유명하기 때문에 어렵지 않게 풀 수 있지만 이 문제는 기존의 피보나치 함수를 재귀호출로 푼다면 런타임 에러가 발생합니다. 따라서 동적 계획법(DP)를 사용해야 합니다. 먼저 피보나치 함수를 점화식으로 표현한다면 다음과 같습니다.F(n) = F(n-1) + F(n-2)위 점화식을 기준으로 이미 계산된 값들을 배열에 저장하여 중복된 계산을 방지해야 합니다. 먼저 dp배열을 초기화해줍니다. 첫 번째 배열은 피보나치 수의 인덱스이며, 두 번째 배열은 크기가 2를 가지는 데 0번째는 0의 개수, 1번째는 1의 개수가 들어가게 됩니다. 이제 fibo(0)과 fibo(1)은 이미 값이 정해져 있기 ..

이번 포스팅에서는 Java 알고리즘에서 필수적이라고도 말할 수 있는 DFS와 BFS에 대해서 알아보겠습니다.  자바를 활용하다 보면 그래프나 트리 구조를 탐색해야 할 때가 있습니다.  예를 들어, 네트워크 경로 탐색, 웹 크롤링, 게임 AI 에서의 경로 탐색 등 다양한 분야에서 이러한 탐색 알고리즘이 사용됩니다.  이때 사용할 수 있는 것이 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)입니다. 이 두 알고리즘은 그래프나 트리 구조에서 특정 노드를 찾거나, 모든 노드를 방문하는 데 유용합니다.  DFS(Depth-First-Search)란❓Depth-First-Search를 번역해보면, 깊이 우선 탐색입니다. DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 이름에서 알 ..

그래프는 많은 컴퓨터 과학 문제에서 필수적인 데이터 구조입니다.  그래프를 사용하면 복잡한 네트워크 구조를 모델링하고 다양한 문제를 해결할 수 있습니다.  예를 들어, SNS에서 친구 관계를 나타내거나, 도로망에서 최단 경로를 찾는 문제 등을 해결할 수 있습니다.  Graph란 ❓Graph는 객체 또는 개체 간의 관계를 표현하는 자료구조입니다. 객체(Node)들 간의 연결(Egde)로 구성됩니다. Graph의 정의그래프는 두 가지 주요 구성 요소로 이루어집니다. 노드(정점, Vertex)그래프에서 개별적인 객체 또는 노드를 나타냅니다.간선(엣지,Edge)노드 간의 연결을 나타내며, 노드 간의 관계를 정의합니다.그래프는 노드와 간선의 집합으로 표현되며 다음과 같이 표현됩니다.G = (V,E)G : Grap..

문제설명입력 & 출력 나의 풀이 이번 문제는 DFS와 BFS를 활용하여 주어진 정점 V로부터 탐색하는 정점을 출력하는 문제입니다. DFS와 BFS에 대한 개념이 있으시다면 어렵지 않게 풀 수 있는 문제였습니다.  먼저 가독성을 위해서 전역변수로 사용할 수 있는 변수들은 전역변수로 선언해 줍니다.  main문 먼저 설명하자면, 빠른 입력을 위해서 BufferedReader클래스를 사용하여 입력을 받아주고, StringTokenizer를 사용하여 간선이 연결하는 두 정점의 번호를 공백을 기준으로 분리를 해줍니다. 그리고 입력받은 정점의 크기만큼 정점을 나타내는 graph배열을 초기화해 줍니다. 이때 문제에서 나왔듯이 정점은 1부터 시작하기 때문에 "+1"을 해줘야 합니다. 그리고 간선의 개수 M만큼 반복하는..