hail2y.log

조합 (Combination)서로 다른 n개의 수 중 순서를 생각하지 않고 r개를 선택; nCr로 표현그에 반해 순열 nPr은 순서를 고려조합의 성질이항계수와 파스칼의 삼각형과 관련이항계수: 이항정리에서 각 항의 계수인 조합 nCr → 쉽게 말해, 이항정리에서는 각 항의 계수가 조합으로 나타난다.이항정리: 두 항의 합의 거듭제곱인 (a+b)^n을 전개한 결과를 정리한 것파스칼의 삼각형: 이항계수들을 삼각형 피라미드 형태로 배열한 것  이를 토대로 코드를 짜면 다음과 같다. 아래쪽에 combi() 함수를 보면 위 성질을 적용하여 재귀 호출한 것을 알 수 있다. import java.util.Scanner;public class Combination { public static void main(Str..

int ans = 0;while(left  1보다 mid까지의 합이 S 값보다 크지 않으면서 가장 큰 mid의 값을 찾는 과정 등차수열의 합 공식((첫항 + 마지막항) / 2) * 개수는 즉, mid * 개수인데, 여기에서처럼 1부터 mid까지는 개수가 (mid+1)이 되어 (mid*(mid+1))/2로 표현된다. 공식으로 접근할 생각을 못 했어서 저런 수식이 있길래 한참을 들여다 봤는데 등차수열의 합이었다. 어이는 없었지만 덕분에 1~mid의 합을 이진 탐색으로도 생각해 볼 수 있어서 좋았다. 그리고 아래는 똑같이 등차수열의 합 공식을 다루지만 접근법이 새로워서 한번 참고해 보면 좋을 것 같다. 수들을 도형으로 표현해 넓이 구하는 공식으로 구하였다. 결론적으로는 이 공식으로 귀결된다.   [참고: h..

모판을 만들어서 푸는 문제가 많이 나온다.구간합을 미리 다 구해놓은 합 배열을 만든다. https://www.acmicpc.net/problem/1292  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ1292_ans { public static void main(String[] args) throws IOException { int[] t = new int[1001]; // 0, 1, 2, 2, 3, 3, 3 ... int idx = 1; for (..

(유클리드) 호제법(Euclidean Algorithm)두 정수의 최대공약수(gcd; Greatest Common Divisor)를 쉽게 알아내는 방법gcd(0, A) = A모든 수는 0을 나눌 수 있다. 따라서, 0의 모든 약수는 임의의 정수 A를 포함한다. 따라서, 둘의 gcd는 A가 된다. gcd(a,b) = gcd(b, a%b) (단, a > b) -- b > a이면 값을 바꾼다  cf. 귀류법어떤 명제가 참임을 직접 증명하는 대신, 그 부정 명제가 참이라고 가정하여 그것의 불합리성을 증명함으로써 원래의 명제가 참인 것을 보여 주는 간접 증명법. [네이버사전]import java.io.BufferedReader;import java.io.IOException;import java.io.InputS..

브루트(brute); 무식한, 야만적인, 맹목적인 + 포스(force); 힘=> 발생할 수 있는 모든 경우를 다 따지며 해를 찾는다 = 완전 탐색 (ex. 비밀번호를 4자리로 설정한다고 할 때, 0000~9999를 다 탐색하여 암호를 해독한다.)사용하는 경우- 문제의 입력 크기가 작을 때 신속하게 결과 얻을 수 있다.- 최적해를 찾을 때 모든 경우를 다 따져보므로 정확도는 굿(but 경우의 수가 너무 많을 경우 실행시간이 너무 오래 걸리거나 메모리 효율 면에서 매우 비효율적일 수 있다.)- 문제의 구조가 간단하고 직관적일 때 유용하다. 다시 정리하자면,완전탐색의 장단점장점 - 알고리즘을 구현하는 것이 상대적으로 쉽다.- 복잡한 알고리즘 없이 빠르게 구현이 가능하다.단점- 알고리즘의 실행시간이 상대적으로 ..

벨로그에서 95% 쓴 글이 임시저장도 안 되고 출간도 안 된 채로 순식간에 날아갔다. 정신 잃고 쓰러질 뻔 했지만 친구가 세뇌하듯 위로해줬다...고맙다 덕분에 정신승리하며 다시 쓴다..! 내가 학기 중에 필기 노트 다 날라간 것도 견뎌냈는데... 아자아자 파이팅! 파이썬이랑 c 공부할 때도 피라미드 문제는 항상 어려웠는데 이제는 더 이상 어려움 느끼면 안 될 것 같아서 각 잡고 다 다뤄보기로 다짐했다! 이렇게 앞으로 나아가는 거겠지- 실제로 어제 코드들 쳐 보면서 하나하나 되니 자신감도 생기고 더 공부하고 싶단 생각이 들었다. 이제 잡담 그만하고 바로 들어가자. (240702) 아래는 반복문을 이용해 구현했지만 시간복잡도를 더 줄이는 방법으로 조건문으로도 엮어서 풀 수 있다. 하루코딩 님 유튜브 영상을 ..