문제 풀이/백준37 [S4] 백준 2417 - 정수 제곱근 (python3) https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 해결방법 0과 n(n>=0) 의 중앙값의 제곱이 n과 같은지, 큰지, 작은지를 따져보며 q를 구해내는 해결 방법이다. n과 m의 중앙값의 제곱은 앞으로 'n과 m의 중앙제곱'이라고 부르겠다. 만약 0과 n의 중앙제곱이 n과 같다면 그 값이 정답이다. ( 0과 4의 중앙제곱 = 2, 2^2 = 4) 만약 0과 n의 중앙제곱이 n보다 크다면 mid와 n의 중앙제곱을 비교한다. 만약 0과 n의 중앙제곱이 n보다 작다면 0과 mid의 중앙제곱을 비교한다. 위 조건문 안에서는 low와 high를 업데이트 해주는 작업도 반드시.. 2023. 1. 19. [S3] 백준 2512 - 예산 (Python3) https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 해결방법 이분 탐색으로 풀이한다. 풀이👀 최소값과 최대값을 lo와 hi라고 하고, 그 안에서 binary search를 한다. 동작 과정은 아래와 같다. mid = (lo + hi) // 2 라 한다. ① mid를 상한액으로 지정한 뒤, 지방의 예산요청을 계산하여본다. 만약 합산한 게 국가예산을 넘어서면 hi = mid로 하여 다시 계산하고, 반대로 국가예산보다 적다면 lo = mid로 하여.. 2023. 1. 18. [S2] 백준 1012 - 유기농 배추 (Python3) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결방법 배추가 상하좌우로 모여 있는 곳 하나당 필요한 배추흰지렁이 수가 된다. 그러므로 이렇게 모여있는 군집이 몇 개 인지만 파악하여 출력하는 것이 목표이다. 파악하는 방법은 DFS, BFS 등이 있는데 이 글에선 BFS를 다루고 있다. grid를 일일이 탐색하다가 배추가 있는 자리라고 표시해둔 곳을 마주치게 되면, BFS를 통해서 상하좌우에 위치한 배추들을 0으로 바꾸어준다. 0으로 바꾸는 이유는 '탐색을.. 2023. 1. 15. [S2] 백준 11568 - 민균이의 계략 (Python3) https://www.acmicpc.net/problem/11568 해결방법 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)의 기초 문제이다. 이전에 이 시리즈를 풀어본 경험이 있어서 풀이의 틀은 쉽게 잡았다. 나는 시간복잡도가 O(n^2) 인 알고리즘으로 문제를 풀었다. arr의 길이가 최대 1,000 이므로 O(n^2)은 1,000,000이라 제한시간(1초) 안에 충분히 통과가 가능하다. 더 빠른 방법은 O(n log n) 있다. n=1000 일때, n log n = 3000 이므로 더 빠르게 통과할 것이다. 풀이 이 문제의 풀이는 arr에 있는 각 원소를 주목해야 한다. arr에 있는 원소들을 반복문으로 앞에서부터 차례차례 접근할 것이다. 이때 그 원소가 이 .. 2023. 1. 15. [S3] 백준 21921 - 블로그 (Python3) https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 해결방법 구간 합 중 가장 큰 값이 무엇이며, 그 값이 몇 번 나오는지 파악해야 하는 문제로 누적합과 슬라이딩 윈도우를 이용할 줄 알아야 한다. 코드 N, X = map(int, input().split()) arr = list(map(int, input().split())) prefix = [0] for i in range(N): prefix.append(prefix[i] + arr[i].. 2023. 1. 14. [S4] 백준 4949 - 균형잡힌 세상 (Python3) https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 이 문제보다 한 단계 쉬운 문제는 백준 9012번: 괄호라고 생각한다. 이 문제를 풀고나서 이 문제를 푸는 것을 추천한다. 해결방법 스택을 활용하는 문제이다. bracket 이라는 리스트 변수에 여는 괄호("(", "[")를 담고, 닫는 괄호(")", "]")가 나올 때마다 bracket의 원소를 pop 해주는 방식으로 문제를 풀었다. 코드 while (string:=inpu.. 2023. 1. 14. [S5] 백준 26517 - 연속인가? ? (Python3) https://www.acmicpc.net/problem/26517 26517번: 연속인가? ? 실수 $t$에 대하여, 함수 $f(x)$가 $x=t$에서 정의되어 있고, $\lim_{x \rightarrow t} f(x) = f(t)$인 경우 "$f(x)$는 $x=t$에서 연속이다"라고 한다. 함수 $f(x) = \begin{cases}ax+b & (x \leq k)\\ cx+d & (x > k)\end{cases}$가 주 www.acmicpc.net 해결방법 고등학교 수학 시간에 배웠던 개념을 잊지 않고 있어서 풀 수 있던 문제였다. 주어진 함수가 x=k에서 연속인지 판단하는 방법은 좌극한과 우극한이 같은지 확인하면 된다. 같다면 연속, 다르면 불연속. 코드 k = int(input()) a, b, c.. 2023. 1. 10. [Python] 백준 5430 - AC https://www.acmicpc.net/problem/5430 해결방법 문제에 나와있는 대로 따르면 충분히 풀 수 있는 문제이긴 하다. 하지만 곧이곧대로 따르기만 하면 여러 가지 문제로 해결이 불가능하다. 코드 tc = int(input()) for _ in range(tc): command = input() arr_len = int(input()) input_raw_arr = input() raw_arr = list(map(str, input_raw_arr)) raw_arr.pop(0); raw_arr.pop(-1) arr = (''.join(raw_arr)).split(',') error = False # True: 에러 on, False: 정상작동중 head = True # True: 앞부터 읽.. 2022. 5. 29. 이전 1 2 3 4 5 다음
