본문 바로가기

DP31

[백준/C++] 양팔저울 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 정말 풀 수 있나? 의문이 들었다.왜냐하면 아무리 DP로 푼다고 해도, 시간 복잡도는 O(3^n)이 되기 때문이다. (n은 추의 개수) 여기서 3^n인 이유는 아래와 같이 3가지 경우가 존재하기 때문이다. 1. 구슬 쪽에 추를 올리는 경우2. 추를 사용하지 않는 경우3. 구슬 반대편에 추를 올리는 경우 그렇기 때문에 시간 복잡도는 O(3^n)이다. 한번 최악의 경우를 상상해 보면 추의 무게가 1, 3, 9 ,27 ... 처럼 3의 배수로 늘어나는 경우이다. (중복해서 만들어지는 추의 무게가.. 2024. 4. 5.

[프로그래머스/C++] 3 x n 타일링 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 경우만 잘 파악하면 쉽게 풀 수 있는 문제다. 가로 세로가 2*3 인 사각형에 2*3인 사각형을 더하면 4*3인 사각형을 만들 수 있다. 이를 이용하면 길이가 n인 사각형을 만들기 위해서는 [0*3인 사각형, n*3인 사각형] + [1*n인 사각형, (n-1)*3인 사각형] ... 을 전부 계산하면 된다. + 참고로 이 문제에서 길이가 홀수인 사각형은 만들 수 없다. 이를 이용하면 문제를 풀 수 있는데 그 전에 알고 넘어가야 되는 게 있다. 위 그림과 같이 길이가 6인 사각형은 [2*3인 사각형, 4*3인 사각형] 처럼 볼 수 있고, [4*3인 사각형, 2*3인 사각형] 으로도 볼 수 있다. 이 경우 .. 2024. 3. 31.

[프로그래머스/C++] 안티세포 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제를 처음 봤을 때 어떻게 풀지 많이 고민했다. 모든 경우를 계속해서 계산하기에는 너무 계산이 많아졌기 때문에 이전에 계산된 내용을 이용해 빠르게 문제를 풀 수 있을 것 같았다. 고민 후에 DP와 Map을 이용해 문제를 해결했다. [문제 풀이] 안티세포 X와 Y에 들어 있는 수 들을 아래와 같이 표현한다고 가정하자 $$ Y\,=\,(i_{ys},\, ...\, i_{ye})$$ $$ X\,=\,(i_{xs},\, ...\, i_{xe})$$ 여기서 안티세포 Y와 X의 합이 같아서 합쳐진다면 합쳐진 새 안티세포 N은 아래와 같이 표현할 수 있다. $$ N\,=\,(i_{ys},\, ...\, i_{xe})$$ 이제 N의 왼.. 2024. 3. 29.

[프로그래머스/C++] 아방가르드 타일 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 DP문제면서 매우 간단한 줄 알았다... 하지만 정답이 아니길래 곰곰히 생각해봤더니 많은 패턴들이 숨어있었다. 먼저 아래 그림을 보자 단순히 3개를 연속으로 붙이는 경우와 1개를 붙이는 경우의 패턴이 있다. 저 패턴들을 붙였을 때 길이를 k라고 하면, 아래와 같이 나타낼 수 있다. $$DP[k-3] \times 1, \,\,\,\,\, DP[k-1] \times 1$$ k보다 길이가 3 짧은 경우에서 3개를 붙여 현재 패턴을 만들 수 있고, k보다 1개 더 길이가 짧은 경우에서 현재 패턴을 만들 수 있기 때문에 위처럼 나타낼 수 있는 것이다. + 이러한 타일링 문제를 처음 보면 세워져있는.. 2024. 3. 10.

[프로그래머스/C++] 등굣길 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 출발지에서 도착지까지 도달하는 최단경로의 개수를 return하는 문제다. 여기서 방향은 항상 오른쪽 아래로 움직이기 때문에, 일정 횟수를 움직여서 도달할 수 있는 위치는 정해져 있다. 그러므로 n칸 움직여서 도달할 수 있는 위치는 위와 왼쪽방향에 있는 n-1칸 움직여서 도달할 수 있는 곳의 경우의 수의 합과 같다. 아래 그림을 참고하면 이해가 쉬울 것이다. 위 그림과 같이 1, 1이 출발지 3, 4가 도착지라고 하면 각 칸까지 이동하는데 걸리는 경우의 수를 나타낼 수 있다. 예를 들어 (2,2)에 도달하는 경우의 수는 (1,2)에서 아래로 이동하는 경우와 (2,1)에서 오른쪽으로 이동하는 경우가 있다... 2024. 3. 8.

[프로그래머스/C++] 숫자 타자 대회 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 단순히 그리디로 풀 수 있나? 고민을 했다. 하지만 어떤 손가락을 움직일지 선택을 하기 위해서는 뒤에 오는 숫자들에 규칙같은게 있어야 하는데, 없기 때문에 그리디로 풀면 안된다는 결론이 나왔다. 그래서 생각한 방법은 탐색이었는데, 탐색도 그냥 하기에는 너무 많기 때문에 DP로 문제를 해결했다. 손가락 위치를 기준으로 특정 숫자를 입력할 때, 내 손가락의 위치를 기록한 vector가 있다면, 최악의 경우 100,000*10*10으로 문제가 해결되기 때문이다. 그리고 특정 번호에서 다른 번호로 이동해서 누르는 경우의 가중치를 쉽게 계산하기 위해 계산을 도와줄 2차원 vector를 만들었다... 2024. 3. 6.

[프로그래머스/C++] 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 문제를 풀기 위한 알고력과 코딩력을 상승시키고, 이때 최소 시간을 구하는 문제다. 여기서 문제를 풀기 위해서는 문제에서 요구하는 알고력과 코딩력을 만족해야 하므로, 모든 문제를 풀기 위해서는 각 문제에서 요구하는 알고력과 코딩력의 값 중 가장 큰 값 이상으로 능력을 올리면 된다. 여기서 최소 시간을 구해야 하는데 DP를 이용하면 쉽게 풀 수 있다. 특정 수치의 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구하면, 이 최소 시간을 이용해 다른 특정 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구할 수 있기 때문이다. (즉, 작은 문제를 해결하는 것으로 전체 문제를 해결할 수 있기 때문에 DP를 이용.. 2024. 3. 4.

[프로그래머스/C++] 단어 퍼즐 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 최솟값을 어떻게 찾을지만 고민하면 쉬운 문제다. 이전에 작은 문제들을 바탕으로 다음 문제를 해결하는 DP로 쉽게 풀 수 있는데, 왜냐하면 특정단어까지 만드는데 사용되는 최소횟수를 이용해 다음 문자까지 만드는데 사용되는 단어의 최소 횟수를 구할 수 있기 때문이다. 아래 그림을 보면 특정 문자가 주어지면 그 문자의 i번쨰 문자를 만드는데 단어가 사용되는 최소 횟수가 적혀있다. 이제 d라는 문자까지 만드는데 사용되는 최소 횟수는 다음과 같이 구해 볼 수 있다. 1. a에 "bacd"라는 문자를 더하기 2. b에 "acd"라는 문자를 더하기 3. a에 "cd"라는 문자를 더하기 4. c에 "d"라는 문자를 더.. 2024. 3. 3.

[프로그래머스/C++] 짝수 행 세기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 아이디어가 정말 안 떠올랐다. 규칙을 발견해 조합으로 해결이 될 것처럼 보였는데, 아무리 고민을 해도 짝수개의 열을 만드는 작업이 잘 안됐다. 그러다가 다른사람의 질문에서 홀수와 짝수라는 힌트를 얻고 방법이 떠올라 문제를 해결할 수 있었다. 먼저 문제의 조건에서 a 배열의 특정 열에 1이 포함된 개수와 b 배열의 특정 열에 있는 1의 개수가 같아야 된다. 그렇기 때문에 이 조건을 만족하기 위해 a의 각 열 당 몇 개의 1이 있는지 개수를 센 다음에 그 열에 있는 1들의 개수만큼 각 행에 배치를 해주면 된다. 여기서 1의 개수를 배치하는 방법을 조합으로 나타낼 수 있는데, n개의 행에서 1을 배치할 r개.. 2024. 2. 29.

[프로그래머스/C++] 쌍둥이 빌딩 숲 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DP를 이용하면 빠르게 풀 수 있는 문제다. 처음에는 큰 빌딩이 새로 생긴다고 생각하고 새로 추가된 큰 빌딩을 기준으로 삼 combination을 이용해 문제를 풀려고 했다. 이렇게 문제를 풀자 문제가 풀리긴 풀리는데 수가 너무 커 1000000007로 나누어 줘야하고, 곱셈을 하는 과정에서 범위를 넘어가기도 했다. 그래서 반대로 작은 빌딩이 추가가 된다고 생각하고 문제를 풀었다. 예를 들어 앞에서 봤을 때 count가 1이고 빌딩의 수가 2인 경우에서, 빌딩의 수가 3으로 늘어난다고 생각을 하자 (2, 1) => 빌딩의 수가 2이면서 count가 1인 경우의 수 그러면 작은 빌딩사이에 큰 빌딩이 들어.. 2024. 2. 14.

[프로그래머스/C++] 카운트 다운 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 다트를 던져서 최소한의 횟수로 일정 점수를 획득하고, 최소한의 횟수 중에서도 싱글과 불을 가장 많이 던지도록 하는 문제다. 이 문제는 DP로 쉽게 풀 수 있다. A라는 점수를 얻기 위한 최소한의 횟수를 구하려면, 아래와 같이 표현 할 수 있다. [B + 다트 점수] = A 여기서 B는 B라는 점수를 얻기 위한 최소한의 횟수다. 그리고 다트 점수는 내가 한번 던져서 나올 수 있는 점수들을 의미한다. 그러므로 A점수를 얻기 위한 최소 횟수를 구하기 위해서는, 이전의 B점수에 대한 최소 횟수를 알면 되므로 DP로 풀 수 있는 것이다. 처음에는 [A-다트점수]=B를 이용해 A를 구하려고 했지만, 이보다 더 직.. 2024. 1. 31.

[프로그래머스/C++] 도둑질 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제는 완전 탐색과 같이 풀기에는 힘든 문제다. 만약 완전 탐색으로 풀 경우를 예로 들면 첫 번째 집을 털경우 세번째 집을 털거나 안털거나 경우로 나뉠텐데, 이런식으로 계산하다보면 2^n과 같은 지수형태의 시간 복잡도를 가지게 되기 때문이다. 그래서 문제를 풀기 위해서는 이전에 계산한 값들을 갱신하면서 경우의 수를 줄여 주는게 핵심이다. 1. 만약 바로 직전에 붙어있던 집을 도둑질 했을 경우 현재 집은 도둑질 할 수 없다. 2. 바로 직전에 붙어있던 집을 도둑질 했을 경우 현재 집은 도둑질하거나 하지 않을 수 있다. 위 두 조건을 생각하면 현재 집까지 도둑질 했을 때 돈의 최댓값은 다음과 같이 나타낼 수 있다. 1. [바로.. 2024. 1. 28.

[프로그래머스/C++] 산 모양 타일링 (2024 KAKAO WINTER INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 이전 삼각형의 개수가 다음 경우의 수에 영향을 미치므로 DP로 풀 수 있다. 그림을 그려보면 더 쉽게 점화식으로 표현 할 수 있다. 먼저 아래의 그림과 같은 도형이 있을 때, 빨간 부분을 기준으로 경우를 나눌 것이다. 빨간 선을 기준으로 경우를 나눈 이유는 아래 그림과 같이 마름모가 옆에 있는 삼각형을 침범하는 경우와 침범하지 않는 경우로 나눌 수 있기 때문이다. 그러면 이 마름모를 기준으로 옆 삼각형을 침범하는 경우와 침범하지 않는 경우를 계산해보자 (여기서 빨간색으로 칠해진 삼각형은 2개로 이루어진 마름모형 타일, 파란색 삼각형은 그냥 한개의 삼각형 타일이다.) 옆 삼각형을 침범하지 않는 경우 .. 2024. 1. 23.

[프로그래머스/C++] 최적의 행렬 곱셈 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음에 행렬이 곱할 수 있는 순서대로 주어지는건지 고민했지만, 순서대로 계산이 가능하도록 주어질 것이라고 보고 문제를 풀었다. 문제를 보면 최악의 경우 200개의 행렬의 모든 순서를 전부 계산해보고 풀기에는 무리가 있어서 DP로 풀기로 했다. A번째에서 C번째 행렬까지의 곱셈연산을 구한다고 하면 (A행렬과 C행렬 사이에 B행렬이 있다고 가정) [A 행렬 ~ B 행렬의 최소 곱셈연산 횟수] + [B 행렬 ~ C 행렬의 최소 곱셈 연산횟수] + [이번 연산 횟수] 값이 최소가 되는 행렬을 찾으면 A 행렬 ~ C 행렬의 최소 곱셈 연산 횟수가 된다. 즉, 이전에 계산한 최소 곱셈연산 횟수가 다음 계산에도 사용되므로 DP로 풀 수.. 2024. 1. 7.

[프로그래머스/C++] 경사로의 개수 (2023 현대모비스 알고리즘 경진대회 예선) HTML 삽입 미리보기할 수 없는 소스 문제 설명 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/214290 위와 같이 맵이 주어지면 방문할 수 있는 경사로를 [1, -2, -1, 0, 2, 1, -2, -1, 0, 2]와 같은 형태로 주고, 얼마나 경사로를 반복할지 횟수 k를 알려준다. 한번에 이동할 수 있는 경사로는 상하좌우로만 이동할 수 있으며 이전에 방문한 경사로도 방문 할 수 있다. 이때 위 조건을 만족하는 경로의 수를 전부 구해 1000000007로 나눈 나머지를 return하면 된다. HTML 삽입 미리보기할 수 없는 소스 3 ≤ grid의 길이 = n ≤ 8 3 ≤ grid[i]의 길이 = m ≤ 8 0 ≤ grid[i][j.. 2024. 1. 5.

이전 1 2 3 다음

티스토리툴바