본문 바로가기

전체 글154

[DP] [BOJ 2163] 초콜릿 자르기 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿을 친구들과 나눠 먹기로 했다. 이를 위해서 정화는 초콜릿을 계속 쪼개서 총 N×M개의 조각으로 쪼개려고 한다. 초콜릿을 쪼갤 때에는 초콜릿 조각을 하나 들고, 적당한 위치에서 초콜릿을 쪼갠다. 초콜릿을 쪼갤 때에는 금이 가 있는 위치에서만 쪼갤 수 있다. 이와 www.acmicpc.net 문제 N x M 초콜릿을 1 x 1 초콜릿으로 자르는 최소 횟수를 구하는 문제 해석 이 문제는 DP로도 풀 수 있고 수학으로도 풀 수 있는데, 여기서는 DP로 접근해보자. 우선, 초콜릿은 자르면 더 .. 2020. 3. 24.
[DP] [BOJ 1003] 피보나치 함수 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 피보나치 함수의 변형 문제로, f(n)을 호출할 때, f(0)과 f(1)의 횟수를 각각 출력하는 문제 (f = 피보나치 함수) 해석 오늘은 태블릿을 놓고와서 그림은 없다. 이 문제는 처음에 알쏭달쏭하다. 내가 풀어봤던 피보나치 함수는 함숫값만 구하면 됐는데, 호출 횟수를 구하라니? 그리고 사실은 문제가 2개다. 0을 호출하는 횟수와 1을 호출하는 횟수. 그래서 두 문제를 한꺼번에 풀다 보니 헷갈리는 부분이 있다. 하지만 결국 푸는 방식은 완전히 동일하다. 피보나치 함수에서 f[n] = f[n-1] + f[n-2]라는 식으로 풀었던 것처럼, (f(n)에서.. 2020. 3. 22.
[DP] [BOJ 1149] RGB거리 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 수직선 위의 N개의 집이 있을 때, 인접한 두 집의 색(R, G, B 중 하나)을 같지 않게 칠하는 최소 비용을 구하는 문제. 무식하게 접근하기 + 중복되는 부분 문제 여느 때처럼 모든 경우를 탐색해 보았을 때, 모든 전체 경우의 수는 2 * 3^N이다. N 2020. 3. 20.
[DP] [BOJ 11726] 2 x n 타일링 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 1x2, 2x1 타일로 2xn의 칸을 채우는 문제. 1x2 하나만 놓을 수는 없으므로 결국 2x2, 1x1 타일을 놓는 경우의 수가 된다.아, 근데 경우의 수를 10,007로 나눈 나머지를 출력해야 한다. 중복되는 부분 문제 개인적으로 문제는 처음 문제를 접했을 때, 답이 너무 보이지 않았다. 여느 DP 문제처럼, 2xn 타일은 더 작은 타일을 합쳐서 만들 수 있다는 점을 이용해서 풀 수 있는데, 2 x n 타일링은 2 x (n-1)에 2x1 타일을 붙이거나, 2 x (n-2)에.. 2020. 3. 19.
[DP] [BOJ 9095] 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 문제 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 방법 구하기 예시) 4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 +.. 2020. 3. 18.
[DP] [BOJ 1463] 1로 만들기 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 어떤 자연수 N에 대해서 세 가지의 연산을 할 수 있다. 1. 3으로 나누어 떨어지면 나눈다. 2. 2로 나누어 떨어지면 나눈다. 3. 1을 뺀다. 임의의 자연수는 이 연산을 반복할 경우 1로 만들 수 있다. 어떤 자연수 N에 대해서, 1로 만들기 위한 연산의 최소 횟수를 구하는 문제. 무식하게 접근하기 우선 가장 무식한 방법은 모든 숫자에 대해서 세 가지 연산을 해보는 것이다. 하지만, 각각의 숫자에 대해서 최대 3개의 연산을 할 수 있으므로, 시간복잡도는 $O(3^N)$가 된다. 근데 N = 100,000이므로 절대로 풀 수가 없다. 제출해보니 메모리 초과가 뜬다. .. 2020. 3. 18.
DP 백준 문제 풀이 문제 리스트 다이나믹 프로그래밍 - 1 페이지 다이나믹 프로그래밍 www.acmicpc.net 1. 1로 만들기 2. 1, 2, 3 더하기 2020. 3. 18.
42 Seoul, La Piscine 회고 이 글은 42 Seoul 프로그램의 관문인 온라인 테스트와 La Piscine에 대한 회고이다. (1.20~2.15, 약 4주) 42 Seoul이란 들어가기에 앞서 간단하게 소개를 해보자. 42 Seoul은, 프랑스 Ecole 42의 교육 프로그램을 가져온 것으로 이노베이션 아카데미의 사업 중 하나이다. (벤치마킹이 아니라, 공식 42 Network에 포함되어있다.) 42 Seoul에서는 교육비, 교수, 교재가 존재하지 않고, 교육 시스템으로서 학생에게 프로그래밍을 가르치고 성장시키는 혁신적인 교육 프로그램이다. 파리, 실리콘밸리 등등 캠퍼스마다 기숙사 지원 여부 등이 다르긴 한데, 한국에서는 기숙사는 지원하지 않고 학생이 교육에 집중하도록 월 100만 원 (세후 91.2만 원)의 지원금을 준다. 42 .. 2020. 2. 16.
42 Seoul Piscine에서 C 확실하게 제출하는 법 오늘 42 Seoul에서 처음 C00을 시도하다가 삽질한 기록을 남겨본다. 0. 42 Header란 무엇인가? 42 헤더는 사용자 정보, 생성 및 수정 날짜가 저장되어있는 주석이다. 일부 편집기에 플러그인으로 존재한다. vscode의 42 header 플러그인: 42 Header - Visual Studio Marketplace OverviewQ & ARating & Review This extension provides the 42 header integration in VS Code. # **************************************************************************** # # # # ::: :::::::: # # vscode-42header :+.. 2020. 1. 22.

티스토리툴바