본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[python] 백준 5376 소수를 분수로 https://www.acmicpc.net/problem/5376 5376번: 소수를 분수로 유리수 분수를 소수로 나타내면, 소수점 아래 자리가 유한 개인 경우(1/8 = 0.125)와 어떤 자리에서부터 일정한 숫자가 한없이 되풀이 되는 경우(1/11 = 0.090909...)가 있다. 소수를 입력받은 뒤, 분수로 www.acmicpc.net 문제 해결 순환소수를 분수로 바꾸는 방법을 알고 있다면 구현은 어렵지 않다. 하지만 순환부분만 존재를 할 때 순환하지 않는 부분(non_repeat)는 ""이 되는데 int(non_repeat)를 사용하면 ValueError가 뜨는 것을 인지하고 작성해야한다. CODE from math import gcd def convert_to_fraction(decimal):.. 2024. 3. 28.
[python] 백준 2304 창고 다각형 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 문제 해결 새로운 유형X 오목하게 들어간 부분이 없다는 것에서 최고 높이의 기둥 좌표를 알아야한다. 가장 왼쪽에서 최고 높이 좌표까지, 가장 오른쪽에서 최고 높이 좌표까지 이웃한 기둥 사이의 영역의 넓이를 계산해준다. 높이가 올라가면 앞으로 넓이가 더 커질 것이므로 타겟 높이를 설정해서 높이가 올라가면 바꿔주고 아니면 유지시킨다. CODE import sys input = sys... 2024. 3. 14.
[python] 백준 1315 RPG https://www.acmicpc.net/problem/1315 1315번: RPG 준규는 새 RPG 게임을 시작했다. 이 게임에서 캐릭터는 2가지 스탯을 가지고 있다. 하나는 힘(STR)이고, 다른 하나는 지력(INT)이다. 캐릭터를 생성했을 때, 두 스탯은 모두 1이다. 게임에는 총 N개의 www.acmicpc.net 문제 해결 수가 크다는 것에서 우선 다이나믹 프로그래밍(DP)를 생각해 볼 수 있다. (BFS,DFS는 비현실적) 주어진 퀘스트를 수행할 수 있고 수행하였을 때 추가 능력치를 얻는데 이를 어디에 얼만큼 쓸 것인지 그리디 방식으로 알 수 없다. 그렇다고 브루트 포스 방식도 조금 부담스럽다. 그래서 3가지 리스트를 만들어 문제를 해결하는 방법을 생각할 수 있다. DP[i][j]: STR=.. 2024. 3. 11.
[python] 백준 14426 접두사 찾기 https://www.acmicpc.net/problem/14426 14426번: 접두사 찾기 문자열 S의 접두사란 S의 가장 앞에서부터 부분 문자열을 의미한다. 예를 들어, S = "codeplus"의 접두사는 "code", "co", "codepl", "codeplus"가 있고, "plus", "s", "cude", "crud"는 접두사가 아니다. 총 N개의 문자 www.acmicpc.net 문제 해결 하나씩 비교를 하면 시간복잡도가 매우 크다. 따라서 정렬을 한 후에 사전식 배열 비교를 한다. S에 포함되어있는 문자열과 검사해야하는 문자열을 비교해서 포함하면 정답+1과 다음 검사해야하는 문자열을 비교를 한다. 만약 포함여부에 해당하지 않고 S에 포함되어있는 문자열의 사전식 배열이 더 뒤이면 검사해야.. 2024. 3. 10.
728x90