1. 문제설명마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다. -사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다. -한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다. -광물은 주어진 순서대로만 캘 수 ..
C#
1. 문제설명위와 같이 명함들이 있고 명함의 가로와 세로의 길이가 주어집니다.모든 명함들을 수납하기 위한 지갑을 만드려고 할 때, 지갑의 가로와 세로의 길이의 최솟값을 곱하여 리턴하십시오.2. 제한사항● sizes의 길이는 1 이상 10,000 이하입니다. ○ sizes의 원소는 [w, h] 형식입니다. ○ w는 명함의 가로 길이를 나타냅니다. ○ h는 명함의 세로 길이를 나타냅니다. ○ w와 h는 1 이상 1,000 이하인 자연수입니다.3. 입출력 예시sizesreturn[[60, 50], [30, 70], [60, 30], [80, 40]]4000[[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]]120[[14, 4], [19, 6], [6, 1..
[ 서론 ] 이전에 못풀었던 문제를 다시 풀어보았습니다. 1. 문제설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다.신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다.한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다.k번 이상 신고된 유저는 게시판 이용이 정지되며, 해당 유저를 신고한 모든 유저에게 정지 사실을 메일로 발송합니다.유저가 신고한 모든 내용을 취합하여 마지막에 한꺼번에 게시판 이용 정지를 시키면서 정지 메일을 발송합니다. 다음은 전체 유저 목록이 ["muzi", "fro..
1. 문제설명 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요. 2. 제한사항 ● arr은 길이 1이상, 15이하인 배열입니다. ● arr의 원소는 100 이하인 자연수입니다. 3. 입출력 예시 arr return [2,6,8,14] 168 [1,2,3] 6 4. 나의 풀이 유클리드 호제법 사용. public int solution(int[] arr)..
1. 문제설명 N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단, 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다. 예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다. 2. 제한사항 ● sticker..
DFS? BFS? DFS와 BFS는 그래프를 탐색하는 방법의 일종이다. 그래프란 정점들과 그 정점들을 연결하는 간선들로 이루어진 자료구조이다. DFS는 깊이우선탐색으로, 그래프를 최대한 깊이 탐색한 후 옆으로 이동하여 똑같이 탐색하는 방법이다. BFS는 너비우선탐색으로, 그래프를 옆에서 옆으로 탐색한 후 점점 밑으로 내려가며 탐색하는 방법이다. DFS 예시 https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=csharp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위 문제는 ..
그리디 알고리즘이란? 그리디 알고리즘이란 우리말로 탐욕법, 탐욕 알고리즘, 욕심쟁이 알고리즘 등 여러가지 말로 불립니다. 이는 눈 앞에 있는 것이 더 좋아보이면 그것을 추구하는 알고리즘입니다. 대표적인 예시를 들어보겠습니다. : 상품에 대한 가격이 매개변수로 주어집니다. 그리고 서로 다른 금액의 동전이 들어있는 1차원 배열이 주어집니다. 상품을 주어진 배열의 동전으로 계산하려고 할 때 지불해야하는 동전의 개수의 최솟값을 리턴해야 합니다. void Start() { int[] coins = { 10, 500, 50, 100 }; Debug.Log(Greedy_Price(1990, coins)); } public int Greedy_Price(int price, int[] coins) { int answer..
1. 문제설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함..
1. 문제설명 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 1. 한 번에 하나의 원판만 옮길 수 있습니다. 2. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다. 1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을..
동적 프로그래밍이란? 큰 문제를 작은 단위로 쪼개서 반복 분할하여 푸는 접근 방식입니다. 네 맞습니다. DFS와 같은 개념입니다. 기본적으로 DFS문제는 재귀함수를 사용해서 풀어가는 방식이 일반적입니다. 그럼 동적프로그래밍은 DFS와 같은 것인가?? 결론부터 말씀드리면, 답은 No입니다. 동적 프로그래밍은 작은 하위 문제의 해결 방법을 계산하여 저장하고, 이를 이용하여 큰 문제의 해결 방법을 도출합니다. DFS와 동적프로그래밍의 차이점!! 여기 숫자가 들어있는 정삼각형 구조가 있습니다. 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 리턴하는 문제입니다. 문제를 처음 접하게되면 기본적으로 DFS로 문제를 풀어야겠다는 생각이 들 것입니다. DFS로 접근하게 되면, 7+3+8+2+..
