Algorithm

https://www.acmicpc.net/problem/117262 x n 크기의 직사각형을 1 x 2, 2 x 1 타일로 채우는 방법의 수를 구하는 프로그램을 작성해야한다. 이는 다이나믹 프로그래밍을 이용하여 해결이 가능하며, 이 문제는 피보나치 수열과 유사한 점화식을 따른다. 이는 다음과 같다. 점화식 유도2 x n 크기의 직사각형을 채우는 방법은 다음 두 가지로 나눌 수 있다.I. 세로로 2 x 1타일을 맨 왼쪽에 하나 놓고 나머지를 채우는 방법II. 가로로 1 x 2 타일을 두 개 놓고 나머지를 채우는 방법 따라서, 첫 번째 경우는 2 x (n - 1) 크기의 직사각형을 채우는 방법의 수와 같고, 두 번째 경우는 2 x (n - 2) 크기의 직사각형을 채우는 방법의 수과 같다. 이를 수식으로 나..

https://www.acmicpc.net/problem/7569이전에 자주 풀어본 bfs 문제이다.다른 문제와 차이가 있다면, 지금까지는 2차원으로 문제를 해결하였는데이번 문제에서 주어진 보기는 3차원으로 해결해야한다.  코드 #include #include using namespace std;int arr[101][101][101]; // 3차원 배열로 변경하여 상자의 개수를 포함시킴int M, N, H;int dx[6] = { 0, 1, 0, -1, 0, 0 }; // 상자의 위, 아래로 이동하는 방향 추가int dy[6] = { 1, 0, -1, 0, 0, 0 };int dz[6] = { 0, 0, 0, 0, 1, -1 }; // 쌓아올려진 상자의 이동은 z축 방향으로 추가int day = 0;v..

https://www.acmicpc.net/problem/1107 브루트포스 알고리즘을 사용하여, 일일히 계산하였다.이때 시작 채널은 100이므로, 100에서 목표 채널을 뺀 수와, 근사치를 구해 횟수를 카운트 한 수를 비교해더 적은 수를 최종 결과로 출력한다.  코드#include #include #include #include #include #include using namespace std;int countDigits(int target, int number) { //횟수 //카운트 비교군 a,b / 이 중 비교하여 카운트가 적은 수를 선택한다. int count_a = abs(target - number); //목표 값 - 근삿값 = 횟수 int count_b = abs(100..

https://www.acmicpc.net/problem/16971차원 선에서 수빈이는 문제에 나온대로 이동한다. BFS를 사용해서 계산한다.초기 큐에 좌표 N을 넣고, 비어있을 때 까지 반복하며 동생(K) 좌표를 찾는다.코드 #include #include using namespace std;int N, K; // N: 수빈이의 위치, K: 동생의 위치bool visited[100001]; // 방문한 위치를 기록할 배열void bfs(int a) { queue> q; // BFS를 위한 큐. 각 원소는 (위치, 시간)을 나타냄 q.push(make_pair(a, 0)); // 수빈이의 현재 위치와 시간 0을 큐에 넣음 while (!q.empty()) { // 큐가 빌 때까지 반복 ..

https://www.acmicpc.net/problem/5525이 문제는 Pn이 몇 군데 포함 되어 있는지 구하는 문제이다. Pn은 N+1개의 I와 N개의 O로 이루어져 있다.마지막에 무조건 I가 나온다는 점을 이용하여 문자열로 코드를 구현하였다.  코드#include #include using namespace std;int N, M;int main() { string S; // 입력 받기 OOIOIOIOIIOII(13) cin >> N; //Pn cin >> M; //입력 글자 수, 반복문에 사용한다 cin >> S; //입력 int count = 0; //몇 군데 포함되어있는지 카운트 for (int i = 0; i 설명주어진 문자열에서 특정 패턴의 반복을..

https://www.acmicpc.net/problem/16928뱀과 사다리 게임을 플레이할 때, 1번 칸에서 100번 칸까지 도착하기 위해 주사위를 최소로 굴린 횟수를 구하는 문제이다.이때 여기서 주어진 입력은 사다리와 뱀의 정보가 주어진다.  최단 경로를 찾아야 하며, 그러기 위해서는 모든 칸을 탐색해야 하고, 방문한 칸을 체크하여 중복으로 방문하는 것을 막아야하니 BFS로 계산하는게 효율적이겠다고 판단하여 BFS로 구현하였다.  코드#include #include #include #include // INT_MAX 사용을 위해 추가using namespace std;vector> ladder;vector> snake;vector moves(101, INT_MAX); // 칸 별 이동 횟수를 저장..

https://www.acmicpc.net/problem/1012 이 문제는 연결된 영역을 찾는 문제로 볼 수 있다. 배추들이 인접해있는 영역을 찾고 각 영역에 대해 최소한의 배추흰지렁이의 수를 계산하면 된다. 코드 #include #include using namespace std; void dfs(vector& field, int x, int y, int m, int n) { //값이 음수이거나, 행렬을 벗어나거나, 이미 방문한 노드, 즉 배추가 없다면 탐색하지 않는다. if (x = m || y = n || field[x][y] == 0) { return; } field[x][y] = 0; // 이미 방문한 배추는 0으로 표시 // 상하좌우로 이동하며 배추가 있는..

https://www.acmicpc.net/problem/1931 이 문제는 회의실을 최대한 활용하여 겹치지 않는 회의를 많이 배정하는 것을 목표로 한다. 이런 유형의 문제는 그리디 알고리즘을 활용하여 효율적으로 해결이 가능하다. 코드 #include #include #include using namespace std; int main() { int n; cin >> n; vector list; for (int i = 0; i > start >> end; list.push_back(make_pair(end, start)); } sort(list.begin(), list.end()); int time = list[0].first; int count..

https://www.acmicpc.net/problem/1874 스택의 LIFO 특성을 이용하여 임의의 수열이 주어졌을 때 스택을 이용해 수열을 만들 수 있는지 알아내는 프로그램을 작성하는 문제이다. 코드 #include #include #include #include using namespace std; int main() { int N; cin >> N; int C = 1; //카운터 vector s(N); //수열 stack stack; //스택 vector o; //+,- for (int i = 0; i > M; if (!stack.empty() && stack.top() == M) { stack.pop(); o.push_back('-'); } else..

https://www.acmicpc.net/problem/1181 정수 N이 주어지고 N개의 줄에 걸처 소문자로 이루어진 알파벳을 단어를 한줄에 하나씩 입력한다. 이때 조건은 다음과 같다. 1. 길이가 짧은 순서대로 2. 길이가 같으면 사전 순으로 (a>b>c) 3. 중복된 단어는 하나만 남기고 삭제 코드 #include #include #include #include #include using namespace std; //N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬 //1. 길이가 짧은 것 부터 //2. 길이가 같으면 사전 순으로, a,b,c //중복된 단어는 하나만 남기고 제거 bool compare(paira, pairb) { if (a.first == b.first) { return a..