myCode/Baekjoon Online Judge
-
알고리즘 정리myCode/Baekjoon Online Judge 2016. 11. 6. 16:31
출처 - http://gooddaytocode.blogspot.kr/2016/04/blog-post_27.html 해당 블로그 좌측 메뉴에 다른 자료도 많음 알고리즘 정리 알고리즘완전 탐색(Exhaustive Search)가능한 경우를 모두 구해서 문제의 해결 방법을 찾는 것실행시간이 너무 길어 제한 시간 내에 문제를 해결할 수 없는 경우가 많다Brute-force searchN 중 반복문을 이용하는 방법큐를 이용하는 방법순열을 이용하는 방법 (재귀 호출로 가능)재귀 호출을 이용하는 방법완전 탐색을 구현하기 용이다른 여러 알고리즘에서 사용코드가 간결하고 구현이 직관적임특징: 쉬운 문제를 어렵게 풀어야 한다특징: 어려운 문제를 쉽게 풀 수 있다설계1. 문제해결을 위해 수행해야 하는 작업을 2. 유사한 형태..
-
k-th smallest selection algorithm (k번째로 작은 숫자를 찾는 알고리즘)myCode/Baekjoon Online Judge 2016. 11. 1. 20:48
http://hackability.kr/entry/Quick-Selection%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-On-%EC%84%A0%ED%83%9D-%EB%B0%A9%EB%B2%95 보통 배열안에서 k번째로 작은 숫자를 구하라라고 하면sort 한 후에 arr[k] 이런식으로 찾는데 O[nlogn]의 매우 비효율적인 방법이다. worst case가 O[n]의 방법을 소개한다.
-
xor 쿼리 (벡터버젼)myCode/Baekjoon Online Judge 2016. 11. 1. 20:20
스타벅스 쿠폰을 위한 위대한 도전이 시작된다. 11.1 시간초과가 뜬다. // Example program#include #include #include using namespace std; int quick_selection(int a, int n, vector ArrList, int k); int main(){ vector v; v.reserve(500000); vector::iterator iter; int queryNum; int totalNum; int x,L,R; cin >> totalNum; for (int i=0; i> queryNum; if (queryNum == 1) { cin >> x; v.push_back(x); } else if (queryNum == 2) { cin >> L >>..
-
XOR 쿼리 [list 버젼]myCode/Baekjoon Online Judge 2016. 11. 1. 20:12
// Example program#include #include #include using namespace std; int main(){ list qList; list::iterator iter; int queryNum; int totalNum; int x; cin >> totalNum; for (int i=0; i> queryNum; if (queryNum == 1) { cin >> x; qList.push_back(x); } else if (queryNum == 2) { } else if (queryNum == 3) { } // display elements for (iter = qList.begin(); iter != qList.end(); ++iter){ cout
-
1002번 문제 : 터렛 (부제 : 도대체 뭘 빠뜨린거야 ㅓㄼ쟏러쟙ㄷ허)myCode/Baekjoon Online Judge 2016. 8. 18. 23:08
FROM - https://www.acmicpc.net/problem/1002 중학교 수학에서 배우던 원 두개의 내접, 외접, 만나는 점의 갯수를 응용한 문제다. 2차원 평면에서의 두 점의 x,y 좌표가 주어지고, 그 좌표를 중심으로 하는 원의 길이도 주어진다. 이걸 단서로 두 원이 만나는 점의 갯수를 구하면 된다. 모든 경우의 수를 따져서 세심하게 코딩했다. 그러나 계속 틀린다고 나온다. 몇시간을 걸쳐 고민한 결과... 출력 마지막에 endl, 즉 개행을 안넣어줘서 틀린거였다.. 후 인생.. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std; int main(){ int num; ci..
-
문제 1463번 : 1로 만들기myCode/Baekjoon Online Judge 2016. 8. 14. 15:25
문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최소값을 출력한다. 다이나믹 프로그래밍을 이용하는 문제다. min_DP[100001] 의 배열을 선언해 배열의 각 인덱스 값에 따라 그 값을 구하기 위한 최소한의 연산 수를 저장해놓는다. 예를 들자면 min_DP[2] = 1, min_DP[10] = 3 이런 식으로 저장 for 문을 이용해 2부터 시작하여..