⭐ 코딩테스트
[백준 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[..
[코딩테스트] 동적계획법 (Dynamic Programming) 15문제
[코딩테스트] 동적계획법 (Dynamic Programming) 15문제
2023.06.08이 글은 보호되어 있기 때문에 이것을 보려면 암호가 필요합니다.
[백준 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 ..
[백준 1932번 C/C++] 정수 삼각형
[백준 1932번 C/C++] 정수 삼각형
2023.06.05목차 [백준 1932번 C/C++] 정수 삼각형 해결방안 Dynamic Programming(DP) 코드 #include #include using namespace std; int tri[501][501], sum[501][501]; int main() { int n, maxValue=0; scanf("%d", &n); for (int i = 0; i < n; i++) { for (int j = 0; j
[백준 25192번 C/C++] 인사성 밝은 곰곰이
[백준 25192번 C/C++] 인사성 밝은 곰곰이
2023.06.04목차 [백준 25192번 C/C++]인사성 밝은 곰곰이 https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 시도 1 - vector 사용 #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n, cnt=0; bool flag; cin>>n; string input; vector v; f..