![]()
문제 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 풀이 1. 가장 좌측에..
문제 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다. 최솟값이 8보다 크면 -1을 return 합니다. 입출력 예 N number return 5 12 4..
슬라이딩 윈도우 고정된 배열에서 부분 배열들을 활용하여 고정된 폭만큼 움직여 값을 구하는 알고리즘이다. 같은 너비의 연속 구간들의 정보를 활용하는 것이다. 연속된 구간들 속에 정보가 겹치는 부분이 발생하는데 이 부분을 버리지 않고 재활용하는 점이 있다. 예를 들어 1 1 1 1 1 5 1 이라고 배열이 있다고 가정을 한다면 5개의 너비 만큼 한칸씩 이동을 할때 5의 크기중 첫 번째는 제거가 되고 5의 크기 중 우측에 새로 값을 추가해주면 된다. 그러므로 중간에 값이 겹치는 범위는 재활용을 하게 된다. https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다..
투 포인터 알고리즘 배열을 탐색하기 위해, 두 개의 포인터를 사용하여 배열을 순회하는 알고리즘 문제에서 이중for문으로 구하면 O(n^2)의 시간복잡도를 투 포인터 알고리즘을 활용하면 O(n)의 시간 복잡도로 풀이가 가능하다. https://www.acmicpc.net/problem/2003 수들의 합 2 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 128 MB 51870 24979 17060 48.389% 문제 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 10,000..
문제 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다. 제거한 바위의 위치 각 바위 사이의 거리 거리의 최솟값 [21, 17] [2, 9, 3, 11] 2 [2, 21] [11, 3, 3, 8] 3 [2, 11] [14, 3, 4, 4] 3 [11, 21] [2, 12, 3, 8] 2 [2, 14] [11, 6, 4, 4] 4 위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다. 출발지점부터 도착지점까지의 거리 distan..
문제 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한사항 입국심사를 기..
![]()
DP - Dynamic Programming (동적 계획법) 복잡한 문제를 여러 개의 간단한 무제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 원리 큰문제를 작은 문제로 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들은 결괏값은 항상 같아야함 메모이제이션(Memoization)모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재상요할 때는 이 DP 테이블을 이용 톱다운 방식과 바텀 업 방식으로 구현 메모제이션 원리 피보나치 수열 구하는 공식은 f(n) = f(n-1) + f(n-2)으로 n번째 수열은 n-1번째 수열과 n-2번재 수열을 더한 값이다. 즉, 5번째 피보나치 수열은 4번째 와 3번째를 더한 값이고, 작은 문제로 나누면 4번째와 3번째..
재귀(Recursion) 재귀(Recursion) - 자기 자신을 호출하여 자신을 반복적으로 호출하면서 결과를 도출 팩토리얼 - 1부터 n까지의 모든 값을 곱하는 방식 n! 는 1 * 2 * 3 * …. * (n-1) * n 이다. 여기서 맨 끝에 n만 제외하면 (n-1)! 이다. 결론적으로 n! = n * (n-1)! 이다. 또 (n-1)!는 …반복 5! = 5 * 4!; 4! = 4 * 3!; … 1! = 1 * 0!; 0! = 1; Java 코드 - 재귀 팩토리얼 // 재귀 - 팩토리얼 public static int factorial(int n) { if (n == 0) { // 기본 케이스 return 1; } else { // 재귀 케이스 return n * factorial(n - 1); }..
