문제 ✨ 조합수는 원래대로라면 \({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
전체 카테고리
Synchronous, Asynchronous JavaScript는 기본적으로는 Synchronous(동기)적이다. 즉, 호이스팅이 된 이후부터 작성된 코드가 동작된다. 하지만 Asynchronous하게 코드를 작성하는 방식들이 존재한다. 가장 익숙하고 대표적인 예로는 setTimeout(브라우저가 제공하는 api로, callback 함수를 전달해 특정 시간이 지난 후 callback 함수를 호출하는 형태)이 있다. Hoisting이란? var, function 정의가 자동으로 가장 최상단으로 올라가는 현상을 말한다. CallBack 함수 Callback 함수에는 Synchronous callback과 Asynchronous callback이 존재한다. function printImmediately(pr..
최초 작성 시에는 트리를 인접 행렬의 형태로 정의하였다. 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...
문제 자체는 어렵지 않다. 이전 글인 '나무 자르기' 글을 참고하면 쉽게 풀 수 있는 문제다. 문제의 조건 중 'N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이 때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오'는 중간값(mid, 자르는 길이)로 잘랐을 때의 랜선 길이의 수(cnt)가 N보다 크더라도 조건에 일치하는 것으로 본다는 의미를 가진다. 또한, 해당 조건(N개 이상의 랜선을 만들 수 있도록 랜선 길이를 정하는 방법)에 일치하는 경우의 수가 여러 가지이며, 이 경우들 중에서 자르는 랜선의 최대 길이(여기서는 이를 확인하기 위한 값으로 mid 사용)가 최댓값인 경우를 찾는 문제이다. 즉, cnt가 M과 같은 경우에는 lt를 mid + 1 로 변경시켜서 두 범위 중 더 큰..
