728x90 반응형 백준 알고리즘55 [백준 2110][파이썬] 공유기 설치 https://www.acmicpc.net/status?user_id=sungmin123&problem_id=2110&from_mine=1 채점 현황 www.acmicpc.net 이진 탐색으로 푸는 문제이다. 먼저 좌표를 정렬한다. 거리의 최솟값(low)은 1이고 거리의 최댓값(high)은 첫 번째 집부터 마지막 집까지의 거리이다. 두 값이 인자로 들어오면 그 중간값(mid)을 구하고 중간값이 조건에 부합하는지 확인한다. 부합한다면 첫 번째 인자로 mid+1, 두 번째 인자로 high를 넣어주고 다시 한 번 이진 탐색을 수행한다. low>high가 되는 순간 멈춘다. 이 문제에서 조금 까다로운 부분이 중간값이 조건에 부합하는지 확인하는 방법이다. 가장 인접한 두 공유기 사이의 거리가 중간값보다 크거나 같.. 2023. 3. 2. [백준 1629][파이썬] 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 이 문제를 해결하기 위해선 알아야하는 수학적 지식이 있다. (a*b)%c=((a%c)*(b%c))%c 위 공식을 사용하면 이 문제를 분할 정복 방식으로 해결할 수 있다. 예를 들어 3을 12번 곱한 값을 7으로 나눈 나머지를 구한다면 3을 6번 곱한 값을 7로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다. 3을 6번 곱한 값을 7로 나눈 나머지는 3을 3번 곱한 값을 7으로 나눈 나머지를 구하고 이를 제곱하여 다시 7로 나누면 된다. 이렇게 하향식.. 2023. 2. 28. [백준 1541][파이썬] 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 식은 +와 -로만 이루어져있고 괄호를 적절히 쳐서 최소값을 구하는 문제이다. 즉 식을 뺄 때는 괄호를 적절히 쳐서 최대한 큰 값을 빼야한다. 50 + 40 - 30 + 40 +20 - 10 + 20 위와 같은 식이 있다고하자. 식에서 -가 나오면 그 값부터 다시 - 가 나오거나 식의 끝까지 괄호를 치면 된다. 50 + 40 - (30 + 40 +20) - (10 + 20) 파이썬의 경우 문자.. 2023. 2. 27. [백준 5430][파이썬] AC https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 파이썬 자료구조 deque와 문자열 관련 메소드를 사용해서 푸는 문제이다. 문제 자체는 어렵지 않으나 시간을 줄이는 알고리즘을 선택해야한다. 이 문제를 풀기 위해 다음과 같은 문자열 관련 메소드들을 알아야한다. 문자열에서 특정 문자를 없애는 방법 특정 문자를 기준으로 문자열을 나누어 리스트로 만드는 방법 리스트 각각의 요소들을 합치는데 특정 문자로 구분하여 합치는 방법 1. 문자열에서 특정 문자를 없애는 방법 문자열 메소드 replace를 사용하여 없앨.. 2023. 2. 25. 이전 1 ··· 4 5 6 7 8 9 10 ··· 14 다음 728x90 반응형
