알고리즘

문제 ✨ 풀이 ✨ 이 문제를 트리라고 생각해보면 다음과 같이 접근할 수 있다. 시작 노드는 1(값과 달라야 함)이다. (이 때의 레벨을 1로 볼 수 있다.) 마지막 노드는 7이다. (이 때의 레벨을 7로 볼 수 있다.) 각 노드가 다음 노드로 이동할 수 있는 경우는 자기 자신 노드의 좌표 값(x, y)에서 x는 [0, 1, 0, -1]를 더하고, y는 [-1, 0, 1, 0]를 더한 좌표의 x좌표와 y좌표가 모두 1보다 크거나 같고, 7보다 작거나 같아야 하며, 이전에 왔던 길은 가지 않아야 한다. 또한 그 값이 1인 경우이다. 이 값을 인접 행렬로 정리할 수 있다. 레벨을 별도의 변수로 두지 않고, y값이 곧 레벨이라고 여긴다. 마지막에 좌표(7, 7)에 도달하는 경우 cnt를 증가시킨다. import..

문제 ✨ 가장 윗 줄에 1부터 N까지의 숫자가 한개씩 적혀 있다. 그리고 둘째 줄부터 파스칼의 삼각형처럼 위의 두개를 더한 값이 저장되게 한다. N과 가장 밑의 숫자가 주어져있을 때, 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러 개 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력해야 한다. 첫째 줄에 두개의 정수 N과 F가 주어진다. N은 가장 윗 줄에 있는 숫자의 개수를 의미하며, F는 가장 밑에 있는 수로 1,000,000 이하이다. 풀이 ✨ 규칙을 찾아야 한다. N이 4이고 F는 16인 경우에, 가장 윗 줄의 숫자들(답)이 3 1 2 4 순서로 있다고 생각해보자. 아래와 같은 역방향 삼각형을 이룰 것이다. 이 때 둘째 줄부터 해당 값들이 더해지는 과정을 모두 써보자...

문제 ✨ 조합수는 원래대로라면 \({n}\mathrm{C}{r} = n!/(n - r)!r!\) 로 계산합니다. 하지만 여러분은 이 공식을 쓰지않고 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요. $${n}\mathrm{C}{r} = {n-1}\mathrm{C}{r-1} + {n-1}\mathrm{C}{r}$$ 입력 첫째 줄에 자연수 $ n(3

최초 작성 시에는 트리를 인접 행렬의 형태로 정의하였다. 1이 트리의 루트임은 알기 때문에, 1부터 시작해서 1의 행렬의 값들이 무조건 1의 자식 노드가 된다. 이 노드들의 행렬을 확인해 인접한 노드이나 부모가 아닌 값을 자식 노드로 여기는 방식을 재귀함수로 구현하였다. 문제는 이렇게 해결한 코드는 메모리 초과로 통과하지 못했다는 점이다..😭 두 번째로 작성한 코드는 인접 리스트를 사용한 방식이다. 일곱개의 리스트 타입의 배열을 생성해 1부터 시작하여 각 노드의 인접 노드 중 부모가 아닌 노드를 자식 노드로 판단해 해당 자식 노드의 부모를 기억하도록 하는 것이다. 코드 상에서 result는 각 노드(인덱스)의 부모(값)를 가지는 배열이고, checked는 이전에 체크한 노드(부모 노드가 됨) 여부를 가리..

트리 순회에는 세 가지 방식이 있다. 각 방식의 차이는 부모 노드와 왼편 자식 노드, 오른편 자식 노드 이 셋의 순서에 있다. 특히나 부모 노드의 순서에 중점을 두는 것이 좋다. 선위 순회는 세 노드 중 부모 노드를 선두로 출력하고 중위 순회는 부모 노드를 중간 순서로, 후위 순회는 부모 노드를 마지막 순서로 출력한다. 작성 코드 package Tree; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; // 트리 순회 public class Algorithm1991 { Node header; static class Node { String data; Node lt, rt; public Node(String dat..

문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.출력 점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다. 최초 작성 코드(Timeout) import java.util.LinkedList; impo..

문제 1부터 주어지는 수 N까지의 수를 중복되지 않게 가지는 배열이 존재한다고 할 때, 공집합을 제외하고 가능한 모든 부분집합을 출력 public class Main { static int n; static int[] result; static void dfs(int k) { if (k == n + 1) { String str = ""; for (int i = 1; i 0) System.out.println(str); } else { int L = 1; result[k] = L; dfs(k + 1); L = 0; result[k] = L; dfs(k + 1); } } public static void main(String[] args) { n = 3; result = new int[n + 1]; dfs(..

재귀 함수란, 자기 자신을 호출하는 함수를 말한다. 흔히 연속적인 규칙이 있는 수들을 나열할 때 유용하다. 가장 대표적으로 재귀를 이용해 해결할 수 있는 문제는 피보나치 수열 출력이다. 피보나치 수열이란 1, 1, 2, 3, 5, 8, 13, ...와 같이 앞의 두 요소를 더한 값이 다음 요소가 되는 수열을 말한다. 재귀함수로 피보나치 수열의 N번째 수를 구하는 방법은 아래와 같다. recurse(n)의 값을 출력하면 그만인 것이다. import java.util.Scanner; public class Main { static int recurse(int n) { if (n == 1 || n == 2) return 1; return recurse(n - 2) + recurse(n - 1); } publi..

이 문제는 어떤 포인트에 맞춰 이분 탐색을 할 지 정하기가 어려운 문제였다. 많은분들이 풀이해놓으신 내용을 보고 어떤 부분들에 중점을 두고, 어떤 방식으로 조금이라도 더 시간을 줄여야할 지 알 수 있었기 때문에 정리해보고자 한다. ✍️ 우선, 이 문제에서 이분 탐색을 사용해야하는 포인트를 먼저 알아보자. B[k]를 구함에 있어서, B[k]는 흔히 배열 B의 K번째 요소로 해석된다. 하지만 이를 방향을 돌려서 생각해보면 해당 요소는 자신 앞에 'K - 1'개의 요소가 있다는 의미가 된다. 더 나아가서, 이 배열이 오름차순으로 정렬된 배열이라는 전제 하에는 어떨까? 이는 곧 자기 자신과 같거나(자기 자신을 포함) 자신보다 작은 요소가 K개 있다는 의미가 된다. 즉, 이분탐색은 여기서 사용되야 한다. 특정 요..

해당 문제는 K개의 수를 받아서 해당 수들이 M개의 카드 목록에 몇개 존재하는지를 확인해야하는 문제이다. 신경써야 할 부분은 첫 번째로 K번 만큼의 루프를 돌아야 한다는 점, 이분 탐색을 이용하면서 어떻게 특정 수가 몇 개 있는지를 확인하느냐이다. 특정 수가 몇 개인지 확인하고자 할 때, 우리는 이분 탐색의 특징을 이용할 수 있다. 이분 탐색은 반드시 탐색하는 배열이 정렬되어 있어야 한다. 이를 이용하면 내가 찾고자 하는 값이 탐색하는 배열에 복수개가 있다면, 이들은 연속해서 존재할 것이라는 점이 중요하다. 때문에 연속해서 있는, 이 같은 수들로 이루어진 블럭의 시작과 끝 인덱스를 안다면 해당 요소가 몇 개 있는지 알 수 있다. 이를 위해 UpperBound, LowerBound 개념을 이용한다. cf...