본문 바로가기

알고리즘

 (305)
[백준] 2637번 : 장난감조립 2637번: 장난감 조립 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 📄 문제개요 장난감을 조립하기위하여 장난감의 의존성을 정의되어있는 테이블이 주어진다. 장난감은 N개의 기본부품과 중간부품으로 나누어 지는데 마지막 N번째의 부품의 기본부품의 개수를 구하는 문제이다. 기본부품은 다른 부품으로 조립 할 수 없는 부품이고, 중간부품은 아래와 같이 구성 될 수 있다. 중간부품 + 기본부품 기본부품 + 기본부품 중간부품 + 중간부품 🤔 문제분석 해당문제는 만약 5번부품의 기본부품의 개수..
[백준] 19238번 : 스타트 택시 19238번: 스타트 택시 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 📄 문제개요 택시와 손님이 존재할때, 택시의기름으로 손님을 목적지까지 운송합니다. 운송할때에 기름이 바닥나면 게임이 종료되고, 기름이 바닥나지않고 손님을 목적지까지 운송을 완료하면 택시의 기름은 손님을 운송할때 쓰인 기름 비용의 2배가 됩니다. 모든 손님을 옮긴뒤에, 택시의 기름양을 출력한다. ( 만약, 모든 손님을 이동 할 수 없다면 -1을 출력한다. ) 🤔 문제분석 손님은 집합자료형 자료구조로 ..
[백준] 16235번 : 나무 재테크 16235번: 나무 재테크 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 📄 문제개요 봄 : 나무의 나이가 가장 작은 순서부터, 자신의 나이만큼 양분을 먹는다. 양분을 먹은 나무는 나이가 1 증가한다. 양분을 먹을 수 없는 나무는 즉시 죽는다. 여름 : 죽은 나무가 양분으로 변한다. 죽은 나무마다 나이를 2로 나눈값이 나무가 있던 칸에 양분으로 추가된다. 가을 : 나무가 번식한다. 번식하는 나무는 나이가 5의 배수이며, 인접한 8개의 칸에 나이가 1인 나무가 생긴다. 겨울 : 양분을 추가한다...
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 📄 문제개요 연속된 가장 긴 바이토닉 수열을 구하는 문제이다. 🤔 문제분석 다이나믹 프로그래밍 문제로, 현재 인덱스로부터 증가하는 가장 긴 값을 갱신한다. 처음부터 끝까지 순회하면서, 현재 인덱스로부터 가장 증가하는 긴 값을 dp 배열에 넣는다. 뒤집어서 한번더 증가하닌 긴 값을 dp 배열에 넣는다. 📝 의사코드 수열을 순회하면서, 증가하는 수열의 정보를 갱신한다. 수열을 반대로 뒤집어, 증가하는 수열의 정보를 갱신한다. 2개의 dp 테이블..
[백준] 17472번 : 다리만들기 2 17472번: 다리 만들기 2 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 📄 문제개요 섬과 바다가 주어지고, 주어진 조건에따라서 섬을 연결 할 수 있다고 할 때, 섬을 연결 할 수 있는 최소 길이를 구하여라, 연결하지 못한다면 -1을 출력하여라. 🤔 문제분석 탐색과 그래프 문제입니다. BFS 탐색으로 섬을 그룹핑 한다. 해당 그룹에서 또다른 그룹 까지의 거리를 구한다. 해당그룹에서 또다른그룹까지의 거리를 가장 짧은 거리순으로 연결해본다 ( 최소신장트리 ) 📝 의사코드 BFS 탐색으로 ..
[백준] 1035번 : 조각움직이기 1035번: 조각 움직이기 1035번: 조각 움직이기 최대 5개의 조각이 있는 5×5 크기의 보드가 있다. 김지민은 조각을 적절히 움직여서 모든 조각이 연결 요소를 이루게 하려고 한다. 즉 상하좌우로 인접한 조각을 모두 연결했을 때, 모든 쌍의 조 www.acmicpc.net 📄 문제개요 5x5 크기의 보드가 주어졌을때, 모든 조각을 움직여서 연결 요소를 만드려고 한다. 조각을 최소로 움직여서 연결요소를 만들 수 있는 값을 구하시오. 🤔 문제분석 문제의 범위가 5x5이니, 완전탐색으로 문제를 접근해야한다. 우선은 연결요소가 될 수 있는 모든 경우의 수를 구한다. 연결요소를 순열로 현재 peice와 거리 계산을 하여 최소값을 갱신한다. 📝 의사코드 별의 개수로 만들 수 있는 모든 조합의 경우의 수를 구한다..
[백준] 1759번 : 암호만들기 1759번: 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 📄 문제개요 암호의 후보의 단어가 주어졌을때, 암호를 만들 수 있는 모든 경우의 수를 구한다. 암호는 문자가 오름차순이어야한다. 동일한 문자는 올 수 없다. 모음의 개수는 1개이상, 자음의 개수는 2개 이상 이어야한다. 🤔 문제분석 완전탐색문제로, 가능한 모든 조합을 확인해보면서 문제를 해결 할 수 있다. 필자는 2가지의 사항으로 문제를 해결 하였다. DFS로 가능한 모든 경우의 수를 탐색해보기 Python 내장 라이브러리 Combinatio..
[백준] 1092번 : 배 1092번: 배 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 📄 문제개요 항구에 크레인이 있고, 최대 박스를 들 수 있는 크레인이 주어지고, 모든 크레인이 동시에 박스를 옮기는데 걸리는 시간은 1분이다. 박스와 크레인이 주어졌을때, 옮길 수 있는 최소 시간을 구하여라. 🤔 문제분석 크레인과 박스를 내림차순 으로 정렬한다. 박스를 순회하면서, 크레인이 박스를 제거시킨다. 박스를 제거시킬때 크레인은 자기가 옮길 수 있는 최대의 무게를 그순간 옮겨야한다. O(M^2*N)으로 문제를 해결한다. 📝..

티스토리툴바