전체 카테고리

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

블로그에 알고리즘 문제 해설을 올리면서, 수식입력이 불가피한 경우가 생겼다. 티스토리에서는 기본적으로 수식 입력이 지원되지 않으니 외부 라이브러리를 사용해야 한다. 내가 사용한 라이브러리는 MathJax로, 구분자를 두어 수식을 입력하면 수식이 정확하다는 전제 하에 원하던 수식 형태로 변환시켜 준다. 라이브러리 추가하기 글 작성 모드를 HTML모드로 변경 후 위에 작성해둔 코드를 글에 추가하자. 참고로 위 코드는 CDN을 통해 항상 최신 버전의 MathJax를 사용할 수 있게 해준다. 만약 Specific한 버전의 MathJax를 사용하고 싶다면, 아래 코드의 두 번째 줄에 mathjax@[버전] 부분을 수정하면 된다. 만약 블로그에 꾸준히 수식을 사용하게 될 것이라면 아예 블로그 어디서든 접근할 수 있..

문제 ✨ 조합수는 원래대로라면 \({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개 있다는 의미가 된다. 즉, 이분탐색은 여기서 사용되야 한다. 특정 요..