목록Algorithm (28)
Inor
- 문제 : https://www.codeground.org/practice/practiceProblemView - 풀이 주어진 요구사항을 간단한 연산으로 구현하면 되는 쉬운 문제였습니다. 커피 가격을 배열에 저장하고 배열의 인덱스로 사원들이 선호하는 커피 번호를 사용했습니다. 사원들을 순회하며 선호하는 커피 가격만큼 법인카드 한도에서 빼기 연산을 했고 한도가 넘어가면 N, 한도 내에서 구입이 가능하면 Y를 출력하도록 했습니다. - 코드 package practice; import java.util.Scanner; public class Starbucks { Scanner sc; int numOfPeople, numOfCoffee, moneyLimit; int[] preferredCoffe, coffee..
- 문제 : https://www.acmicpc.net/problem/9324 비밀 코드가 정확한 코드인지 잘못된 코드인지 해석하는 문제입니다. 어떤 알파벳이 이전에 3번 출현 했으면 해당 알파벳을 한번 더 써줘서 비밀 코드를 만듭니다. 예를 들어서, ABBSABB라는 코드가 있다면 B가 3번 출현했고 마지막에 B를 추가로 적어서 비밀 코드를 만들었습니다. 그리고 이 코드는 참입니다. 만약, ABBSAB 코드가 주어졌다면 이는 거짓입니다. B가 3번 나왔지만 마지막에 B를 써주지 않았습니다. 또한, ABBSABA 코드가 주어졌다면 이는 거짓 코드입니다. B가 3번 출현했지만 마지막 B 다음에 A가 출현했습니다. - 풀이 이전까지 알파벳이 얼마나 출현했는지 보여주는 배열(numOfAfter)을 선언해서 암..
- 문제 : https://www.acmicpc.net/problem/2851 10개의 버섯이 차례대로 주어지고 슈퍼마리오가 버섯을 순서대로 먹으며 점수를 높이는 상황을 구현하는 문제입니다. 점수가 최대한 100에 가까울 경우에 버섯 먹는 과정을 그만두고 그 점수를 출력합니다. 만약에 98과 102가 나오는 상황에서는 102를 출력하면 됩니다. - 해결 먼저 버섯을 순서대로 먹도록 구현했고 버섯을 먹으며 다음 단계에 먹을 버섯의 값과 비교해서 어떤 값이 100에 가장 가까운지 확인했습니다. 그리고 만약 102와 98이라는 값이 나오면 100과의 차이가 2 일 경우에 102에 우선순위를 두도록 했습니다. now와 after변수를 이용해서 현재 점수와 다음 버섯을 먹었을때의 점수를 비교했습니다. - 소스 코..
- 문제 : https://www.acmicpc.net/problem/10250 문제가 길지만 간단한 문제입니다. 사람의 번호를 층수로 나누었고 엘리베이터에서 얼만큼 떨어져있는지를 계산했습니다. 그리고 나머지 연산으로 사람 번호를 층으로 계산했습니다. 몇 층에 있는지 계산하기 위함이었고 0이 나오면 가장 위의 층에 있는 경우이므로 따로 분기해서 계산 했습니다. - 소스 코드 import java.util.Scanner; public class ACMHotel { int tNum; int[][] testCases; int[] results; public void solve() { Scanner sc = new Scanner(System.in); String tString; tNum = sc.nextInt(..
- 문제 : https://www.acmicpc.net/problem/11052 남은 붕어빵을 세트로 판매하는 문제입니다. 세트를 어떻게 나누어야지 이윤을 가장 많이 남길 수 있는지 풀어야됩니다. 이전 값이 다음 값에 영향을 줄 수 있기(memoization) 때문에 DP로 풀었습니다. - 풀이 먼저 하나의 경우를 만들고 각각을 분류하며 풀었습니다. 경우를 나열해본 결과 D[N]을 구하기 위해 D[N]부터 D[1]까지 적절하게 더해주며 결과를 도출했습니다. D[N]을 구하기 위해 먼저 N개의 붕어빵 세트를 만들었을때 값을 D[N]에 넣어줬습니다. 그리고 나머지 값들과 비교해줬습니다. D[N] < D[N-j] + D[N-(N-j)]로 비교하면 N보다 작은 값 중에 가장 큰 값과 가장 작은 값을 차례로 비교..
- 퀵 정렬 퀵 정렬은 이름대로 매우 빠른 정렬 알고리즘에 속합니다. 퀵 정렬은 최악인 경우 O(n^2), 보통인 경우 O(nLogn)의 시간 복잡도를 갖고있는 정렬 알고리즘입니다. 최악인 경우는 정렬이 완료된 상태에서 정렬을 시도하면 발생합니다. 최악인 경우가 발생하는 경우를 살펴보기에 앞서, 퀵 정렬이 어떤 방식으로 동작하는지 알아보겠습니다. 퀵 정렬은 분할/정복 방식으로 인자들을 정렬합니다. 분할하는 방식은 Pivot 값을 기준으로 기준보다 작은 값과 큰 값을 분류하고 정렬합니다. Pivot은 정렬 인자들 중에 프로그래머가 임의로 선정한 값입니다. 저는 배열에서 가장 오른쪽에 있는 값을 Pivot으로 선정했습니다. 이렇게 말로 설명하기보다 배열이 단계별로 어떻게 변화하는지 직접 확인하며 학습해보겠습..