2 3 hat headgear sunglasses eyewear turban headgear 3 mask face sunglasses face makeup face answer : 5 3 해빈이의 옷을 종류별로 입을 수 있는 최대 가짓수를 계산하는 문제이다. 알몸은 안되며, 종류별로 착용하지 않을 수도 있다. 확률과 통계 시간에 종종 풀어본 유형의 문제인데, 해빈이 옷이 1번 종류 4개, 2번 종류 2개, 3번 종류 2개가 있다고 하면, 각 종류별로 입지 않는 경우 한 개씩을 추가해서 5 * 3 * 3을 하면 옷을 입지 않는 것을 포함 가능한 모든 조합의 수이다. 여기서 옷을 입지 않는 경우를 빼주면 답이 된다. 알고리즘은 이렇게 짜면 되는데, 구현이 문제다. 사실 옷의 이름은 필요가 없다. 종류별로 몇..

4 -1 2 1 3 answer : 6 6 0 1 2 4 3 5 answer : 27 1 -1 answer : -1 배열의 각 숫자를 위치에 관계없이 두 개씩 묶을 수도 있고 묶지 않을 수 있다. 그리고 원소들의 합을 구하는데, 묶은 수끼리는 곱하고 모든 수를 더해서 그 값이 최대가 되게 하면 된다. 우선 배열을 정렬한다. 그 후 규칙에 따라서 묶을지 말지, 어떤 수와 묶을지를 정하였다. 규칙 1) 음수끼리는 묶는다. 단, 작은 수 끼리 묶는다. 규칙 2) 묶이지 못한 음수는 0과 묶을 수 있으면 묶고 아니라면 묶지 않는다. 규칙 3) 0은 음수가 아니면 묶지 않는다. 규칙 4) 1은 묶지 않는다. 규칙 5) 양수는 양수끼리 묶는다. 단, 큰 수 끼리 묶는다. 이 정도 규칙을 생각했고, 이제 이 조건들을..

int 자료형으로 표현 가능한 숫자는 210,000,000(21억) 언저리까지이다. 그 이상의 숫자는 오버플로우가 발생하므로 long long 자료형을 사용해야 한다. 내가 코딩하다가 숫자가 21억이 넘어갈지 안 갈지 어떻게 알아??라는 의문이 들 수 있다. 1. 먼저 알고리즘을 생각해본다. 사람마다 다르지만 나는 퍼수도코드로 짜고 시작한다. 2. 시간복잡도를 생각해본다. O(N*M) 이런 식으로 나온다면 N과 M의 최댓값을 기준으로 곱해서 생각하면 된다. 얼추 21억이 넘겠다 싶으면 안전하게 long long으로 짜는 편이 좋다. 3. long long으로 코드를 바꿀 때 콤팩트하게 확실하게 안 바꿔도 되는 자료형을 제외하고는 다 바꾸는 편이 좋다. 연산 중 자동 형변환이 일어날 수 있다. 시간초과도 ..

예제 1 3 1 3 2 6 answer : 16 예제 2 4 2 4 2 3 1 answer : 19 n개의 카드에 대해 어떤 두 카드의 숫자를 그 두 카드의 합으로 바꾸는 것을 m번 진행한 뒤 n개의 카드의 숫자 합이 최소가 되게 하는 문제이다. 먼저 그리디 하게 매 턴마다 가장 작은 숫자 두 개를 고르면 된다고 생각했다. 매 턴마다 그리디 하게 숫자를 고르는 것까지는 문제가 없어 보였고, 구현 부분은 우선순위 큐를 이용해 간단히 우선순위를 내림차순으로 하고, pop 두 번 후 두 숫자를 더한 값을 push 두 번 하는 식으로 구현했다. 여기까지는 쉬웠지만 주의할 점이 하나 있었다. n개의 카드가 최대 1,000개이고 15 * n번의 턴이 진행되며 각 카드의 숫자는 최대 1,000,000여서 int 자료..

힙 최대 힙은 완전 이진트리이고, 부모가 항상 자식보다 큰 자료구조이다. 완전 이진트리란, 마지막 레벨을 제외하고 모든 레벨의 노드가 다 채워져 있고 마지막 레벨은 왼쪽부터 채워지는 트리이다. 최소 힙은 반대로 부모가 항상 자식보다 작다. 힙은 완전 이진트리의 특성상 부모와 자식의 index가 명확해서 배열을 사용한다. A[i]의 부모는 A [i/2]이고 왼쪽 자식은 A [2*i] 오른쪽 자식은 A [2*i + 1]이다. 힙은 힙 특성 유지하기(heapify), 힙 만들기(buildHeap), 삽입(insert), 삭제(delete)만 알면 된다. 힙 구현 힙 특성 유지하기(heapify) 배열 A에 대해 i번째 원소를 최대힙의 루트가 되게 한다. 아래는 퍼수도 코드이다. heapify(A, i){ l ..

교재 Introduction To Algorithms 3rd Edition를 바탕으로 수업시간에 다룬 내용 위주로 정리하였다. ​ 알고리즘 기본 용어 정리 매개변수((parameter))는 문제에서 언급된 할당되지 않은 변수들이다. 문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 매개변수 : n, S ​ 실체((instance))는 매개변수에 실제로 할당된 값이다. → 문제 : 오름차순으로 n개의 정수 리스트 S를 정렬하시오. → 실체 : n = 6, S = [10, 7, 11, 5, 13] ​ 알고리즘이란 어떤 수학적으로 엄밀히 정의된 문제를 풀기 위한 유한한 절차와 방법이다. 알고리즘의 실험적 분석 주어진 알고리즘을 소스코드로 구현한 다음, 실제 환경에서 동작시켜 실제 실행 시간을 측정..