devBB 메모장

백준 온라인 저지(BOJ) 2579번 계단 오르기 https://www.acmicpc.net/problem/2579 * 사용언어 : C언어, C++ 1. 문제 점수가 쓰여진 300개 이하의 계단을 한 계단 or 두 계단 씩 오를 때 지나온 계단의 총 점수의 최대값을 출력 (단, 연속된 세 개의 계단을 밟을 수 없고, 마지막 계단은 반드시 밟아야 함) 2. 풀이 bottom-up 방식으로 풀기 위해서 크기가 N * 2인 2차원 배열을 선언했습니다. 배열의 i번(1차원) index에 있는 2개의 값은 각각 [① i번 계단에 도착하기 직전에 한 계단을 올라왔을 때의 최대값]과 [② 두 계단 올라왔을 때의 최대값]을 구해서 저장합니다. 그리고 마지막에 dp[N - 1][0]과 dp[N - 1][1] 중 큰 값을..

백준 온라인 저지(BOJ) 1932번 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 크기가 N인 정삼각형에 각 숫자가 채워져 있음 맨 위층부터 대각선 왼쪽, 오른쪽 둘 중 하나를 선택해서 내려올 때 합이 최대가 되는 경로에 있는 수의 합을 출력 2. 풀이 규칙이 명확하게 주어진 문제이기 때문에 bottom-up 방식으로 구현하였습니다. 우선 정사각형을 주어진 그대로 2차원 배열로 입력을 받습니다. 그리고 각 위치의 숫자에 왼쪽 위(x - 1) dp 값과 오른쪽..

백준 온라인 저지(BOJ) 1149번 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N개의 집을 R, G, B 중 하나의 색으로 칠해야 함 각각의 집을 색칠하는 비용이 주어질 때, 인접한 집의 색이 다르도록 모든 집을 칠하는 비용의 최소값을 출력 2. 풀이 N번 집을 Red로 색칠할 때의 총 비용은 [N번 집 Red 색칠 비용] + min([N - 1번 집 Green ..

기간 : 20240221, 20240226 (2회 독) 기억하고 싶은 문장 "꼭대기에는 뭐가 있지? 우리는 어디로 가고 있는 거지?" "저 위에 무엇이 있는지는 모르지만, 이런 짓을 하면서까지 올라갈 가치는 없어." 노랑 애벌레는 올라가는 것만이 꼭 높은 곳에 이르는 길은 아니라는 것을 깨달았습니다. 내용 정리 호랑 애벌레가 애벌레 기둥을 기어오르기 시작함 기둥을 오르다가 만난 노랑 애벌레와 함께 기둥을 내려와 살아감 호랑 애벌레는 노랑 애벌레를 남겨두고 혼자서 다시 기둥을 오름 그리고 꼭대기에 도달한 후에 그곳에는 아무 것도 없다는 것을 알게 됨 그 때 나비가 된 노랑 애벌레가 호랑 애벌레 곁에 나타남 호랑 애벌레는 무언가 깨달음을 얻고 노랑 나비를 따라 기둥을 내려옴 그리고 노랑 나비를 따라 고치 속..

백준 온라인 저지(BOJ) 9461번 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 아래 그림과 같이 삼각형들이 나선 모양(시계 방향)으로 놓여져 있음 P(N)은 나선 중 N번째 정삼각형의 변의 길이일 때 P(N)을 출력 2. 풀이 수열의 규칙을 찾아 bottom-up 방식으로 구현하여 풀면 됩니다. 초반 삼각형들을 살펴보면 규칙이 잘 안 보이는데 오히려 그림에서 큰 삼각형(7, 9, 12 등..

백준 온라인 저지(BOJ) 1904번 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이www.acmicpc.net* 사용언어 : C언어, C++ 1. 문제1 하나로 이루어진 타일 또는 0타일 두 개를 붙인 00타일로 만들 수 있는 크기가 N인 타일(2진 수열)의 개수를 출력 N은 최대 1,000,000이고, 출력은 수열의 개수를 15,746으로 나눈 나머지로 출력 2. 풀이단순 재귀로 구현하면 시간 초과가 발생합니다. 동적 계획법에 속하는 문제인 만큼 dp[] 배열을 선언..

백준 온라인 저지(BOJ) 9184번 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 문제에 주어진 w(a, b, c)를 구현하여 출력하는 프로그램을 작성 2. 풀이 문제에 w(a, b, c) 함수가 주어져있지만 그 방식 그대로 구현하면 시간 초과가 발생합니다. 시간 초과가 발생하지 않도록 불필요한 반복을 줄이려면 동적 계획법을 사용하면 됩니다. 동적 계획법은 용어 자체가 직관적이지 않은..

공식 홈페이지나 각종 웹사이트(블로그 후기 등)에서 제가 원하는 답변을 찾지 못했을 때 특정 업체나 가게에 직접 전화해서 나누었던 대화를 정리해둔 글입니다. 게시글을 작성한 시점 쯤에 확인한 내용임을 다시 한 번 강조드리고, 확실하게 확인해야 한다면 직접 전화를 걸어보시기를 권장드립니다. 1. 일시 2024년 2월 24일(토) 10시 경 2. 장소 배달의 민족 고객안심센터 https://place.map.kakao.com/64266255 배달의 민족 서울 송파구 백제고분로 478 (방이동 149-4) place.map.kakao.com * 전화번호 : 1600-9880 (배민 앱 > my배민 > 문의 및 알람 > 고객센터 > 고객안심센터 상담) 3. 통화 전 상황 - 8시 50분 경 주문 > 9시 반 도..

백준 온라인 저지(BOJ) 24416번 알고리즘 수업 - 피보나치 수 1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 n의 피보나치 수를 2가지 방식으로 구할 때 두 코드의 실행 횟수를 출력 (① 재귀, ② 동적 계획법) 2. 풀이 동일한 연산의 반복으로 결과값을 구하는 경우 top-down 방식, bottom-up 방식으로 구분이 되는데 두 가지 방식을 구현해보고 비교해볼 수 있는 ..

백준 온라인 저지(BOJ) 14889번 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N(짝수)명의 사람을 두 개 팀으로 나눔 i번 사람과 j번 사람이 팀이 되면 Sij + Sji 만큼 팀 능력치가 올라감 두 개 팀의 능력치의 차이가 최소가 되도록 팀을 구성하고 그 차이를 출력 2. 풀이 DFS를 활용하여 depth가 N / 2가 될 때까지 한 팀으로 구성합니다. base condition에 도달한 경우 팀..