실력진단 결과 코드트리 8주차 실력진단 결과 오늘의 학습 Parametric Search 다음 문제는 어떻게 해결해 볼 수 있을까요? 1부터 n까지의 자연수의 합이 100이상인 경우 중 가능한 n의 최솟값을 구하는 프로그램을 작성해보세요. 단, 답은 1에서 30사이라고 가정합니다. 무작정 코드를 작성한다면, 1, 2, 3 ..., 30 전까지 계속 더해보며 최초로 그 합이 100을 넘는 순간을 찾아 바로 그 직전의 숫자를 구하게 될 것입니다. 넘어야 하는 합을 s라 했을 때 시간복잡도는 O(S)가 됩니다. 하지만 만약 이 문제가 수학 문제로 나왔다면, 다음과 같이 시도하게 될 것입니다. 1차 시도 (n = 15) 1부터 15까지의 합은 120이므로, 일단 15은 답의 후보 중 하나입니다. 이제 더 작은 ..
실력진단 결과 코드트리 7주차 실력진단 결과 오늘의 학습 Tree DP 각 정점에 값이 적혀있는 트리 정보가 아래와 같이 주어졌을 때, 각각의 노드마다 자신을 포함하여 자손 노드들에 적혀있는 수들의 합을 구해보려고 합니다. 위 그림에서 예를 들어 6번 노드의 경우 자신을 포함한 자손 노드 번호가 6, 2, 3, 5 이므로 각 노드에 적혀있는 수들의 합인 2 + 3 + 3 + 4 = 12가 나와야 합니다. 즉, 우리가 얻고 싶은 결과는 아래와 같습니다. 이를 각 노드를 정한 뒤 해당 노드에서 자식 노드로 움직이는 것을 재귀적으로 반복하는 탐색을 진행하는 완전탐색 방법을 통해 구현한다면, 각 노드를 정하는데 O(N), 각 노드마다 최대 확인해야 하는 노드 수가 O(N)이 되어 총 O(N^2)의 시간복잡도를 ..
실력진단 결과 코드트리 6주차 실력진단 결과 오늘의 학습 Bitmask DP 다음 문제는 어떻게 해결해볼 수 있을까요? 아래와 같이 노드가 4개 간선이 x개 있는 양방향 그래프가 주어져있습니다. 3번 노드에서 시작하여 모든 노드를 정확히 한번씩만 방문하되, 이동거리의 합이 최소가 되도록 해보세요. 3번에서 시작하여 모든 정점을 단 한번씩만 방문해야 하는 문제이므로 가장 간단한 방법은 모든 순열을 만들어보는 백트래킹을 이용하는 것입니다. 백트래킹을 이용해 모든 순열을 만드는 방법에 대해 아직 잘 모르신다면, 순열 만들기 유형을 공부하시고 나서 다시 이 설명을 읽는 것을 추천드립니다. 수열 만들기 링크 : https://www.codetree.ai/missions/2/problems/n-permutation..
실력진단 결과 코드트리 5주차 실력진단 결과 오늘의 학습 Bit Operator 다양한 비트 연산자에 대해 다뤄보도록 하겠습니다. 비트 연산은 기본적으로 2진법을 기반으로 합니다. Bit 연산는 컴퓨터의 기본 연산이기에 속도가 굉장히 빠릅니다. and 연산자 (|) and 연산자 |는 두 수 a, b를 이진법으로 표현한 뒤 각 자리에 적혀있는 bit에 대해 and 연산을 진행한 후 그 결과를 다시 10진수로 표현해줍니다. and 연산이란 둘 다 1일 때만 1, 아니라면 0이 되는 연산입니다. 예를 들어 5 | 6은 4가 됩니다. 101 (5) 110 (6) and ---------- 100 (4) or 연산자 (|) or 연산자 |는 두 수 a, b를 이진법으로 표현한 뒤 각 자리에 적혀있는 bit에 ..
실력진단 결과 코드트리 4주차 실력진단 결과 오늘의 학습 Trie & 트라이 6개의 문자열 "app", "apple", "apply", "apart", "ban", "banana"이 주어졌다고 생각해봅시다. 여기서 "ap"로 시작하는 서로 다른 문자열의 수를 구하기 위해서는 각 문자열과 일일이 비교를 해봐야 할 것입니다. public class Main { // 변수 선언 public static int n = 6; // 주어진 문자열 public static String[] words = new String[]{ "app", "apple", "apply", "apart", "ban", "banana" }; // 찾고자 하는 문자열 (prefix) public static String target = "..
실력진단 결과 코드트리 3주차 실력진단 결과 오늘의 학습 Two Pointer & 두 포인터 다음 문제는 어떻게 해결해 볼 수 있을까요? [6, 3, 2, 4, 9, 1] 와 같이 숫자들이 주어졌을 때, 특정 구간을 잘 골라 구간 내 숫자의 합이 10을 넘지 않으면서 가장 큰 구간의 크기를 구하는 프로그램을 작성해보세요. 무작정 코드를 작성한다면, 모든 구간 O(N^2)개를 잡아보면서 그 안에 있는 숫자를 전부 더해 합이 10을 넘지 않는 경우 중 구간 크기의 최댓값을 구하면 되므로 O(N^3)이 소요됩니다. 이 방법에 대한 코드는 다음과 같습니다. public class Main { public static void main(String[] args) { int[] arr = new int[]{0, 6..
실력진단 결과 코드트리 2주차 실력진단 결과 오늘의 학습 이진탐색 & 이분탐색 업/다운 게임이라는 것을 들어보셨나요? 한 사람이 수를 생각하고, 다른 사람이 수를 예측해서 부르면 그것보다 큰지, 작은지 불러주면서 최대한 빨리 그 수를 맞추는 게임입니다. 많은 사람들이 수를 처음 예측할 땐 범위의 가운데에 해당하는 숫자를 부르고, 그 이후엔 업/다운에 맞춰 특정 구간의 가운데를 부르는 방법으로 수를 추측합니다. 이진탐색의 아이디어도 저것과 동일합니다. 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것입니다. 업/다운 게임에서 비춰보면, '다운'이라는 말을 들으면 우리는 그 값보다 더 작은 값을 선택해야 하고, '업'을 외쳤다면 더 ..
실력진단 결과 코드트리 1주차 실력진단 결과 오늘의 학습 +1 -1 Technique 다음 문제는 어떻게 해결해 볼 수 있을까요? 1개의 선분이 주어졌을 때, x = k 직선과 만나는 서로 다른 선분의 수는 몇 개인지를 판단하는 프로그램을 작성해보세요. 단, 주어지는 x 좌표는 모두 다름을 가정해도 좋습니다. 예로, 다음 그림에서의 답은 2가 됩니다. 눈으로 봤을 때는 지극히 당연히 2개라는 것을 알 수 있지만, 이를 컴퓨터가 계산하기 쉽게 나타내기 위해서는 어떻게 해야 할까요? 바로 선분마다 시작점에는 +1, 끝나는 지점에는 -1을 적은 뒤, 빨간선 앞에 있는 점들에 적혀있는 숫자들을 전부 더해주면 됩니다. 이 의미는 곧 앞에 시작, 끝 지점이 전부 다 있는 선분들은 0으로 처리하고, 단 시작점만 나온..
