즐겁게 개발

문제k번 happiness 배열을 훑으면서 남아 있는 가장 큰 값을 더해서 반환한다. 단, 한 번 가장 큰 값을 뽑으면 그 다음엔 배열에 담긴 모든 값이 1씩 줄어들고 그 상태에서 가장 큰 값을 또 꺼내야 한다.나의 접근법happiness를 오름차순 정렬하고, k개만큼 앞에서 가장 큰 값에서 인덱스를 뺀 값을 더해간다. 단, 가장 큰 값에서 인덱스를 뺀 값은 최소 0이다.class Solution { public long maximumHappinessSum(int[] happiness, int k) { Arrays.sort(happiness); int n = happiness.length; for (int i = 0; i 코멘트시간복잡도는 코드 라인따라 계산해보..

www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 이 문제를 처음 보면 어떻게 풀어야 할 지 감이 안 잡힌다. 그러나 잘 생각해보면 BFS를 이용해서 풀 수 있는 문제라는걸 알 수 있다. 나이트가 이동할 수 있는 방향은 왼쪽과 같다. 문제는 이렇게 이동할 수 있는 나이트를 시작위치에서 종료위치로 옮기는 최소횟수를 구하는 것이다. 차례대로 생각을 해보자면, 나이트는 시작위치에서도 저 8개 위치로만 이동할 수 있고, 8개 위치 중 하나를 골라 이동한 뒤에 또 8개 ..

이해하기 왼쪽과 같은 그래프가 있다고 하자. 깊이우선은 말그대로 옆에 노드가 있더라도 아래로 먼저 움직이고(깊게), 너비우선은 옆에 노드가 있으면 무조건 옆에 있는 노드로 움직인다고(넓게) 생각하면 된다. 옆 그래프를 DFS하면 1 - 2 - 4 - 5 - 3 - 6 이 되고, BFS하면 1 - 2 - 3 - 4 - 5 - 6 이 된다. 그렇다면 이 그래프를 코드로 나타내려면 어떻게 하면 될까? 왼쪽처럼 배열로 나타낼 수 있다. 각 줄은 노드 한개를 의미한다. 1번 노드는 2, 3번과 연결되어 있기 때문에 1번째 줄에는 2, 3만 1이고, 2번 노드는 1, 4, 5번과 연결되어 있기 때문에 2번째 줄에는 1, 4, 5만 1이다.(양방향으로 가능한 노드일 경우 이렇다.) 이 배열을 DFS, BFS하면 아래..

ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98 이항 계수 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 조합론에서, 이항 계수(二項係數, 영어: binomial coefficient)는 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다 ko.wikipedia.org 매일 매일 알고리즘 문제를 하나씩 풀고 있는데, 오늘 문제에서는 이항계수라는 개념이 나와서 정리해보려고 한다. 본 내용은 위의 링크를 토대로 학습한 내용을 정리한 것이다. 이해하기 우선 이항계수가 어떤건지 ..

유클리드 호제법은 소인수분해를 하지 않고 2개의 자연수의 최대공약수를 구하는 알고리즘으로 큰 수들의 최대공약수를 구할 때 사용할 수 있다. 이해하기 두 수 a, b가 있다고 하자. a와 b는 공약수 j의 배수이므로 아래와 같다. A = 약수 j * a B = 약수 j * b A를 B로 나누면 아래와 같다. A = (B * x) + y y = A - (B * x) y = (j * a) - (j * b * x) y = j * (a - b * x) 즉, A를 B로 나눈 나머지 y는 A와 B의 공약수 j를 약수로 한다. B = j * b y = j * (a - b * x) 위처럼 b와 y의 공약수는 j이다. 즉, b와 y의 최대공약수(i)는 j와 같거나 j보다 크다. (1) B = 최대공약수 i * c y = ..

정렬 알고리즘은 내가 생각하기에 제일 간단한 알고리즘인데... 종류가 많아서 머릿 속에 빡하고 안 들어오는 느낌이어서 정리해본다. 버블정렬(Bouble Sort) 이해하기 4 3 2 5 1 위와 같은 수열이 있다고 하자. 버블 정렬을 이해하는 데 있어 중요한 것은 버블 정렬을 할 때 수열 중 어떤 하나의 수는 정렬을 따로 할 필요가 없다는 것이다. 왜냐하면 다른 수들이 모두 정렬된 상태라면 자연히 그 숫자도 자리를 찾은 것이기 때문이다. 4 3 2 5(여기까지만) 1 처음 4에서 시작해보자. 우리는 4라는 수를 꺼내서 5가 있는 네번째 자리까지만 가면 된다. 왜냐하면 앞수와 뒷수를 비교하는 과정에서 마지막으로 5와 1을 비교하게 될 것이고, 1은 수열의 마지막이라 비교할 뒷수가 없기 때문이다. 4는 3과..

이름만 봐도 이해하기 힘든 LIS(Longest Increasing Subsequence)는 쉽게 말하자면 나열된 수들 중 오름차순으로 정렬된 가장 긴 부분수열이다. 이해하기 3 1 4 5 2 7 위와 같은 수열이 있다고 하자. 이 때 부분수열은 길이가 1인 부분수열도 있을것이고, 2인 부분수열도 있을것이고, 6인 부분수열도 있을것이다. 제일 앞에 있는 수를 선택할 경우를 생각해보자. 3(★) 1 4 5 2 7 3까지의 수열을 보면 3 밖에 존재하지 않으므로 길이는 1이다. (이 길이는 나중에 써먹어야 하므로 저장해야 한다.) 3 1(★) 4 5 2 7 그 다음 1까지의 수열을 보자. 1까지의 수열([3, 1])에서 부분수열의 최장길이를 구하려면 어떻게 해야 할까? 3과 1을 비교해서 3이 1보다 크므로..