프로그래밍 공부 노트

https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 이용해 수열의 값을 저장하는 문제이다. 이 때 만들어지는 수열의 밀도가 높지 않고, 인덱스와 값의 범위가 int를 넘어갈 수 있으므로 long long을 이용해야 한다. #include #include using namespace std; typedef long long ll; // A[i]: 수열 A를 저장할 공간 map A; // A[k]를 생성할 때 사용할 두 변수 int P, Q; // A[idx]가 호출된 적이 없다면 해당 값을 채운 뒤 그 값을 반환한다 ll get(ll idx) { if (!A[idx]) ..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 큐를 이용해서 K - 1번 push와 pop을 반복해도 좋지만, K번째 원소를 바로 찾을 수 있는 배열을 이용하는 것이 더욱 빠른 문제이다. #include #include using namespace std; int main() { // N: 순열의 길이, K: 순열의 점프 크기 int N, K, idx = 0; vector v; // 문제의 조건을 입력받은 뒤 순열을 오름차순으로 채운다 scanf("%d %d", &N, &K); for (int i = 0; i < N; i++) v.p..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 각 파티를 그래프, 파티에 참여하는 사람을 노드, 서로 만난 사람의 관계를 에지, 처음에 진실을 아는 사람을 탐색 시작 노드로 치환하면 이 문제는 그래프 탐색 문제가 된다. 우선 진실을 아는 사람, 그러니까 탐색을 시작할 노드 번호를 입력받고 파티, 그러니까 연결되지 않은 그래프를 입력받아 저장한다. 그리고 탐색 시작 노드로부터 각 그래프에 대해 탐색을 진행하면 탐색한 그래프와 탐색하지 않은 그래프로 나뉘게..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 주어진 문제에서 2번 연산을 k번 하는 것은 3번 연산을 N - k번 하는 것과 같다. 또 2번 연산은 큐의 맨 앞 원소를 push한 뒤 큐에서 원소를 pop하는 것으로 볼 수 있기 때문에, 이 문제는 큐를 이용해서 간단하게 풀 수 있다. #include #include using namespace std; int min(int a, int b) { return a < b ? a : b; } ..