🔗https://school.programmers.co.kr/learn/courses/30/lessons/92345문제 정보※ 자세한 문제에 대한 정보의 위의 링크를 참조해주세요!제한 사항1 ≤ board 의 가로, 세로 길이 ≤ 5board 원소는 0 or 10 = 발판 없음, 1 = 발판 있음좌측 상단 좌표 = (0, 0), 우측 상단 좌표 = (board 세로 - 1, board 가로 - 1)플레이어 초기 위치는 무조건 보드 내부에 있음.상대 플레이어가 있는 칸으로 이동 가능.문제 요약문제에서 요구한 사항을 요약하면 다음과 같습니다.무조건 A부터 게임을 시작한다.양 플레이어는 최적의 플레이를 한다. 이길 ‘수’ 있는 플레이는 최대한 빨리 승리하도록 플레이 → 최대한 적게 움직임.질 ‘수밖에’ 없는 ..

해당문제 링크목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 문제에서 요구하는 것은 주어진 챕터들에서 인접하는 두 개의 챕터끼리 합치면 두 파일의 크기의 합을 가진 하나의 파일이 되고 파일을 합칠때 필요한 비용은 두 파일의 크기 합이다. 이 경우 모든 챕터를 합쳐 하나의 챕터를 만들때 최소비용을 구하라. 최적화 문제이다. 먼저 완전 탐색을 이용하여 생각해보자. 간단하게 N개의 챕터에서 2개의 챕터를 뽑아서 합친다고 생각을 하면 nC2가 N번 반복되기 때문에 N^2 * N => O(N^3)의 복잡도를 가진다. 그렇기에 다른 방식을 찾아보자. 더 효율적인 시간 복잡도로 구현하기 위해서 관찰을 해보니 해당 문제에서는 최적의 subproblem을 찾을 수 있..

해당문제 링크 목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 문제에서 원하는 것은 각 인덱스마다 오큰수를 찾아서 출력하는 것이다. 오큰수 = 해당 인덱스보다 더 큰 값과 인덱스를 가지는 수중 가장 왼쪽 인덱스에 위치한 수이다. 먼저 이진탐색을 이용하여 upper bound과 같은 방법을 사용하는 것을 생각할 수 있다. 하지만 이진탐색은 정렬이 되었을 때 사용가능하고 해당 문제에서 정렬을 한다면 값의 위치가 바뀌어서 원하는 답을 도출할 수 없다. 그렇다면 DP를 이용할 수 있을까? 관찰해본 결과, 이는 어려울 것 같다. 그 이유는 subsolution이 도출이 되어야하는데 중복되는 연산이 없다. 각 인덱스의 값에 따라 너무 상이한 결과를 도출하기 때문에 ..

해당문제 링크목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 문제에서 요구하는 것을 알아보면 2x1,1x2 타일이 주어지는데 이것을 이용해서 3xN 짜리 벽을 가득 채울 수 있는 경우의 수가 몇개인가? 문제에서 벽을 채운다는 것을 그림으로 보여줬고 그 모양이 벽이 가득차있는 형태이기에 가득채울 수 없다면 경우의 수는 0개인 것이라 생각해야한다. 일단 먼저 경우의 수를 구할 수 있는 방법이 뭐가 있을까? 완전 탐색으로 접근하면 타일을 놓는 모든 경우를 직접 찾을 수 있다. 하지만 N이 커질수록 정답이 기하급수적으로 커지는 것이 쉽게 예상이 되기에 완전 탐색 접근으로는 시간 초과가 날 것이다. 세야 하는 경우가 많지만 일일이 셀 수가 없다. 다른 방법의 ..

해당문제 링크 목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 문제에서 요구하는 것은 intervals 내에 범위들 중 겹치는 것은 하나로 뭉쳐서 반환하라는 것이다. 해당 문제에서 중요한 것은 intervals 내 범위들이 정렬이 되어있는지가 중요하다. 정렬이 되어있지 않다면 탐색하면서 하나로 뭉치기가 여간 어려운 것이 아니다. 예를 들어, 제일 처음에 [0,0]이란 범위가 나오고 [0,3],[4,5],[0.1] 다음엔 이런 순서의 범위가 있다면 규칙적으로 합치기가 어렵다. 근데 [0,0],[0,1],[0,3],[4,5] 이런 순서로 나열되어있다면? 규칙적으로 합칠 수 있게 된다. 그래서 먼저 정렬을 해준다. start 값에 대해서 정렬을 해주..

해당문제 링크 목차 문제풀이 아이디어 구현코드 문제풀이 아이디어 먼저 문제에서 요구하는 내용부터 알아보자. target 숫자가 주어졌을때, candidates 안에 존재하는 숫자들로 순서를 고려하지 않은 모든 경우의 수들 중에 합해서 target이 되는 조합들을 반환하라. 라는게 문제에서 요구하는 사항이다. 그렇다면 모든 경우의 조합을 구해야한다. 조합을 구하는 시간 복잡도를 생각하면 O(2^N)이다. 해당 문제에서 가장 큰 N은 30으로 주어지는데 그럼 시간 복잡도가 O(2^30)이 된다. 원하는 시간 안에 답을 구할 수 없을 것 같다. 그리고 백트래킹을 이용할 수도 있는데 백트래킹은 가지치기를 얼마나 잘하느냐에 따라 성능이 좌우되지만 최악의 ..