문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/77486 2021 Dev-Maching에서 나온 문제 카카오 기출문제만 풀다와서 그런진 모르겠는데, Level 3 치곤 쉽게 풀었다. 만약 카카오 코딩 테스트에서 나왔다면, Level 2 쯤 아니었을까? 문제 핵심 및 풀이 그림에서 보면 알 수 있듯이, 트리 구조가 형성되는 것을 알 수 있다. 그리고 해당 문제에서는 자신을 추천한 사람을 아는 것이 중요한데, parent [i] = k : i를 추천한 사람이 k이다. 이런 식으로 정의하도록 한다. 사람 이름 문자열을 매핑 여기서 생각해야 할 것은 트리의 각 노드들이 사람이름(문자열)이라는 점이다. 그래서 parent의 인덱스로 문자열을 사용..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/60062# 카카오 코딩 테스트에 나왔던 문제다. 확실히 문제 이해하기도 복잡하다. 문제 핵심 및 풀이 유형 유추 제한 조건에 보면 외벽의 최대 길이(n)는 200까지이다. 인원을 배치할 수 있는 경우의 수는 200가지이다. 인원은 최대 8명까지 가능하다. 그리고 결함이 있는 외벽도 15개까지밖에 주어지지 않는다. 계산에 필요한 인원, 외벽, 최대 길이가 굉장히 짧다. O(n^2)을 하더라도 충분하고 O(n^3)도 가능하다. 그래서 완전 탐색이 사용가능하다고 생각했다. 어떻게 하면 외벽 점검을 최소의 인원만 사용할 수 있을까 해당 문제에서 키워드는 외벽이 원형 모양이라는 것이다. 이 말은 외..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12905? 1과 0으로 채워진 보드판이 존재한다. 표에서 1로 이루어진 가장 큰 정사각형의 넓이를 출력하는 것이 문제 이때, 보드의 크기는 최대 1000x1000까지 가능하다. 문제 핵심 및 풀이 최악의 경우 반복 횟수 보드의 최대 크기는 1000x1000이다. 그리고 구해야 하는 것은 정사각형의 크기이다. 만약 이를 직접 1의 개수를 세어가면서 구한다면 어느 좌표에서 시작해야 최대 정사각형인지 모르기 때문에 최악의 경우 1000x1000 배열을 전부 훑어야 할 수도 있다. 그런데 각 시작점부터 1의 개수를 세야 하기 때문에 1000 x 1000 x 1000 x 1000 = 10^12번 해..

문제 링크 ↓ ↓ ↓ https://school.programmers.co.kr/learn/courses/30/lessons/12900 세로 길이가 2이고, 가로길이가 n으로 주어진다. 타일은 2가지 방식 중 하나로만 배치할 수 있다. 1. (1x2) 타일을 가로로 배치하는 경우 2. (2x1) 타일을 세로로 배치하는 경우 가로길이가 n일 때 나올 수 있는 경우의 수를 1,000,000,007로 나눈 나머지를 구하는 문제 문제 핵심 및 풀이 일단 답을 구할 때 1,000,000,007로 나누라고 한 거 보니 경우의 수가 엄청나게 많이 나올 것이라는 것을 예측할 수 있다. 가로( n)가 1일 때부터 나올 수 있는 패턴을 나열해 보자. 1,2,3,5 순으로 개수가 많아진다. 답을 구할 때 1,000,000,..

https://school.programmers.co.kr/learn/courses/30/lessons/1835?language=cpp [A, C, F, J, M, N, R, T] 8개의 알파벳을 나열하는 것을 베이스로 한다. 입력으로 있는 data의 모든 조건에 부합하여 나열할 수 있는 경우의 수가 총 몇 가지가 나오는지 구하는 문제 문제 핵심 및 풀이 해당 문제 풀이의 핵심은 조건의 개수 n이 최대 100개까지라는 점. 그리고 8개의 알파벳을 나열할 때 나올 수 있는 모든 경우의 수는 8! = 40320밖에 되지 않는다는 점이다. 그래서 일단 나올 수 있는 경우의 수는 백트래킹을 구하는 것이 적절하다. 그렇게 줄을 다 세우면, 그다음부터 data에 따라 필터링을 해주면 된다. 필터링 방법은 간단하다...

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/136797 입력으로 눌러야 하는 숫자가 순서대로 주어지고, 왼손과 오른손 엄지를 가지고 숫자를 눌러야 한다. 각 숫자를 누를 때마다 가중치라는 비용이 드는데 이는 위치에 숫자의 위치에 따라 달라진다. 조건은 아래와 같다. - 이동하지 않고 제자리에서 다시 누르는 것 → 가중치 1 - 상하좌우 인접한 숫자로 이동 → 가중치 1 - 대각선으로 인접한 숫자로 이동 → 가중치 1 - 같지 않고 인접하지 않은 숫자를 누를 때 → 위 규칙을 따라 가중치 합이 최소가 되는 경로 처음에 왼손은 4번, 오른손은 6번에서 시작한다. 이때, 나올 수 있는 가중치의 최소합을 구하는 문제 입력으로는 숫자만 ..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/68646 인접한 풍선 2개를 선택해서 둘 중 하나를 터트리는 행동을 풍선이 최종적으로 1개 남을 때까지 반복한다. 두 풍선 중 번호가 더 작은 것을 터트리는 행동은 최대 1번밖에 할 수 없다. 즉, 횟수 제한이 없는 것은 두 풍선 중 번호가 더 큰 풍선을 터트리는 행동이다. 그리고 최후까지 남을 수 있는 풍선의 개수를 구한다. 문제 접근 단계 제한 사항에서 얻을 수 있는 정보 제한 사항부터 살펴보자. 일단 배열의 길이, 그러니까 풍선의 개수는 최대 1,000,000개까지 가능하다. 이게 뜻하는 바는, 시간복잡도가 O(N^2)까지 가면 10^12이므로 10초가 훌쩍 넘어버린다. 그러니까..

문제 이해 단계 https://school.programmers.co.kr/learn/courses/30/lessons/12904? 팰린드롬이란 앞뒤를 뒤집어도 똑같은 문자열을 뜻한다. 입력으로 문자열 s가 주어질 때, s의 부분 문자열 중에 가장 긴 팰린드롬의 길이를 구하는 문제 문제 접근 단계 제한사항부터 살펴보자. 문자열의 길이 s는 2,500 이하의 자연수이고, 알파벳 소문자로만 구성되어 있다. 팰린드롬이라는 좌우대칭 규칙성을 판단할 때는 보통 스택을 사용한다. 이 문제에서 사용하려고 했는데, 각 자리마다 스택을 사용하여 넣었다 뺐다 하는 것은 굉장히 비효율적이다. 그리고 예전에 백준 포스팅에서 이런 유사한 문제를 다룬 적이 있다. https://howudong.tistory.com/319 [C+..