알고리즘(アルゴリズム） 썸네일형 리스트형 Greedy 그리디 : 어떤한 것을 기준을 정렬을 해서 시작 1.쪼갤 수 있는(fractional) 배낭 문제에서 그리디는 100프로 최적값을 찾아 줌. 2. canonical Coin System에서 그리디는 100프로 최적값을 찾아 줌 3. Interval Scheduling 알고리즘에서는 그리디가 100프로 최적값을 찾아 줌. 사용하기 적합할 때 1. DP 처럼 동적으로 데이터가 수시로 바뀔 때! 2. DP는 무조건 중복된 하위 문제가 존재하기에 빠르게 최적값을 구할 수가 있다. 하위 문제가 존재하나 중복되지 않은 경우에는 그리디로 빠르게 구해 볼 수도 있다.(최적값은 보장 못함) =========================================================================.. 더보기 long vs int 문제 출처 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 백준을 풀다가 맞왜틀!?의 함정에서 벗어 나지를 못하였다. 아니나 다를까 자료형의 문제였다. 최종 결과 SUM 변수는 long long형으로 선언을 하였고, 정수를 담을 배열(num)은 INT형으로 선언을 했다. 그러나 여기에 고약한 논리적 함정이 있었다. 우선 int형의 크기는 플랫폼마다 다르다. 예를 들어, 32bit 체제일 떄는 4 byt.. 더보기 반례(counterexample)를 자동으로 찾아 주는 코드(Python/C) 가끔 문제를 풀다 보면 예제도 다 통과했는데 도대체 왜 틀렸는지 알 수 없는 문제들이 있다. (왜맞틀?????) 그럴 때 진짜 답답해서 미쳐버릴 거 같은 심정으로 반례를 찾아 헤매는데 이게 찾기 쉽지 않다. 그럴 때는 반례 생성기를 만들어서 찾으면 된다. 이 반례 생성기는 백준 1654문제를 기준으로 만들었다. 총 3단계에 걸쳐서 작성을 한다. Python 1. 예제 생성 함수 작성( EX.입력값) 우선 example()이라는 예제 생성 함수를 만든 뒤, 문제에 맞춰서 randint()으로 최소 값, 최대 값 주고 예제를 생성하면 된다. 원래 1 더보기 수열에서 중앙값을 최적으로 구하는 알고리즘(백준 1655번) 문제 출처 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 중간값 구하기 알고리즘은 다음과 같다. 1. 최대 힙의 크기는 최소 힙의 크기와 같거나, 하나 더 크다. 2. 최대 힙의 최대 원소는 최소 합의 최소 원소보다 작거나 같다. 이때 알고리즘에 맞지 않다면 최대 힙, 최소 힙의 가장 위의 값을 swap해준다. [결과] 이때 이 두가지 규칙을 유지해 준다면 항상 최대 힙 top값이 중간값이 된다. 예시 그림을 통해 어떻게 구현.. 더보기 이전 1 2 3 4 다음
