Coding Test/백준

문제설명입력 & 출력 나의 풀이 이번 문제는 N개의 배열에서 M배열의 요소가 존재하는지 판단하는 문제입니다. 문자열에서 숫자를 찾는 방식을 사용할 수도 있지만, 문자열에서 숫자를 찾는 방식은 비효율적입니다. 따라서 이진 탐색을 사용하면 시간 복잡도를 크게 줄일 수 있습니다.  main문에서는 먼저 빠른 입력과 출력을 위해서 Buffer클래스를 사용하여 입력과 출력을 받아줍니다. StringTokenizer를 사용하여 공백을 구분하고 배열에 저장해 주고, 이진탐색에서 선행되어야 하는 정렬을 수행해줍니다. 그리고 이진 탐색함수로 받은 결과를 StringBuilder를 사용하여 결과를 추가해 줍니다. 이진탐색을 수행할 binarySearch 함수에서는 이진 탐색의 동작 방식인 시작점 left와 끝점 right..

문제설명입력 & 출력 나의 풀이 이번 문제는 N×M크기의 배열로 표현되는 미로가 있을 때 (1,1)에서 시작해서 주어진 (N, M)까지 가는 최단 거리를 출력하는 문제입니다. 문제를 딱 보면 알 수 있듯이 BFS로 풀어야 합니다. 코드를 나눠서 설명해보겠습니다. 먼저 자주 선언되는 변수들을 전역변수로 선언하여 가독성을 높여줍니다. N x M의 배열로 표현되는 미로의 크기를 받아줄 N, M 그리고 미로 map, 방문 여부를 체크할 visited를 전역변수로 선언해 줍니다. 그리고 상하좌우로 이동할 dx와 dy를 초기화를 해줍니다. 이 방향 배열은 개인이 어느 방향으로 설정할지에 따라서 다릅니다.  상(Up): X 좌표는 위로 이동하므로 dx [] 값이 음수가 됩니다.dx [0] = -1, dy [0] = ..

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

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