자료구조,알고리즘 (51) 썸네일형 리스트형 [Python, Java] 프로그래머스 - 디펜스게임 문제준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.준호는 처음에 병사 n명을 가지고 있습니다. 매 라운드마다 enemy[i]마리의 적이 등장합니다. 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다. 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다. 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다. 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다. 무적권은 최대 k번 사용할.. [Python] 프로그래머스 - 다리를 지나는 트럭 문제트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 we.. [Python, Java] 프로그래머스 - 짝지어 제거하기 문제짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.예를 들어, 문자열 S = baabaa 라면b aa baa → bb aa → aa →의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.제한사항문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다.두번 반복되는 문자.. [Python] 프로그래머스 - 전력망 둘로 나누기 문제n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다.송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요.제한사항n은 2 이상 100 이하인 자연수입니다.wires는 길이가 n-1인 정수형 2차원 배열입니다.wires의 각 원소는 [v1, v2] 2개의 자연수로 이루어져 있으며, 이는 전력망의 v1번 송전탑과.. [Python, Java] 프로그래머스 - 피보나치수 문제피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.예를들어F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5와 같이 이어집니다.2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.제한 사항n은 2 이상 100,000 이하인 자연수입니다. 피보나치 방법의 기초인 재귀 호출을 통해 시도해보았습니다.def fibonacci(n): if n == 1 or n =.. [Python] 프로그래머스 - 호텔 대실 문제최소한의 객실 수를 구해 반환하는 문제입니다. 예약 시간이 주어지고 퇴실 시간을 기준으로 10분간의 청소시간이 필요합니다. 이때 최소로 필요한 객실의 수를 구하면 됩니다. 백준에서도 비슷하게 회의시간을 잡는 문제가 있었던 것으로 기억합니다.풀이1. 예약 시간 및 종료 시간을 정렬합니다.2. 최소 힙을 사용해 현재 사용중인 객실의 종료시간을 업데이트 해 둡니다.3. 각 예약이 끝난 후 10분의 시간을 추가하여 다음 예약과 겹치는 지 판단합니다. 4. 만약 가장 빠른 예약 시간이 청소 완료 시간보다 늦다면, 해당 객실을 재사용 할 수 있도록하고 종료시간을 힙에서 제거합니다.5. 새로운 종료시간을 힙에 추가합니다.Pythonimport heapqdef time_to_minutes(time): hour.. [Python] 프로그래머스 2진법 만들기 문제124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.124 나라에는 자연수만 존재합니다.124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다.자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.제한사항n은 50,000,000이하의 자연수 입니다.문제에서 제공된 표를 보면 이해하기 쉽습니다. 10진법을 2진법으로 바꾸는 것 처럼 10진법을 124진법으로 바꾸는 것입니다. 여러가지의 수로 테스트 해보면 다음과 같은 규칙을 찾을 수 있습니다. 숫자 n을 3으로 나누었을 때 나머지가 1이면 1이고, 2로 나누었을 때 나머지가 2면 2, 나머지가 0이면 4.. [Python] 프로그래머스 - 삼각 달팽이 문제정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.트리를 활용해서 값을 채우고, 트리를 배열로 변환하여 반환하는 방식으로 해결하였습니다. 구조가 사각형으로 바뀌어서 그렇지 결국 트리의 형태를 보여주고 있기 때문에 트리로 해결하는 것이 가장 적합해보였습니다.풀이1. 높이가 N인 트리를 생성합니다 (build_tredd) -> 문제에서 주어진 N도 높이를 의미하고 있기 때문에 필요한 노드의 수 만큼 생성됩니다.2. 맨 위의 노드부터 시작해서 노드를 연결해나갑니다.아래 -> 오른쪽 -> 대각선.. 이전 1 2 3 4 ··· 7 다음
