다이나믹 프로그래밍 알고리즘은 문제를 각각 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다. 그리디 알고리즘은 항상 그 순간에 최적이라고 생각되는 것을 선택하며 풀어나가는 것이고, 다이나믹 프로그래밍은 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해나간다는 차이가 있다. 중복되지 않은 문제들은 분할 정복 알고리즘으로 해결한다(대표적으로 퀵 정렬, 병합 정렬) 알고리즘 특징 다이나믹 프로그래밍 최적 부분 구조 중복된 하위 문제들 그리디 알고리즘 최적 부분 구조 탐욕 선택 속성 분할 정복 최적 부분 구조 최적 부분 구조는 어떤 것인가? 아래 그림에서 집1에서 집2로 가는 최단 경로를 찾는다고 가정하자. 집1에서 빌딩까지 가는 경로는 3가지, 빌딩에서 집2까..

문제 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) B진법 수 N을 10진법으로 바꾸면, 항상 10억보다 작거나 같다. 출력 첫째 줄에 B진법 수 N을 10진법으로 출력한다. Solution 1. B진법 수 N을 10진법으로 출력해야 하는 문제이다. 2진법 수 1100을 10진법으로 출력해야한다고 가정하면 N의 element 값에 B의 해당 element의 idx승 만큼 각각 곱해서 더해주면 된다. import ..

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order. Example 1: Input: expression = "2-1-1" Output: [0,2] Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2 Example 2: Input: expression = "2*3-4*5" Output: [-34,-14,-10,-10,10] Explanation: (2*(3-(4*5))) = -34 ((..

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 Constraints: n == nums.length 1 half]

문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 트리는 재귀로 정의된 자기 참조 자료구조이다. 트리는 특수한 형태의 그래프이 일종이다. 정확히는 순환 구조를 갖지 않는 그래프이다. 트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트리이다. 이진 트리는 왼쪽, 오른쪽 최대 2개의 자식을 갖는 매우 단순한 형태이다. 이진 트리에는 여러 유형이 있다. F..

문제 이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다. 아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다. BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 ..

문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 각 노드의 부모 노드 번호를 출력해야 하는 문제이다. 예제 입력 1의 트리 그래프는 다음과 같다. 노드가 7개이므로 트리 구조를 담을 graph 리스트를 다음과 같이 만든다. graph = [ [], [], [], [], [], [], [], [] ] 첫번째 노드가 1이므로 idx가 0번째인 노드는 빈 리스트로 유지하기 위해 n+1개의 []를..

코딩테스트 연습 - 체육복 | 프로그래머스 (programmers.co.kr) 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육..