C++

(C++) 백준 2579번 - 계단 오르기

문제 링크 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 다이나믹 프로그래밍을 이용하여 풀이하였다. 2차원 배열을 사용해서 arr[x][0]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟지 않았을 경우, 즉 x-2번째 계단을 밟았을 때로, arr[x][1]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟았을 경우, 즉 x-1번째 계단을 밟았을 때이다. 마지막으로 다이나믹 프로그래밍을 진행할 때 x-2가 인덱스일 때의 값이 필요하므로 초기값으로 ..

(C++) 백준 9095번 - 1, 2, 3 더하기

문제 링크 : https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 활용하여 풀이하였다. 입력이 1일 때 1, 입력 2일 때 2, 입력이 3일 때 4이라는 초기값을 부여해 준 후, 입력값이 i일 때의 값은 arr[i-1]+arr[i-2]+arr[i-3] 임을 이용해 풀이하였다. #include using namespace std; int arr[12]; int T, n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> T; arr[1] = 1; ..

(C++) 백준 1463번 - 1로 만들기

문제 링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 활용하여 풀이하였다. 입력이 1일 때 0, 입력 2일 때 1이라는 초기값을 부여해 주고 그 이후에 상황에 맞춰 1씩 더해주는 방식으로 풀이하였다. #include #include #include using namespace std; int arr[1000002]; int X; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> X; arr[2] = 1; for(int i = 3; i

(C++) 백준 15683번 - 감시

문제 링크 : https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 풀이 백트래킹을 사용하여 풀이하였다. 먼저 전체 사무실에서 CCTV가 위치한 곳의 좌표를 Queue에 넣는다. 다음으로 Queue의 Front에 위치한 CCTV가 스캔할 수 있는 지역을 체크한다. 체크한 뒤 사무실의 정보와 Queue를 함수의 변수로 넘겨가면서 Queue가 빌 때까지 재귀적으로 진행한다. #include #include #include #define X f..

(C++) 백준 2910번 - 빈도 정렬

문제 링크 : https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 문제 풀이 stable_sort와 커스텀 비교 함수를 사용하여 풀이하였다. pair를 사용해 값과 빈도수를 동시에 저장하는 것과 stable_sort를 사용하는 것이 중요하다고 할 수 있다. #include #include #include #define X first #define Y second using namespace std; int n, c; vector v; // 첫번째 int는 값, 두번째 int는 나타난 빈도수..

(C++) 백준 1181번 - 단어 정렬

문제 링크 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 풀이 sort 함수와 커스텀 비교 함수를 사용하여 단어를 정렬하여 풀이를 진행하였다. 다만 C++ vector에서의 중복 제거를 처음 사용해 보아서 조금 어려움도 있었다. ※ unique 함수는 중복된 값들을 뒤로 보내고, 중복된 값들의 시작 위치를 반환한다. ※ erase 함수는 시작 위치부터 종료 위치까지의 값을 모두 제거한다. #include #include #..

(C++) 백준 15657번 - N과 M (8)

문제 링크 : https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 입력받은 수들을 정렬한 후 배열에 들어올 수가 이전에 배열에 삽입된 수보다 작지 않도록 조건만 달아주면 쉽게 풀 수 있다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int i..

(C++) 백준 15656번 - N과 M (7)

문제 링크 : https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 아주 간단한 백트래킹 문제로 N과 M (3) 문제처럼 특별한 조건이 없기에 다른 백트래킹 문제에 익숙하다면 어렵지 않게 풀 수 있는 문제이다. 입력받은 수들을 정렬한 후에 N과 M (3) 문제와 같이 풀이하면 된다. #include #include using namespace std; int n, m; int arr[10]; // ..

(C++) 백준 15655번 - N과 M (6)

문제 링크 : https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용한 풀이이다. 정렬을 한 후에 백트래킹을 하면서 이전에 들어간 수보다 들어갈 수가 더 적다면 그 경우는 건너뛰는 식으로 구현한다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int isUsed[..

(C++) 백준 15654번 - N과 M (5)

문제 풀이 : https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. N과 M (1)과 따로 입력값을 정렬해야 한다는 점만 제외하면 거의 동일한 문제이다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int isUsed[10]; void nNm(i..