⭐ 코딩테스트/백준
[백준 10844번 C/C++] 쉬운 계단 수
[백준 10844번 C/C++] 쉬운 계단 수
2023.06.20목차 [백준 10844번 C/C++] 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 해결전략 Dynamic Programming (DP) 동적계획법 코드 #include using namespace std; int dp[101][11]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i=1; i
[백준 1966번 C/C++] 프린터 큐
[백준 1966번 C/C++] 프린터 큐
2023.06.17[백준 1966번 C/C++] 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 해결전략 Queue Priorty Queue Queue에 make_pair로 인덱스 번호와 값을 동시에 담는다. 값이 정렬되어 들어가는 PriorityQueue와 Queue를 비교하며 cnt을 한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.t..
[백준 9663번 C/C++] N-Queen
[백준 9663번 C/C++] N-Queen
2023.06.17[백준 9663번 C/C++] N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해결전략 Backtracking 백트래킹 코드 #include using namespace std; int n; int col[15]; int answer = 0; bool isPossible(int level) { for (int i = 0; i < level; i++) { // 같은 열에 있는 경우 if (col[i] == col[level]) return fals..
[백준 1463번 C/C++] 1로 만들기
[백준 1463번 C/C++] 1로 만들기
2023.06.15[백준 1463번 C/C++] 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 해결전략 동적계획법 (Dynamic Programming) DP dp[1] = 0 코드 #include #include using namespace std; int main(){ std::ios::sync_with_stdio(false); std::cin.tie(NULL); int n; cin >> n; vector dp(n+1); dp[1] = 0; dp[2] = 1; dp[3] = 1; for (int i = 4; i
[백준 11866번 C/C++] 요세푸스 문제 0
[백준 11866번 C/C++] 요세푸스 문제 0
2023.06.14목차 [백준 11866번 C/C++] 요세푸스 문제 0 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 해결전략 코드 #include #include #include using namespace std; vector v; queue Q; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k, input, cnt=0; cin >> n >> k; for(int i=1; i
[백준 11047번 C/C++] 동전 0
[백준 11047번 C/C++] 동전 0
2023.06.13목차 [백준 11047번 C/C++] 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 해결전략 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘 해결전략 문제에 따라 최적해의 구성 요소를 선택하기 위한 기준을 정한다. 초기 해답을 비어있는 상태 또는 어떠한 형태로 설정한다. 선택 기준에 따라 해답에 요소를 추가하거나 선택한다. 선택한 요소를 기준으로 다음 요소..
[백준 1874번 C/C++] 스택 수열
[백준 1874번 C/C++] 스택 수열
2023.06.12목차 [백준 1874번 C/C++] 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 해결전략 Stack 사용 코드 #include #include #include using namespace std; stack st; vector v; int main() { std::ios::sync_with_stdio(false); std::cin.tie(NULL);..
[백준 1181번 C/C++] 단어 정렬
[백준 1181번 C/C++] 단어 정렬
2023.06.10글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다 목차 [백준 1181번 C/C++] 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 해결전략 set 사용 set은 원소를 넣을 때 오름차순으로 정렬되어 들어..
[백준 11650번 C/C++] 좌표 정렬하기
[백준 11650번 C/C++] 좌표 정렬하기
2023.06.09목차 [백준 11650번 C/C++] 좌표 정렬하기 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 해결전략 2차원 벡터를 생성한 후 첫 번째, 두 번째에 값을 담아준다. sort로 오름차순으로 정렬한다. 코드 #include #include #include using namespace std; vector v; int main() { int n, a, b; cin >> n; v.resize..
[백준 2579번 C/C++] 계단 오르기
[백준 2579번 C/C++] 계단 오르기
2023.06.09목차 [백준 2579번 C/C++] 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 해결전략 Dynamic Programming (DP) 도착지점이 i번째 계단이라면 올라가는 방법은 ( i - 3 )번째 계단에서 2칸 올라간 후 ( i - 1)번째 계단에서 1칸 올라가거나 ( i - 2 )번째 계단에서 2칸으로 올라가거나 둘 중 하나이다. 코드 #include #include using namespace std; int n; int stair[..
[백준 1920번 C/C++] 수 찾기
[백준 1920번 C/C++] 수 찾기
2023.06.08목차 [백준 1920번 C/C++] 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 해결전략 값으로 검색이 가능한 set 사용 emplace로 값을 set에 넣어주고 iterator로 값을 검색한다. 코드 #include #include using namespace std; set mySet; int main() { std::ios::sync_with_stdio(false); std::c..
[백준 7785번 C/C++] 회사에 있는 사람
[백준 7785번 C/C++] 회사에 있는 사람
2023.06.07목차 [백준 7785번 C/C++] 회사에 있는 사람 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 해결전략 set을 사용. key값에 사람 이름을 넣고 찾아서 접근 후 제거. 코드 #include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin ..