Algorithm

https://www.acmicpc.net/problem/5430함수 R : 배열에 있는 수를 뒤집는다. 처음에는 배열을 직접 뒤집는 함수를 구현했으나, 시간이 너무 오래 걸려bool을 사용해 함수를 뒤집었다고 인식하게 하였다. (Reverse = false : 뒤집지 않음, Reverse = true : 뒤집음) 함수 D : 배열의 첫번쨰 수를 제거한다. 즉, Reverse = false인 경우 배열의 첫번쨰 수를 제거(front) 하고, Reverse = true인 경우 배열의 마지막 수를 제거한다(end)    배열이 비었을 떄 D를 사용 시 error를 출력한다. 여기까지는 배열만 입력해서 출력하는 간단한 문제인 줄 알았으나,배열을 대괄호 안에 쉼표로 구분하여 입력해야 한다.  getline과 s..

https://www.acmicpc.net/problem/7662문제를 정리하자면,1. 이중 우선순위 큐: 데이터의 삽입과 삭제가 가능한 자료 구조로, 삭제할 때 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터를 삭제할 수 있는 이중 우선순위 큐를 구현한다. 2. 명령어:- I n : 정수 n을 큐에 삽입하는 연산- D 1: 큐에서 최댓값을 삭제하는 연산- D -1: 큐에서 최솟값을 삭제하는 연산 3. 입력과 출력:I. 첫 번째 줄에 테스트 데이터의 수를 나타내는 정수 T, 각 테스트 데이터는 k개의 연산으로 구성된다.II. 각 연산은 문자 ('D' 또는 'I') 와 정수 n으로 이루어져 있다.III. 각 테스트 데이터에 대해, 모든 연산을 처리한 후 큐에 남아 있는 값 중 최댓값과 최솟값을 출력IV..

https://www.acmicpc.net/problem/10026구역을 나누는 문제는 보통 BFS나 DFS로 해결할 수 있다. 필자는 DFS를 이용하였다. 먼저 구역을 나누는 함수를 구현 후, 색약이 바라보는 구역을 구현하기 위해G를 R로 변환하는 함수를 구현한다.   코드#include #include using namespace std;const int dx[] = { -1, 1, 0, 0 };const int dy[] = { 0, 0, -1, 1 };void dfs(vector>& grid, vector>& visited, int x, int y, char color){ visited[x][y] = true; // 방문 위치를 방문했다고 저장 for (int i = 0; i = 0 &&..

https://www.acmicpc.net/problem/30804주어진 문제는 막대에 꽂힌 과일들 중에서 두 종류 이하의 과일만 남도록 앞쪽과 뒤쪽에서 몇 개의 과일을 빼내어 과일의개수가 가장 많은 경우를 찾는 것이다.  조건:1. 과일의 총 개수 N이 주어짐 2. 과일의 종류는 1부터 9까지이며, 각 과일은 S1,S2,....,SN과 같이 나열된다.   3. 앞에서 a개 뒤에서 b개의 과일을 뺼 수 있다. 4. 두 종류 이하의 과일만 남기도록 하여, 남은 과일의 개수가 최대가 되도록 해야 한다.    이 문제를 어떻게 접근해야 할까?접근 방법을 두 케이스로 나눠봤다. 접근 방법:1. 빈도수 카운트:- 각 과일의 빈도 수를 카운트하여, 현재 과일 종류를 추적- 빈도 수를 관리하여, 두 종류를 초과하면 ..

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); // 칸 별 이동 횟수를 저장..