본문 바로가기
728x90

전체 글408

[python] 백준 11562 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 문제 해결 graph[u][v] : u에서 v까지 가는데 필요한 양방향화 필요한 길 개수 처음에 INF로 정의한다음 연결되어있다고 입력값이 주어지만 graph[u][v] = 0 만약 양방향이 아니고 u→v는 연결이 되어있는데 v→u는 연결이 안되어있으면 graph[v][u] = 1로 정의 플로이드-위셜을 이용하여 필요한 양방향화 길의 개수를 구할 수 있다. 플로이드-위셜로 최소거리가 아닌 필요한.. 2024. 4. 3.
[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.
728x90