devBB 메모장

백준 온라인 저지(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 ..

백준 온라인 저지(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) 함수가 주어져있지만 그 방식 그대로 구현하면 시간 초과가 발생합니다. 시간 초과가 발생하지 않도록 불필요한 반복을 줄이려면 동적 계획법을 사용하면 됩니다. 동적 계획법은 용어 자체가 직관적이지 않은..

백준 온라인 저지(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에 도달한 경우 팀..

백준 온라인 저지(BOJ) 14888번 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 * 사용언어 : C언어, C++ 1. 문제 N개의 숫자와 N-1개의 연산자(+, -, *, /)가 주어졌을 때 숫자 사이에 연산자를 하나 씩 끼워넣어 만들 수 있는 결과의 최대값과 최소값을 출력 단, 연산자 우선 순위는 무시하고 앞에서부터 순서대로 연산함 (결과는 -10억보다 크거나 같고 10억보다 작거나 같음, 중간 결과도) 2. 풀이 DFS를 활용하여 간단하게 풀 수 있는 문제입니다. N개의 숫자를 1차원 배열에 넣고, 배열의 index를 DFS의 depth로 보는 방식입니다. 문제에서 연산자의 개수는 search 알고리즘에서 흔히 사용하는 visited 배열처럼 제공됩니다. 이..

백준 온라인 저지(BOJ) 2580번 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 9 * 9 크기의 스도쿠를 풀고 출력 (빈 칸은 0으로 주어짐) 2. 풀이 1) 설계 다른 백트래킹 유형의 문제들과 마찬가지로 DFS를 기반으로 구현했습니다. 풀이의 핵심인 재귀 함수(sudoku)의 내부 구조는 아래와 같습니다. 모든 숫자를 채운 경우 (depth == 81) 정답 출력 후 종료 모든 숫자를 ..

백준 온라인 저지(BOJ) 9663번 N-Queen https://www.acmicpc.net/problem/9663 * 사용언어 : C언어, C++ 1. 문제 N * N 체스판에 퀸 N개를 배치했을 때 서로 공격할 수 없도록 놓는 방법의 수를 출력 (퀸은 가로, 세로, 대각선을 거리 제한 없이 이동하며 공격할 수 있음) 2. 풀이 DFS를 활용하는 전형적인 형태의 백트래킹 문제입니다. 2차원의 체스판이 있다고 했을 때 row를 DFS의 깊이로 보고 각 column을 배치되는 위치로 보고 DFS로 풀었습니다. (각 row에 1개의 퀸만 배치 가능 → 각 row에서 어떤 column을 사용하냐를 결정하는 DFS) 통상 DFS는 visited라는 배열을 만들고 해당 노드를 방문했다고 1로 표시하는 것이 일반..

백준 온라인 저지(BOJ) 15652번 N과 M (4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N개의 수에서 M개의 숫자를 뽑아 나열하는 모든 경우를 출력 (숫자 중복 허용, 비내림차순 수열만) 2. 풀이 아래 (3)번 풀이로 작성한 코드에서 약간만 수정하여 풀었습니다. for문을 통해 재귀함수를 타는 부분(수열의 다음 자리 숫자를 지정하는 부분)에서 시작 숫자를 1부터가 아닌 직전 자리의 ..