본문 바로가기

알고리즘

 (14)
[Python] BOJ 백준 21943 연산 최대로 문제 N개의 양의 정수 X{i}와 곱하기 연산자, 더하기 연산자가 총 N−1개가 존재하고 괄호는 무수히 많이 사용해도 된다. 이 연산에는 곱하기 연산자와 더하기 연산자의 우선순위가 동일하다. 정수와 연산자는 아래와 같이 배치해야한다. 정수의 순서는 바꿔도 상관없다. 예를 들어 정수 1, 2, 3이 있고 더하기 연산자와 곱하기 연산자가 각각 하나 있다고 가정하면 아래와 같이 만들 수 있다. 예를 들어, 수 1,2,4,5,7,8와 더하기 연산자가 4개 곱하기 연산자가 1개 있다고 하자. 괄호를 이용하여 최대값을 구하는 방법 중 일부이다. (((1+2)+4)+7)×(5+8) ((1+2)+(4+7))×(5+8) (1+(2+4)+7)×(5+8) (1+2+4+7)×(5+8) 연산을 잘 이용하여 값을 최대로 만들어 ..
[Python] BOJ 백준 21942 부품 대여장 문제 송훈이는 로봇 동아리 회원이다. 로봇 동아리에서 필요한 부품이 있을 경우 자유롭게 빌려서 쓰고 다시 돌려놓으면 된다. 하지만 부품 정리를 하다가 부품 관리가 너무 힘들어져 새로운 시스템을 도입하려고 한다. 부품을 빌려갈 경우 부품 대여장에 정보를 반드시 작성해야한다. 또한 빌려간 부품을 반납 할 경우에도 부품 대여장에 정보를 작성해야한다. 또한 대여기간을 정하고 대여기간을 넘길 경우 1분당 벌금을 부여하도록 하는 시스템이다. 만약 대여기간이 5분, 1분당 벌금이 5원이라 했을 때 대여한 시각이 2021년 1월 1일 1시 5분이라면 2021년 1월 1일 1시 10분까지 반납해야한다. 2021년 1월 1일 1시 14분에 반납을 했다면 4분 늦었기 때문에 벌금을 20원을 내야한다. 부품 대여장에 쓰는 형..
[Python] BOJ 백준 21941 문자열제거 문제 지우고 싶은 문자열 S와 지울 수 있는 문자열 A{1}, A{2}, ..., A{M}이 주어진다. 문자열 A{i}들은 각자 X{i}라는 점수를 가진다. 이 때, 문자열 S를 삭제 연산을 이용하여 모두 제거하려고 한다. 삭제 연산은 두 가지 방법이 존재하며, 원하는 만큼 여러 번에 걸쳐서 수행할 수 있다. 문자열 S의 부분 문자열 중에 문자열 A{i} 가 존재한다면 해당하는 부분을 지우고 X{i} 만큼의 점수를 얻는다(여러 부분 존재해도 한 번만 지운다). 문자열 S에서 문자 하나를 지우고 점수를 1점을 얻을 수 있다. 예를 들어, 문자열 S가 "abcxyzxabc"이 있고 "abc" 문자열을 지울 경우 10점, "xyz" 문자열을 지울 경우 5점을 얻는다고 하자. 문자열을 모두 제거하여 최대 점수를..
[Python] BOJ 백준 21940 가운데에서 만나기 문제 준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다. 도시를 연결하는 도로는 일방 통행만 있어서 도시 A{i}에서 도시 B{i}로 가는 시간과 도시 B{i}에서 도시 A{i}로 가는 시간이 다를 수 있다. 준형이와 친구들은 아래 조건을 만족하는 도시 X를 선택하여 거기서 만나려고 한다. 왕복시간은 자신이 살고 있는 도시에서 도시 X로 이동하는 시간과 도시 X에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다. 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다. 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다. 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다. 도시가 많다보니 계산하기 힘들..
[Python] BOJ 백준 21939 문제 추천 시스템 Version 1 문제 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령어는 총 3가지가 있다. 아래 표는 각 명령어에 대한 설명이다. recommend x x가 1인 경우 추천 문제 리스트에서 가장 어려운 문제의 번호를 출력한다. 만약 가장 어려운 문제가 여러 개라면 문제 번호가 큰 것으로 출력한다. x가 -1인 경우 추천 문제 리스트에서 가장 쉬운 문제의 번호를 출력한다. 만약 가장 쉬운 문제가 여러 개라면 문제 번호가 작은 것으로 출력한다. add P L 추천 문제 리스트에 난이도가 L인 문제 번호 P를 추가한다. (추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진..
[Python] BOJ 백준 21938 영상처리 문제 간단하지만 귀찮은 영상처리 과제가 주어졌다. 과제의 명세는 다음과 같다. 세로 길이가 N\이고 가로 길이가 M인 화면은 총 N × M개의 픽셀로 구성되어 있고 (i, j)에 있는 픽셀은 R{i,j} (Red), G{i,j} (Green), B{i,j} (Blue) 3가지 색상의 의미를 담고 있다. 각 색상은 0이상 255이하인 값으로 표현 가능하다. 모든 픽셀에서 세 가지 색상을 평균내어 경계값 T보다 크거나 같으면 픽셀의 값을 255로, 작으면 0으로 바꿔서 새로운 화면으로 저장한다. 새로 만들어진 화면에서 값이 255인 픽셀은 물체로 인식한다. 값이 255인 픽셀들이 상하좌우로 인접해있다면 이 픽셀들은 같은 물체로 인식된다. 화면에서 물체가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 풀이 ..
[Python] BOJ 백준 21937 작업 문제 민상이는 자신이 해야할 작업 N개를 아래와 같이 작업 순서도로 그려보았다. 위 그림에서 5번 작업을 하기 위해 제일 먼저 2번 작업을 끝내야 하고 그 다음으로 4번 작업을 끝내야 5번 작업을 할 수 있다. 3번 작업은 먼저 해야하는 작업이 없으므로 3번 작업을 바로 시작 할 수 있다. 작업 순서를 정할때 위배되는 작업 순서는 없다. 예를 들어, A 작업을 하려면 B 작업을 먼저 해야하고, B 작업을 해야하기 전에 A 작업을 해야하는 상황은 없다. 민상이는 오늘 반드시 끝낼 작업 X가 있다. 민상이가 작업 X 을 끝내기 위해서 먼저 해야하는 작업의 개수를 구해주자! 풀이 단순히 재귀함수 구현으로 풀 수 있는 문제였다. 깊이 탐색을 이용해서 각 작업의 선행 작업들을 처리하게 하고, 스택에서 빠져 나오면..
[Python] BOJ 백준 21924 도시건설 문제 채완이는 신도시에 건물 사이를 잇는 양방향 도로를 만들려는 공사 계획을 세웠다. 공사 계획을 검토하면서 비용이 생각보다 많이 드는 것을 확인했다. 채완이는 공사하는 데 드는 비용을 아끼려고 한다. 모든 건물이 도로를 통해 연결되도록 최소한의 도로를 만들려고 한다. 채완이는 도로가 너무 많아 절약되는 금액을 계산하는 데 어려움을 겪고 있다. 채완이를 대신해 얼마나 절약이 되는지 계산해주자. 예산을 얼마나 절약 할 수 있는지 출력한다. 만약 모든 건물이 연결되어 있지 않는다면 -1을 출력한다. 풀이 핵심 아이디어는 n개의 도시를 위해 n-1개의 간선을 설치한다는 것 이다. MST 유형의 문제라고 판단하고 Prim 알고리즘을 이용해서 풀었다. 초기에 다른 문제를 풀 때 처럼 코드를 짰는데, 시간 초과도..

티스토리툴바