알고리즘

[BOJ/C++] 11726번 2xn 타일링 : DP(다이나믹 프로그래밍)

문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 문제해결 1. 테이블 설정 D[i] = 2 X i 일때 가능한 방법의 수 코드 #include #include #include using namespace std; int arr[10001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; arr[1] = 1; arr[2] = 2; for (int i..

[BOJ/C++] 1149번 RGB 거리: DP(다이나믹 프로그래밍)

문제 설명 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000..

[BOJ/C++,Kotlin] 2579번 계단오르기 : DP(다이나믹 프로그래밍)

문제 설명 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계..

[알고리즘] 이진탐색 알고리즘 (Binary Search)

이진탐색 알고리즘 (Binary Search) 란? 정렬된 배열에서 검색 범위를 반으로 줄여나가면서 해당 값이 배열안에 있는지를 찾는 알고리즘이다. 이진탐색 알고리즘은 반드시 정렬된 배열에서만 사용할 수 있다. 예시로 A라는 값을 찾으려고 할 때 맨 처음 A와 중간 값을 비교하고, A가 더 크다면 중간에서 오른쪽을 탐색, A가 작다면 중간에서 왼쪽을 범위로 탐색을 한다. 이 과정을 반복하여 해당 값이 있는지를 찾아낸다. 사진과 같이 이진탐색이 이루어진다. 이진탐색 코드 구현 #include #include using namespace std; bool compare(int a, int b) { return a < b; } int main() { ios::sync_with_stdio(0); cin.tie(..

[BOJ/C++] 9095번 1,2,3 더하기 : BFS or DP(다이나믹 프로그래밍)

문제 설명 정수 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보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 문제풀이 1. DP 다이나믹 프로그래밍을 통해서 풀 수 있다. D[i] 를 1,2,3을 더해서 i를 만들 수 있는 횟수로 둔다. 점화식을 만들기 위해 4 예시를 보면 아..

[BOJ/C++] 1463번 1로 만들기 : BFS or 다이나믹 프로그래밍(DP)

문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 문제해결 1. BFS 일차원 행렬의 BFS 문제처럼 초기값을 1로 두고 1에서 입력한 N 값에 가장 최소한으로 도달하는 거리를 구하면된다. 처음에 코드를 구현했을 때 100%에서 틀렸습니다가 떴는데 바로 1일 때 케이스를 확인하지 못해서 발생한거였다. 큐를 pop하고..

[BOJ/C++] 7576번 토마토 : BFS 시작점 여러개

문제 설명 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 ..

[BOJ/C++] 4179번 불! : BFS 시작점 종류 여러개

문제 설명 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간은 통과하지 못한다. 입력 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자들은 다음을 뜻..

[BOJ/C++] 1697번 숨바꼭질 : BFS 일차원 행렬

#include #include using namespace std; int dist[100002]; int main() { ios::sync_with_stdio(0); cin.tie(0); int N, K, time = 0; cin >> N >> K; fill(dist, dist + 100001, -1); dist[N] = 0; queueq; q.push(N); while (dist[K]==-1) { int cur = q.front(); q.pop(); for (int dir : {cur-1,cur+1,2*cur}) { if (dir = 100000) continue; if (dist[dir]!=-1) continue; dist[dir] = dist[cur] + 1; q.push(d..

[BOJ/C++] 2178번 미로 : BFS 거리 측정

분류 너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal) 문제 설명 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N..

[BOJ/C++] 1926번 그림 : BFS

문제 설명 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다. 입력 첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다) 출력 첫째 줄에는 그림의 개수, 둘째 줄에는 그 중 가장 넓은 그림의 넓이를 출력하여라. 단,..

[바킹독 알고리즘] 0x09강:BFS in 다차원 배열

BFS: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 사진만으로 이해가 어렵다면 바킹독 알고리즘 영상을 직접 보면 이해가 더욱 쉬울 것이다. 정리 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행한다. 3. 해당 칸을 이전에 방문했다면 아무 것도 하지않고, 처음으로 방문했다면 방문표시를 남기고 해당 칸을 큐에 삽입한다. 4. 큐가 빌때까지 2번을 반복한다. 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. BFS 구현 코드 ver C++ #include #include using namespace std; #define X first #define Y second int..