반응형 Programming401 [C/C++] 백준 #2565 전깃줄(가장 긴 증가하는 부분수열) 이번 문제는 백준내에서도 아주 자주 나오는 가장 긴 증가하는 부분수열(LIS; Longest Incremental Sub-sequence) 문제입니다. 전깃줄이 꼬이지 않게 배열하기 위해서 몇개의 전깃줄을 없애야 하는 문제입니다. https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 그동안 제가 작성했던 가장 긴 증가하는 부분 수열 문제들을 모아두면 다음과 같습니다. https://sdev.tistory.com/1384 https://sdev.tistory.. 2023. 7. 19. [C/C++] 백준 #2564 경비원(구현) 이번 문제는 기하학적인 이해만 있어도 구현하기가 편합니다. https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 모든 좌표를 기준점에서 시계방향으로 돌 때의 거리로 계산을 하면, 두 지점 사이의 거리를 계산하기 편합니다. A->B 로 가는 거리와 B->A로 가는 거리 중에 짧은 것을 선택하면 되겠죠. 제 경우에는 시계방향으로 돌 때, 왼쪽 아래를 기준점으로 하여서 계산을 했습니다. 이러면 수직선상에 한 점으로 표시될 수 있는데요. 실제 시작지점과 끝지점은.. 2023. 7. 18. [C/C++] 백준 #2553 마지막 팩토리얼 수(수학) 이번 문제는 수학의 구조를 잘 알고 있으면 크게 문제 없이 풀 수 있습니다. https://www.acmicpc.net/problem/2553 2553번: 마지막 팩토리얼 수 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다. www.acmicpc.net 이번 문제는 팩토리얼 계산을 하고, 마지막에 연속된 0을 제외한 마지막 숫자를 출력하는 프로그램입니다. 프로그램으로 작성할 때에는 2라는 소인수와 5라는 소인수를 미리 제거하고, 끝자리만 계산하시면 됩니다. 2의 소인수의 개수가 5의 소인수의 개수보다 크므로, 나머지 2의 소인수의 개수를 가지고 최종 계산을 해주면 됩니다. 사실 2의 거듭제곱을 하면, 끝자리 숫자가 2, 4, 8, 6 을 반복하기 때문에 이를 이용하면 루프를 돌리.. 2023. 7. 8. [C/C++] 백준 #2529 부등호(탐욕 알고리즘) 이번 문제는 백트래킹(back tracking) 기법을 사용하면 편하게 풀 수 있는 문제입니다. 큰 수의 경우에는 9부터 원하는 개수만큼, 작은 수의 경우에는 0부터 원하는 개수만큼 선택해서 그것으로 백트래킹을 하면 됩니다. 저는 조금 다른 식으로 풀어보았습니다. https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 바로 탐욕 알고리즘을 이용해서 큰 수가 들어가야할 위치를 찾는 것이죠. 예를 들어서 (1) (4) ... 형.. 2023. 6. 24. [C/C++] 백준 #2527 직사각형(수학) 도형에서 위치를 가지고 겹침 판정을 하는 것은 꽤 어려운 일입니다. 이러한 겹침판정은 게임 등에서 충돌이 발생했는지 판정하기 위해서 많이 사용됩니다. 그 중 가장 간단한 판정법은 구(또는 원) 판정입니다. 구 판정법은 두 중심의 거리와 반지름의 합으로 손쉽게 판정을 할 수 있습니다. 다음으로 간단한 것이 축에 평행한 직육면체(또는 직사각형) 판정입니다. 이러한 판정법은 AABB(Axis Aligned Bounding Box)라고 해서 경계 박스 충돌 검사에서 많이 활용됩니다. 이번 문제는 2차원 평면에서 직사각형 충돌 판정을 하는 문제입니다. https://www.acmicpc.net/problem/2527 2527번: 직사각형 4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나.. 2023. 6. 22. [C/C++] 백준 #2517 달리기(병합 정렬) 이번 문제는 정렬해서 풀었습니다. 세그먼트 트리를 이용해도 됩니다. 알고리즘 효율은 비슷하겠죠. https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 www.acmicpc.net 정렬은 기본정렬과 고급정렬, 그리고 특수정렬이 있습니다. 특수정렬이 가장 빠르지만, 일반적으로 사용하기 어려운 경우가 많습니다. 기본정렬과 고급정렬은 모두 비교정렬인데, 기본정렬의 시간 복잡도가 \(O(N^2)\)인 데 비해서 고급정렬의 시간 복잡도는 \(O(N \log N)\)입니다. 고급정렬은.. 2023. 6. 16. 이전 1 2 3 4 5 6 ··· 67 다음 728x90
