원당컴퓨터학원

함수의 개념 집합 A,B에 대해 집합 A에서 B로 가는 관계가 성립 할 때, 집합 A의 원소 a에 대해 집합 B의 원소 b 하나가 대응 되는 관계, 즉 입력값(정의역)에 의해 하나의 결과값(치역)이 존재하는 관계를 함수라 한다. 따라서 함수는 어떤 입력에 대해 단 하나의 결과를 출력한다. "어떤 입력값 x에 따라 하나의 출력값 y가 결정 된다면 y는 x의 함수" y = f(x) 로 표현한다. 함수의 종류 1차함수 : 정의역과 공역이 실수의 집합인 f(x) = ax+b 와 같은 형태의 함수, 그래프는 직선으로 나타난다. 2차함수 : f(x)=ax2 + bx + c(단 a ≠ 0) 와 같은 형태의 함수,그래프는 포물선 형태 지수함수 : y=ax(단,a를 양의 상수,x를 모든 실수) 와 같은 형태의 함수,로그..

다음 그림과 같이 강에서 부터 각 마을까지는 파이프로 연결이 되어 있는데 각 연결 되어 있는 파이프의 굵기가 서로 다릅니다. 위의 그림에서 각 숫자는 1시간에 밸브를 최대로 열었을때 흘려 보낼 수 있는 파이프의 용량입니다. 원당이는 가뭄에 대비하기 위해 강으로 부터 여러 마을을 거쳐 논까지 물을 공급할때 한시간에 최대로 보낼수 있는 물의 양을 알고 싶습니다. 여러분이 위의 그림을 보고 1시간에 흘려 보낼 수 있는 최대 양을 구해 주세요. 문제풀이) 더보기 먼저 강에서 A,B,C 마을에 각각 물을 흘려 보내 봅니다. 그 다음 A,B,C 마을에서 통로로 보낼 수 있는 양의 물을 흘려 보내 봅니다. E에서 논으로 750을 흘려 보내고 남은 10을 D로 흘려 보낸 후 D에서 논으로 340을 흘려 보낼 수 있습니..

원당이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려고 합니다. 하지만 아쉽게도 허브가 없어서 컴퓨터와 컴퓨터를 직접 연결해야 합니다. 그런데 모든 컴퓨터가 자료를 공유하기 위해서는 모든 컴퓨터가 연결되어 있어야 합니다. 이때 네트워크 연결 비용을 책정해야 되는데 기왕이면 가장 작은 금액으로 연결을 하고 싶습니다. 다음과 같이 컴퓨터와 컴퓨터의 연결하는 비용이 주어졌을때 최소로 모든 컴퓨터를 연결하는 비용은 얼마인지 구해 주세요. 6대의 컴퓨터가 있으며 연결비용은 다음과 같습니다. 컴퓨터번호,컴퓨터번호- 연결비용 1,2 - 5 1,3 - 4 2,3 - 2 2,4 - 7 3,4 - 6 3,5 - 11 4,5 - 3 4,6 - 8 5,6 - 8 문제풀이) 더보기 그림으로 그려보면 위와 같습니다. 여기..

비트연산 활용 1. 모든 부분집합 순회하기 예) 피자의 토핑 종류가 (페페로니,소시지,양파) 라고 하면 {페페로니},{페페로니,소시지},{페페로니,소시지,양파},{소시지},{소시지,양파},{양파} 와 같이 하나 하나 열거하는 경우 다음과 같이 처리 1 2 3 4 5 6 for (int subset = pizza; subset; subset = ((subset-1) & pizza)) { //subset 은 pizza의 부분 집합 } Colored by Color Scripter cs 2. 비트마스크를 활용하여 에라토스테네스 체 치기(체치는 메모리를 적게 잡기 때문에 훨씬 더 많은 양의 체를 칠 수 있다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..

원당이와 길동이가 다음과 같은 게임을 하려고 합니다. 게임의 규칙은 다음과 같습니다. 규칙1) 맨 처음 게임을 시작하는 사람은 모든 공을 한번에 가져가는 것을 제외하고 임의의 수 만큼 공을 가져 갈 수 있습니다. 규칙2) 두번째 가져가는 사람 부터는 한개 이상의 공을 가져가며 상대편이 바로 전에 가져간 공의 2배 이하로만 공을 가져갈 수 있습니다. 즉 첫번째 사람이 1개를 가져갔다면 두번째는 1개 또는 2개 를 가져 갑니다. 규칙3) 마지막 공을 가져가는 사람이 이깁니다. 그렇다면 공이 현재 10개가 있습니다. 원당이가 먼저 시작하려고 하는데 원당이가 이길수 있는 방법이 있는지 궁금합니다. 만약 이길수 있다면 원당이는 처음에 몇개를 가져가야 이길 수 있을까요? 여러분이 원당이에게 알려 주세요. 정답) 더..

