알고리즘, 문제해결103 [백준 17497번] 계산기 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/17497 17497번: 계산기 첫 번째 줄에 버튼을 누른 횟수 K (0 ≤ K ≤ 99) 를 출력합니다. 누른 횟수를 최소화 하지 않아도 됩니다. 단, 누른 횟수가 99번을 넘으면 안됩니다. 만약 99번 안에 N을 만드는 방법이 존재하지 않는 www.acmicpc.net 백준에서는 이 문제를 greedy method라고 분류해는데, greedy method가 맞는지 개인적으로는 잘 모르겠습니다. 처음에는 greedy method 방법으로 접근했습니다. 현재 값 x에서 곱하기, 빼기, 곱하기, 나누기 연산을 해 보고, 주어진 값 N까지의 절댓값이 가장 작은 방법을 고르는 식으로 했는데, 코드도 100줄 가량으로 길어질 뿐더러 N =.. 2020. 11. 5. [백준 1202번] 보석 도둑 문제 링크: www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 대표적인 Greedy Method를 이용하는 문제입니다. 제가 접근한 방법은, 가지고 있는 보석을 값이 비싼 순서대로 정렬한다. 비싼 보석부터 차례로 가방에 넣습니다. 더 담을 수 있는 가방이 없으면, 프로그램을 종료하고, 가방에 넣은 보석의 총 값어치를 출력합니다. 이를 위하여 보석의 정보를 기록하기 위하여 형식의 pair라는 타입을 만.. 2020. 10. 12. 비트마스크 (Bitmask) 연산 "프로그래밍 대회에서 배우는 알고리즘 문제해결전략", 16장. 비트마스크 를 읽고 공부한 것을 기반으로 작성하였습니다. 우리가 사용하는 컴퓨터의 자료는 모두 2진수를 기반으로 이루어져 있습니다. 컴퓨터가 2진수를 이용한다 함은 보통은 컴퓨터를 사용하는 사람, 즉 우리에게는 큰 상관이 없지만, 프로그램 작성 시 연산 시간과 공간적 효율을 고려한다면 이진수를 직접 다루는 것이 효율적일 것입니다. 이러한 목적으로 이진수 표현을 자료구조로 쓰는 기법을 비트마스크 (bitmask) 라고 합니다. 비트마스크 기법은 아래와 같은 이점을 가진다고 합니다: 더 빠른 수행 시간. 대부분 O(1) 의 시간복잡도를 가져, 통상적인 다른 자료구조보다 훨씬 빠른 연산속도를 자랑합니다. 다만 비트마스크를 사용하는 경우 원소의 수가.. 2020. 5. 29. [백준 1463번] 1로 만들기 문제 주소는 여기로 아까 merge sort 문제 풀고 나서 가볍게 도전해 볼 문제로 고른 이번 문제... 그러지 말았어야 했어요. 입력받은 숫자를 1. 3으로 나누어 떨어진다면 3으로 나누거나 2. 2로 나누어 떨어진다면 2로 나누거나 3. 1을 뺀다. 위 세 과정 중 하나를 반복하여 결과적으로 숫자를 1로 만들고, 그러기까지 필요한 총 연산 수의 최솟값을 출력하는 문제입니다. 되게 단순한 문제인 줄 알았는데 그게 아니더라구요. 3 또는 2로 나누어 떨어질 때도, 1을 빼는 쪽이 결과적으로 더 연산이 적게 필요할 수도 있어요. 예를 들어 10은 10-5-4-2-1, 총 연산수 4번이지만 10-9-3-1, 즉 1을 빼는 쪽으로 시작하면 총 연산수가 3번입니다. 늘 그렇듯 잘 모를 때는 백준의 질문 검색을.. 2020. 5. 8. [백준 2751번] 수 정렬하기 2 문제 주소는 여기로 앞의 정렬 문제 글에 이어서 포커스를 각기 맞춘 sorting algorithm에 대한 문제를 풀어 봤어요. 백준에는 총 3개의 sorting 관련 문제가 있는데, 1번은 메모리와 시간이 평범하며 입력하는 테스트 케이스의 수가 적은, 가장 보편적인 sorting 문제. 이것은 selection sort 로 풀었습니다. 3번은 메모리가 아주 제약되지만 시간이 넉넉한 sorting 문제. 이것은 counting sort로 풀었구요. 그리고 이번에 다룬 2번은 메모리는 넉넉하지만 입력 case가 많고, 시간이 2초로 상당히 빠듯한 sorting 문제입니다. 실제로 저도 2번 시도때는 전부 시간 초과가 걸렸었어요. 그래서 연산시간이 빠른 알고리즘을 찾아 봤습니다. Merge sort, 또는 .. 2020. 5. 8. [백준 10989번] 수 정렬하기 3 문제 주소는 여기로 기본 알고리즘 공부 겸 숫자 정렬 문제를 풀어보고 있었습니다. 위 문제에 대해 제가작성한 답은 아래와 같습니다: #include #include #include using namespace std; void arraysort(vector& array, int length) { for (int i = 0; i array[j]) swap(array[i], array[j]); } } } int main() { int size; cin >> size; if (size 10000000) return 1; vector array(size); fo.. 2020. 5. 6. 이전 1 ··· 14 15 16 17 18 다음
