개발 블로그 개발 블로그

문제 초기 대출금(price)과 매월 상환금(monthlyPayment), 상환기간(loanTerm)이 주어졌을 때 이자율을 계산하라. 단 상환기간은 월 단위로 주어지며 매월 이율은 연이율을 12로 나눈 것과 같다. 이자율은 1e-9 이하의 오차범위를 가져야 한다. 입출력 예시 입력 1)price = 6800monthlyPayment = 100loanTerm = 68 출력 1)0 입력 2)price = 2000monthlyPayment = 510loanTerm = 4 출력 2)9.562054624620941 풀이 이자율을 미지수로 두고 매번 남은 잔액에 대해 생각해 보면 잔액 *= 이자율/1200 + 1잔액 -= 월 상환금 인 것을 알 수있다. 이자율에 구체적인 값을 넣고 오차범위 안에 드는 값을 구하면..

문제 n명의 회사원이 둥근 테이블에 앉아 회의를 하려고 한다. 회의를 시작하기 전에 그들은 먼저 악수를 해야한다. 회사원들은 각각 다른 사람과 악수를 해야 하며 모든 악수는 동시에 진행되어야 하지만 서로의 팔이 교차되어서는 안 된다. 정수가 주어졌을 때 그만큼의 직장인이 하는 악수가 성립하는 조합의 수를 리턴하는 함수를 작성하라. 입출력 예시 입력 1)int n = 2 출력 1)1 입력 2)int n = 8 출력 2)14 풀이 이 문제를 풀기 위해서는 카달랑 수의 개념을 알아야 한다. 조합론에서, 카탈란 수(Catalan數, 영어: Catalan number)는 이진 트리의 수 따위를 셀 때 등장하는 수열이다. 위 문제를 통해 수열의 점화식을 알아보자. 모든 사람이 악수를 해야 하기 때문에 주어지는 정수..

문제 대학교 알고리즘 동아리 회장인 당신은 회원들과 함께 MT를 왔습니다. 하지만 초보 총무의 실수로 예산이 부족해 긴급하게 학생들에게 추가 모금을 할 수 밖에 없는 상황에 처했습니다. 당신은 회원들에게 부족한 예산을 기부받아 내려고 하고 있습니다. 하지만 학생들은 모두 눈치만 보고 있는 상황입니다.회원들은 모닥불을 가운데 두고 빙 둘러 앉아 있습니다. 눈치를 많이 보는 학생들은 양 옆에 앉은 학생들 중 한 명이라도 기부를 하면 자신은 기부를 하지 않는다고 합니다. 학생들의 순서가 배열로 주어지고 각 배열에 학생들이 기부하려고 하는 금액이 저장되어 있습니다. 이 때 배열의 첫번째와 마지막에 위치한 학생들은 서로 인접한 것으로 생각합니다. 어떻게 하면 기부금을 최대로 모을 수 있을까요? 입출력 예시 입력 ..

문제 유명한 동적계획법 문제중 하나인 냅색(knapsack) 문제를 풀어 보자. 몇 개의 물건이 있고 각 물건에는 무게와 가치라는 2개의 매개변수가 주어진다. 일정한 무게까지 물건을 배낭에 넣을 수 있다고 할 때 가치의 합계가 최대가 되려면 물건을 배낭에 어떻게 넣어야 할까? 풀이 동적계획법을 적용하는 굉장히 유명한 문제로 동적계획법을 이해하는 정석과 같은 문제이다. 핵심은 전체탐색을 하되 이전에 했던 계산을 다시 재활용 하도록 만든다는 점이다. 이를 위해 이차원 배열을 선언하고 배열은 i번째 선택에서 총무게가 j일 때 가지는 최대 가치로 설정한다. 같은 횟수의 선택일 때 같은 무게에서 이미 구한 값 보다 더 낮은 가치라면 굳이 탐색할 필요가 없으니 수행시간이 상당히 줄어들게 된다. 코드은 다음과 같다...

문제 당신은 미로 제작을 의뢰 받았다. 당신이 제작할 미로는 조금 특이한데 바로 미로에 도전하는 사람의 점프력이 상당히 좋기 때문이다. 이 도전자는 초기에 주어진 int[] moveRow, int[] moveCol에 따라 점프할 수 있는데 미로의 밖으로 나가거나 미로의 막힌 부분 위에 올라갈 수는 없다.이 도전자는 항상 최단거리로 움직이는데 당신은 미로의 출구를 가장 오랜시간이 걸리는 곳에 정해야 한다. String 배열로 주어지는 maze에는 "."과 "X"로 구분된 미로 지도가 주어진다. 가장 먼 거리를 움직여야 찾을 수 있는 미로의 출구까지 간 거리를 리턴하는 함수를 만들어라 입출력예시 입력예시 1) String[] maze = {"X.X","...","XXX","X.X"}; int startRow..

문제 주어진 정수 배열 number에는 50개 미만의 1보다 크고 1000보다 작은 정수가 주어져 있다. 이 중 단 하나의 숫자에 +1 하여 전체 숫자의 곱을 가장 크게 만든 뒤 그 곱을 리턴하라. 입력예시 numbers = {1, 2, 3}return : 12 numbers = {1, 3, 2, 1, 1, 3}return : 36 풀이 가장 쉽게 떠올릴 수 있는 풀이는 먼저 배열의 모든 원소의 곱을 구한 뒤, 전체 배열을 순회하며 그 배열의 숫자를 나눈뒤 다시 1을 더한 숫자로 곱해 보며 최대값을 찾는 것이다. 시간 복잡도는 O(N)으로 매우 짧지만 이 문제는 약간의 수학적 센스를 발휘하면 조금 더 쉬워진다. +1 을 하여 전체의 곱을 가장 크게 만드는 숫자는 배열에서 가장 작은 숫자이다. 어떤 숫자 ..

문제 사람들은 각각 두가지의 취미를 가지고 있다고 한다. 취미는 String 배열인 first와 second에 나누어져 들어온다. 예를 들어 i번째 사람의 첫번째 취미는 first[i] 에 문자열로 저장되어 있고, 두번째 취미는 second[i] 에 저장되어 있다. 이때 가장 많은 사람들이 즐기는 취미 생활은 총 몇 명이 즐기고 있는지 리턴하라. 입 출력 예제 입력String[] first = {'a','b','a','a'};String[] second = {'b','a','b','b'}; 출력4 풀이 단순히 생각해서 이중반복문을 사용해서 전체 배열을 돌면서 같은 이름의 숫자를 세면 된다. 이중반복문을 사용하는 것이 코드를 지저분하게 보이기 때문에 Map객체를 이용해 조금 더 간결한 코드를 얻을 수 있다..