비트마스크란? 컴퓨터는 모든 정수형변수를 이진수로 표현합니다. 이 때 이진수의 한 자리를 비트(bit)라고 부릅니다. 비트는 0 또는 1의 값을 가지며 컴퓨터가 표현하는 모든 자료의 근간이 됩니다. 이러한 이진수표현을 자료구조로 사용하는 기법을 비트마스크(BitMask) 라고 부릅니다. 비트마스크는 엄밀하게 ㅏ료구조라고 할 수는 없지만 굉장히 유용하게 사용 됩니다. 비트마스크를 왜 사용하는가? 1. 더 빠른 수행시간 : 비트마스크 연산은 O(1)으로 구현이 됨, 따라서 여러번 수행하는 경우에는 작은 최적화로 속도 향상을 가져올 수 있음 2. 더 간결한 코드 : 반복문 없으 한줄에 사용하므로 짧은 코드를 작성 3. 더 작은 메모리 사용 : 32비트형 정수형 자료형에 32개의 0/1 형태의 정보를 저장 비트..

2차원 펜윅트리를 구현하기 전에 1차원펜윅트리를 먼저 이해합니다.(https://wondangcom.tistory.com/1582) 1차원 배열이 여러개 인 행렬 구조의 데이터가 업데이트가 많은 경우 사용하게 되는데 1차원펜윅트리를 여러 개 이어 붙인 것이 2차원 펜윅트리라고 생각할 수 있다. 2차원의 구간합을 구하기 위해서 2개의 인덱스(y,x)가 필요하다. 그림으로 이해하면 다음과 같다. (x1,y1) ~ (x2,y2) 의 구간합을 구하는 방법을 살펴 보면 먼저 (0,0)~(x2,y2) 의 구간합을 구한다. 이때 녹색과 하늘색 부분인 (0,0) ~ (x1,y2), (0,0)~(x2,y1) 구역을 빼 주면 되는 것을 확인 할 수 있다. 이렇게 두개의 구간 합을 빼 주면 (0,0) ~ (x1,y1) 구간..

펜윅트리(Fenwick Tree)란? - Binary Indexed Tree 라고도 하며 이진수를 이용하여 위치값을 표현하는 세그먼트 트리와 유사한 트리 펜윅트리(Fenwick Tree) 의 개념 10진수 수를 이진수로 표현해 보면 다음과 같다. 3 = 00000011 4 = 00000100 5 = 00000101 6 = 00000110 8 = 00001000 9 = 00001001 10 = 00001010 11 = 00001011 12 = 00001100 16 = 00010000 여기서 이진수의 마지막 1의 위치를 확인하면 다음과 같다. 3= 왼쪽에서 첫번째 자리 (10진수의 값으로 1) 4= 왼쪽에서 3번째 자리 (10진수의 값으로 4) 5= 왼쪽에서 첫번째 자리(10진수의 값으로 1) ... 16 ..

18세기 초 프러시아의 옛 지점 쾨니히베르크의 중심을 흐르는 프레겔 강에 7개의 다리가 놓여있었습니다. 당시 시민들 사이에서 같은 다리를 두 번 이상 지나지 않고 이들 7개의 다리 를 꼭 한 번씩 모두 건널 수 있을지 없을지에 대한 논의가 많았는데요 만일 한 번만 다리를 지나는 것이 가능하다면 어떤 방법으로 다리를 건너야만 할까? 라는 문제입니다. 여러분이라면 이 문제를 어떻게 말할 수 있을까요? 이 문제를 해결하기 위해 오일러라는 수학자는 이 문제를 쉽고 단순하게 표현하기 위해 다리와 섬들의 사이 관계를 평면상의 점과 선분으로 표현하였습니다. 이렇게 여러 관계를 점과 선분으로 표현한 모양을 그래프라고 합니다. 즉, 위 문제를 점과 선분으로 표기 하면 다음과 같은 그림이 된다. 이처럼 그래프는 문제를 해..

세그먼트 트리(Segment Tree)란? - 주어진 쿼리에 대해 빠르게 응답하기 위해 만들어진 자료구조 - 구간 중에 Max,Min,Sum(최대,최소,구간의 합) 등을 빠르게 갱신할 수 있는 자료구조 세그먼트 트리(Segment Tree) 구현 목적 배열의 데이터 수 : 10개 배열의 데이터 A[10] = {1,2,3,4,5,6,7,8,9,10} 목적 : 구간에 대한 합 예) 4번째 부터 6번째까지의(배열의 3번지부터 5번지까지의) 구간합은? 15 이러한 구간합을 구하는 가장 간단한 방법은 합을 미리 구해 놓고 1번째 부터 6번째의 합 21 에서 1번째 부터 3번째의 합 6을 빼면 15가 나온다. 1 2 3 4 5 6 7 8 9 10 1 3 6 10 15 21 28 36 45 55 하지만 각 데이터가 ..