원당컴퓨터학원

이분그래프란 그래프 G=(V,E)에서 꼭짓점 집합 V가 V=V1 U V2 이고 V1 ∩ V2 = ∅ 을 만족하는 두 집합 V1과 V2로 분리되며 그래프의 모든 모서리가 V1의 한 꼭짓점에서 V2의 어떤 꼭짓점으로 연결되는 그래프 꼭짓점 집합 V = {a,b,c,d,e,f} 를 두개의 집합 V1 = {a,c,e},V2={b,d,f} 로 분할 되며 V=V1 U V2 이고 V1 ∩ V2 = ∅ 을 만족하므로 이분 그래프이다. 이러한 이분 그래프를 찾는 방법은 두개의 색을 이용해서 색칠해 나가는 방법이 있다. 완전이분그래프란 그래프 G=(V,E)에서 꼭짓점 집합 V가 V=V1 U V2 이고 V1 ∩ V2 = ∅을 만족하는 두 집합 V1과 V2로 분리되고, 그래프의 모든 모서리가 V1의 한 꼭짓점에서 V2의 모든..

원당이 동네에는 우물이 있다. 이 우물은 10분 동안 7/5 리터의 물이 솟아 나온다. 그렇다면 하루에 나오는 물의 양은 얼마인가? 문제풀이) 하루 24시간을 분으로 변경하면 24 * 60 = 1440분이다. 10분에 7/5 리터의 물이 솟아 나오므로 1분에 7/50 리터의 물이 솟아 나온다. 따라서 하루에 나오는 양은 1440 * 7 / 50 = 1008/5 리터이다. 정답) 1008/5리터 또는 201.6 리터

목표 덧셈 연산을 할 때 100,1000,10000 과 같이 떨어지는 수로 채워서 연산하는 방법에 대해 살펴 본다. 개념이해하기 91 + 997 + 9998 + 99987 과 같은 수를 연산할 때 다음과 같이 채운수로 생각해 본다. (100-9)+(1000-3)+(10000-2)+(100000-13) = 111100 - 9 - 3 -2 - 13 = 1111077 위와 같이 100,1000,10000,100000 을 채워서 부족분만 연산해서 빼주는 방법으로 처리하면 된다. 작품소개 엔트리봇이 계산하는 방법을 얘기 해 주고 몇문제를 풀지 물어 본다. 문제 수 만큼 반복하면서 100을 채우는 수,1000을 채우는 수,10000을 채우는 수,100000을 채우는 수 등을 임의의 수로 정해서 덧셈 연산을 묻고 기..

계산 순서 바꿔 빠르게 계산하기 연산 순서가 동일한 경우 +,- 또는 *,/ 와 같은 경우 계산 순서를 서로 바꾸어 빠르게 연산 할 수 있다. 다음은 문제 풀이 과정의 하나이다. 예제1) 73.2 – 32.1 + 26.8를 계산하시오. 문제풀이) (73.2 + 26.8) – 32.1 = 100 – 32.1 = 67.9 예제2) 123 – 73 + 19 + 377 + 981 - 27 을 계산하시오. 문제풀이) (981 + 19) + (377+123) – (73+27) = 1000 + 500 – 100 = 1400 위의 예시를 보고 다음의 문제를 풀어 보시오. 문제 1) 64.1 – 27.9 + 82.1 + 35.9 + 117.9 – 72.1를 계산하시오. 더보기 (64.1+35.9)+(82.1+117.9)..

명제란? 명제란 객관적으로 참과 거짓을 구분 할 수 있는 문장으로 추상적이고 주관적인 견해를 배재한 문장이다. 예를 들어 "대한민국의 수도는 서울특별시이다" 에서 이 내용은 객관적으로 참,거짓을 판별 할 수 있으므로 명제이다. "이 컴퓨터는 비싸다" 에서 이 내용은 개인의 기준에 따라 참 거짓이 달라 질 수 있으므로 명제가 아니다. 이 때 조건은 알파벳 p,q,r 순으로 사용하고 그의 진리집합을 각각 영어 대문자를 사용하 P,Q,R로 사용하는 것이 관례이다. 논리연산자와 합성명제 1. 부정(not) ~p 와 같이 사용하면 문장 p가 명제일 때 "p가 아니다" 를 의미하며 p의 진릿값의 반대를 갖는 명제이다. 2. 논리곱(and) p ∧ q 와 같이 사용하며 p,q가 명제일 때 p,q 의 진릿값이 모두 참..

