본문 바로가기
반응형

Programming397

[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.
[C/C++] 백준 #2512 예산(이분 탐색) 이번 문제는 예산이 요청되었을 때, 정해진 예산에 맞추어 최대 허용 예산값을 구하는 문제입니다. https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 이 문제는 최대 허용 예산값에 대해서 전체 예산 요청들을 만족하는지 아닌지를 판단할 수 있습니다. 최대 허용 예산값이 커질 수록 당연히 예산 초과가 될 수 있고, 최대 허용 예산값이 작아질수록 예산이 만족하기 때문에 어떤 값 이하에서는 항상 조건을 만족하고 그것을 초과하는 경우에는 항상 조건을 만.. 2023. 6. 12.
[C/C++] 백준 #2504 괄호의 값(스택) 괄호의 짝맞춤은 처음 언어를 배우면서 스택을 이용한 활용 사례로 많이 나오는 편입니다. 복합괄호 형태로 나오게 되는데요. 복합괄호가 아니라면 굳이 스택을 사용하지 않아도 됩니다. 이 문제는 단순한 괄호 짝 맞추기보다 어려운 문제입니다. https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 저는 일단 스택을 두가지 용도로 사용했습니다. 현재까지 계산된 결과를 저장하는 용도와 짝을 맞추는 용도로 썼습니다. 계산될 결과의 경우에는 양수값을 사용하였고.. 2023. 5. 30.
[C/C++] 백준 #2503 숫자야구(브루트포스) 숫자야구는 게임기가 없던 시절에 자주 했던 게임이죠. 숫자위치에 따라서 스트라이크와 볼을 불러주면, 그 결과에 따라서 상대방의 숫자를 맞추는 게임입니다. https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 이번 문제는 기존에 나온 결과를 가지고 가능성이 있는 숫자들의 개수를 알아내는 문제입니다. 이것을 이용하면 사람과 컴퓨터간에 숫자야구 게임을 만들 수도 있습니다. 알고리즘은 상당히 간단합니다. 모든 숫자리스트에 대해서 스트라이크와 볼을 기존 히스.. 2023. 5. 29.
[C/C++] 백준 #2502 떡 먹는 호랑이(구현) 이번 문제는 알고리즘이 무엇이라고 이야기하기가 어렵습니다. 그냥 구현이라고 하도록 하겠습니다. https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 피보나치 수열은 동적 계획법(dynamic programming)이나 재귀함수(recursion)이 나올 때 자주 등장하는 문제입니다. 일반적으로는 첫번째 항이 1, 두번째 항이 1인 경우입니다. 이번 문제는 d번째 항의 값이 주어졌을 때, 가능한 첫번째 항과 두번째 항 중 하나를 출력하면 됩니.. 2023. 5. 28.
728x90