문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/92342? 카카오 코딩테스트로 나오면 문제인데, 자주 풀어보긴 해야겠다. 문제 핵심 및 풀이 해당 문제의 유형은 제한사항을 보면 알 수 있다. 최대 10발까지 가능하고, 점수도 11개가 끝이다. 충분히 완전탐색으로 풀 수 있는 문제다. 라이언 점수 경우의 수 완전 탐색으로 풀면 되기 때문에, 백트래킹을 떠올렸다. n개의 화살을 11개의 점수에 각각 넣어보면 된다. 여기서 중요한 것은 맞추는 순서는 상관없다는 것이다. 어차피 해당 점수에 맞은 화살 개수만을 따지기 때문에 백트래킹할 때 중복 조합으로 구현해 주면 된다. 점수 계산 점수를 구하는 방법은 간단하다. 모든 점수를 확인해 주면서 어피..

문제 링크 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/138475 1억 x 1억 크기의 행렬이 존재하고, 그 정수 s~e 사이 범위에서 가장 많이 나오는 정수가 뭔지를 알아내는 문제 문제 핵심 및 풀이 제한 사항을 보면 1억 x 1억짜리 행렬은 아니더라도, 최댓값 e가 5,000,000까지 가능하기 때문에 O(n^2) 연산만 해도 바로 시간초과 그리고 O(N) 짜리 연산을 하더라도 모든 starts 값에 대해서 답을 구해준다면, starts의 최대 길이는 100,000이니까, 10^5 * 10^6 이어서 역시 시간초과다. 결국 모든 starts의 범위에 대한 값을 미리 구해놓을 수밖에 없다. 즉, 메모라이징 기법을 이용하는 DP 문제라고 대놓고..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/118669? 여러 출입구, 쉼터, 산봉우리로 왕복하는 코스 중에서 intensity가 최소인 것을 찾는 문제. 문제 핵심 및 풀이 왕복? 같은 출입구에서 시작하여 산봉우리를 찍고 다시 돌아오는 것이다 .그리고 갔던 길을 다시 가도 된다. 그래서 말이 출입구 - 산봉우리의 왕복이지, 사실상 편도로 계산해도 된다. 왜냐하면 최소의 intensity를 찾았다면, 그 경로 그대로 다시 내려오면 되니까.. 예를 들어, 출입구가 1이고, 4번이 산봉우리라고 하자.1번 출입구에서 4번 산봉우리까지 도착하는데 줄일 수 있는 intensity가 3이라고 하면 어떤 경로 (1 - a - b - 4) 이런 식..

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