문제 출처 : https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net 문제를 살펴 보면 테스트케이스를 입력 받고 문자열과 반복할 횟수를 입력 받아 문자열을 하나씩 잘라내서 반복할 횟수만큼씩을 반복하여 하나의 문자열을 만들어 출력한다. ​ 알고리즘 테스트 케이스 횟수를 입력 받는다. 테스트 케이스 횟수 만큼 반복하면서 다음을 수행한다. 반복횟수와 문자열을 입력 받는다. 문자열 길이만큼 반복하면서 앞에서 부터 문자열을 하나씩 잘라내어 반복횟수만큼..

바구니 안에 빨간공 120개와 파란공 30개가 들어 있다. 이렇게 들어 있는 바구니에서 다음과 같은 절차에 의해 공을 꺼낸다. 1. 두개의 공을 꺼낸다. 2. 만약 두개의 공의 색깔이 같으면 빨간공 한개, 서로 다르면 파란공 한개를 집어 넣는다. 3. 1과 2를 계속 반복한다. 바구니의 마지막 공의 색깔은 어떤 색이 될까? 문제풀이) 바구니 안의 공이 빨간공 120개 파란공 30개 에서 시작을 한다. 만약 두개 모두 빨간공을 꺼냈다면 빨간공이 119개,파란공 30개가 된다. 두개 모두 파란공이었다면 빨간공이 121개,파란공은 28개가 된다. 두개 모두 색깔이 다르다고 하면 빨간공 119개 파란공 30개가 된다. 이것을 확인 했을 때 빨간공은 1개가 줄거나 1개가 늘어난다. 파란공은 0개가 줄거나 2개가 ..

소인수 분해를 이용하여 계산하기 곱셈 연산을 할 때 소인수 분해를 이용하여 계산하면 계산이 빨라진다. 다음은 문제 풀이 과정의 하나이다. 예제1) 75 * 12를 계산하시오. 문제풀이) (3 * 25) * (3*4) = 3*3 * 25*4= 900 4*25 = 100 이 되는 원리를 이용하여 연산하였다. 예제2) 250 * 48 을 계산하시오. 문제풀이) 250 * 48 = (2*125) * ( 3*2*8) = (3*2*2)*(8*125)=12000 125 * 8 = 1000이 되는 원리를 이용하여 연산하였다. 위의 예시를 보고 다음의 문제를 풀어 보시오. 문제 1) 44 * 25 를 계산하시오. 더보기 4*11*25=1100 문제2) 625 * 16 을 계산하시오. 더보기 6*125*2*8=12000

모스알고리즘이란? 모스 알고리즘은 업데이트가 없는 구간 쿼리들을 처리하는 알고리즘이다. 기본 아이디어는 업데이트가 없기 때문에 '앞에서 계산된 값을 최대한 활용하자'이다. 특히 조회만 하는 경우는 쿼리의 순서를 자유롭게 바꿀 수 있는 환경에서 미리 계산된 값을 다시 이용할 수 있을 것이다. 이전에 살펴 보았던 제곱근분할법(https://wondangcom.tistory.com/2721) 을 이용하여 모스알고리즘을 구현 할 수 있는데 이 알고리즘으로 해결할 수 있는 문제는 원소의 수정은 없고 구간 내에서 어떤 결과를 찾는 종류의 쿼리만 있는 문제이다. 그렇다면 기존 문제보다 활용범위가 좁은 것은 아닐까? 간혹 세그먼트 트리 등을 이용해서 해결하지 못하는 경우가 발생한다. 이러한 문제 유형은 아래에서 살펴 ..

다항 회귀(https://wondangcom.tistory.com/2684) 에서 우리가 과대 적합과 과소적합을 피하는 방법으로 교차검증으로 판단 한다고 언급을 했었다. 여기서는 교차검증은 무엇이고 어떤 원리인지 살펴 보자. 1. 교차검증의 원리 교차 검증은 전체 데이터 세트를 훈련세트와 테스트 세트를 8:2로 나눈 다음 훈련세트에 해당하는 부분을 다시 K개의 덩어리로 나눈다. 그런 다음 1개씩을 따로 떼어서 검증에 사용하고 나머지 4개의 덩어리를 훈련에 사용하는 방식이다. 2. 교차 검증 과정 훈련 세트를 k개의 폴드로 나눈다. 첫번째 폴드를 검증 세트로 사용하고 나머지 폴드(k-1ro)를 훈련 세트로 사용한다. 모델을 훈련한 다음에 검증세트로 평가한다. 차례대로 다음 폴드를 검증 세트로 사용하여 반복..