본문 바로가기
728x90
반응형

백준 알고리즘55

[백준 1874][파이썬] 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택을 이용하는 문제. 어렵지는 않지만 여러가지 상황들을 고려하는 것이 까다로웠던 문제이다. 나는 다음 세 변수들을 생성하여 서로 값을 비교하면서 문제를 풀었다. 마지막으로 스택에 넣은 값 (이 값은 무조건 1씩 증가) 현재 스택의 가장 위에 있는 값 입력 값 다음과 같은 상황들을 고려하면 된다. 입력 값(3번)이 .. 2023. 2. 23.
[백준 10986][파이썬] 나머지 합 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 특정 수로 나누어 떨어지는 구간 합의 개수를 구하는 문제이다. 모든 (i, j)쌍을 구하면 너무 오랜 시간이 걸린다. 구간 합을 적절히 이용해서 효율적으로 답을 구하는 알고리즘을 짜야한다. 이 문제를 풀기 위해 우선 누적 합을 통해 구간 합을 구하는 방법을 알아야 한다. 백준 11659번 문제를 한 번 풀어보는 것을 추천한다. https://grow.. 2023. 2. 21.
[백준 1004][파이썬] 어린 왕자 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주 www.acmicpc.net 조금만 생각해보면 어렵지 않게 풀 수 있다. 진입/이탈의 최솟값을 구하는 문제이기 때문에 출발점 혹은 도착점을 포함하고 있는 원의 개수를 세면 된다. 원이 점을 포함할 경우 반드시 진입 혹은 이탈을 해야하기 때문이다. 원이 점을 포함하고 있는지 확인을 위해서는 점과 원의 중심사이의 거리를 구하면 된다. 원의 중심과 점 사이의 거리가 원의 반지름보다 작으면 원이 점을 포함한다. 모든 .. 2023. 2. 16.
[백준 11050, 11051][파이썬] 이항 계수 11050번과 11051번은 문제에서 주어지는 입력 값의 범위만 다르고 똑같은 문제이다. 11051번 문제를 기준으로 풀이해보려한다. https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 풀이법은 두 가지로 나뉜다. 1. 반복문 사용 모두 알다시피 조합을 구하는 식은 아래와 같다. $$ nCr =\frac{nPr}{r!} $$ 이렇게 반복문을 사용하여 조합을 구하는 방법이 있다. import sys n, k = map(int, sys.stdin.readline().split()) res=1 for i in r.. 2023. 2. 15.
728x90
반응형