본문 바로가기
728x90

알고리즘316

[C++] 백준 16480 외심과 내심은 사랑입니다. https://www.acmicpc.net/problem/16480 16480번: 외심과 내심은 사랑입니다 수진이는 외심과 내심 없이는 살 수 없다고 말할 정도로 외심과 내심을 사랑한다. 하지만, 갑자기 수진에게 어려운 일이 닥쳤다. 바로 평면에 있는 삼각형 ABC에서 외접원의 반지름의 길이 R이고, www.acmicpc.net 문제 해결 오일러의 삼각형 공식을 알면 풀 수 있고 모르면 풀기 힘든 문제 증명은 중학교 3학년 수준 참고문헌(위키피디아) 오일러 삼각형 정리 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 오일러 삼각형 정리와 그에 필요한 보조선, 보조점들 기하학에서 오일러 삼각형 정리(Euler三角形定理, 영어: Euler's triangle theorem)는 삼각형의 .. 2023. 12. 6.
[python] 백준 1981 배열에서 이동 https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 해결 (1,1)에서 (n,n)까지 가는데 거쳐간 수들 중 최솟값과 최댓값 차이를 구하는 문제 이동하면서 최솟값과 최댓값을 변경해가며 저장하고 갈 수도 있을 것 같은데 그러면 que안에 너무 많은 데이터가 저장이 되어 메모리 제한에 걸린다. 따라서 최솟값과 최댓값을 고정값으로 가져가며 그 안에 수들이 통과하여 이동할 수 있는지 확인해가는 식으로 bfs를 이용할 수 있다는.. 2023. 12. 4.
[python] 백준 30823 건공문자열 https://www.acmicpc.net/problem/30823 30823번: 건공문자열 양의 정수 $N$, $K$와 영어 알파벳 소문자로 구성된 길이가 $N$인 문자열 $S$가 주어진다. reverse(i)를 $S$의 $i, i+1, ... , i+k-1$번째 문자로 이루어진 부분 문자열을 뒤집는 연산이라고 정의하자. $i = 1, 2, www.acmicpc.net 문제 해결 시간초과에 고민을 많이 해보게 된 문제 하나씩 돌리면 당연히 정답이 나오지만 숫자가 500000까지 가능하므로 시간초과가 난다. 따라서 규칙을 찾아야한다. 규칙은 직접 해보면서 찾는 것이 쉽다. 먼저 K번째 문자부터 끝문자까지 순서대로 나온다는 것을 알 수 있다. 그리고 N과 K의 차이가 홀수면 앞에 K-1번째 문자까지 순서대.. 2023. 12. 3.
[python] 백준 2234 성곽 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 문제 해결 우선 숫자에 따라 벽이 존재유무를 확인할 수 있다. 남: 8, 동:4, 북:2, 서:1인 만큼 bfs의 이동방향도 남, 동, 북, 서 순서대로 해서 값을 비교해서 벽의 존재유무를 알 수 있다. 벽이 존재하지 않으면 일반 bfs와 다를바가 없다. 다만 각 영역에 대한 기록을 해야하므로 room_info를 통해 group_num과 땅 사이즈를 위치마다 기록을 한다. 하나의 벽을 허물 .. 2023. 12. 3.
728x90