본문 바로가기
반응형

Programming456

[C/C++] 백준 #2567 색종이-2(구현) 이번 문제는 색종이를 붙였을 때, 차지하는 둘레를 구하는 것으로 구현을 하면 됩니다. https://www.acmicpc.net/problem/2567 2567번: 색종이 - 2 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 색종이를 아무 방향이나 붙인다면 아주 어려운 문제가 되겠지만, 축에 평행하게만 붙이고 눈금에 맞추어 붙이기 때문에 색칠하기 문제로 전환해서 풀 수 있습니다. 색종이를 붙일 판을 배열로 설정하고, 색종이를 붙이면 그 영역만큼 색칠하면 됩니다. 물론 트리형태로 만들면 더 빠른 속도로 색칠할 수 있겠지만, 여기서는.. 2023. 7. 23.
[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.
728x90
반응형

티스토리툴바