원당컴퓨터학원

자료 출처 - 알고리즘트레이닝 이 표는 프로그래밍인사이트에서 출간한 알고리즘 트레이닝 서적을 인용했습니다.국내 정보 올림피아드를 준비하는 학생이라면아시아정보올림피아드 또는 국제정보올림피아드 에서의 출제 유형을 확인하고 그에 따른 기법들을 연구하고 숙지할 필요가 있을것입니다.국내 정보 올림피아드 또는 국내 알고리즘 대회 역시 이러한 대회의 문제와 유형이 비슷할 것입니다. 또한 경진대회(프로그래밍 대회) 에 능숙해 지기 위해서는 알고리즘을 설계한 후에는 반드시 다음과 같은 질문을 해 보아야 한다고 조언 하고 있습니다. 1. 범위 내에 최대입력이 주어졌을때, 현재 만든 알고리즘의 시간 및 공간 복잡도가 그 문제의 시간 및 메모리 제한을 통과 할 수 있는가?- 실제 프로그래밍 대회에서는 제대로 작동하는 알고리즘..

I. 영재의 정의- 영재란 어떤 사람인가에 대한 관점은 오래 전부터 있었으나 아직까지 그 정의에 대하여 일치된 견해를 찾아보기가 힘들다. “영재교육의 시조인 Terman은 IQ 135이상인 자를 일컬어 영재아라 정의하였다. 그러나 해를 거듭하면서 사회성이나 지도력, 높은 성취동기, 예능 분야에까지 그 범주를 넓혀서 광의의 의미로 영재성을 해석하고 있다. 최근에는 ‘영재’라는 용어를 정의할 때 창의성, 일에 대한 집착력, 지도 능력 등 보다 포괄적인 요인들을 포함하려는 경향을 보이고 있다”- Marland는 “영재는 전문가에 의해 뛰어난 능력으로 인하여 훌륭한 성취를 할 것으로 보이는 사람으로 판별된 아동으로 자신과 사회에 기여하기 위해 정규학교가 제공하는 것 이상의 특별한 교육 프로그램이나 도움을 필요로..

에라토스테네스의 체는 소수를 찾는 방법입니다.고대 그리스 수학자 에라토스테네스가 발견하여 에라토스테네스의 체라고 이야기 하는데요. 원리는 다음과 같습니다.먼저 0 과 1은 소수가 아니라고 마킹을 해 놓고 2부터 찾아 가면서 해당 수가 소수라면 소수의 배수들을 모두 너는 소수가 아니야 라고 마킹을 해 놓는 것입니다. 예를 들면 2를 만났을때 2의 배수 4,6,8,10,.... 등과 같은 모든 짝수들에 대해서 소수가 아니라는 것을 마킹하는 것이죠.그리고 3을 만나면 3의 배수 6,9,12,15.... 등과 같이 3의 모든 배수들을 소수가 아니라고 마킹을 합니다.4를 만나면 이미 소수가 아니라고 마킹이 되어 있기 때문에 그 배수들은 확인 할 필요가 없습니다.5를 만나면 5의 배수들에 대해서도 마찬가지로 소수가..

제가 몇주 전부터 알고리즘 상으로는 최대 600만번 계산이 되어 시간초과가 나올 수가 없는데 (알고리즘상 1초당 최대 1억번 연산 처리를 기준으로 함) 계속해서 타임아웃이 발생하더라구요. 무엇이 문제인지 몰라서 알고리즘은 맞는데 구현이 잘못 된 줄 알고 수십번도 더 제출해 보았는데요...결국 몇주동안 풀지 못했던 문제가...scanf,printf 를 사용하지 않고 cin cout 을 사용해서 타임아웃이 걸렸다는 것을 아는 순간 맥이 쫙 빠지네요...ㅠ.ㅠ 알고리즘으로는 전혀 문제가 없는데 또 다른 알고리즘을 요구하는 문제인줄 알고 알고리즘 해법을 찾으러 구글링 하다가 도저히 해법을 못찾아 포기했던 문제였는데요.. 우연한 계기로 cin cout 이 scanf printf 보다 컴파일 속도가 느린것을 확인했..

유클리드 호제법은 2개의 자연수 또는 정수의 최대 공약수를 구하는 알고리즘의 하나 입니다.정보올림피아드에서 2개의 최대 공약수를 구하는 문제가 종종 나오는데...이때 유클리드 호제법을 이용해서 문제를 풀어 나가면 훨씬 빠르고 유용하게 사용할 수 있습니다.예를 들면 131 과 109 의 최대 공약수를 구하는 문제같은 경우 131이 3의 배수인지 아닌지 판단 하고 109가 3의 배수인지 아닌지 판단 하는 것보다는 다음과 같이 구하면 훨씬 수월하게 풀릴것 같네요.131 % 109 = 22 이므로22 와 109 의 최대공약수와 동일 하고...109 % 22 = 21 따라서 22와 21의 최대 공약수와 동일 하기 때문에 최대공약수는 1이 나오게 됩니다.131이 소수인지 아닌지 판단 하는 것보다 이렇게 판단하는 것..

문제풀이) g(0)=1,g(1)=1,g(2)=2를 반환한다고 되어 있는데...여기서 g의 함수가 무엇을 하는지 먼저 살펴볼 필요가 있을것 같습니다.g(11)이 들어 간다고 하면 i,j,k 가 0 부터 11까지 3중 반복이 됩니다.그런데 어떤 경우에 f(i,j,k) 를 호출해서 r에 누적을 해서 누적한 값을 리턴하게 됩니다.어떤 경우냐 하면 i + 2*j + 3*k == 11 인 경우에 해당합니다.그렇다는 얘기는 다음과 같은 경우에 f(i,j,k)를 호출한다고 볼수 있겠네요.i,j,k 는 다음과 같은 경우 호출 될것 같습니다.i j k 11 0 0 9 1 0 7 2 0 5 3 0 3 4 0 1 5 0 8 0 1 6 1 1 4 2 1 2 3 1 0 4 1 5 0 2 3 1 2 1 3 2 2 0 3 0 1 3..

오늘은 2018년 정보올림피아드 지역대회 초등부 33번 문제를 풀어 보겠습니다. 이번 문제는 while 문과 do while 문의 사용법과 후치증가 후치감소 등의 연산 작업 하는 내용을 확인하는 아주 간단한 내용입니다. 먼저 a=2, b=2 로 초기화 되어 시작 됩니다. while(b) 문장은 b가 0 이 되면 빠져 나갑니다.b가 0 이 되기 전에a=3, b=1a=4, b=0 이 되어 a=4 에서 while 문을 빠져 나가고..그 다음 do while 문에서는 a가 0 이 되면 빠져 나가는 문장입니다.따라서a=3,b=1a=2.b=2a=1.b=3a=0,b=4 따라서 b를 출력하므로 정답은 2번 입니다. 정보올림피아드 문제 풀이 리스트 정리

위와 같은 그림에서 교차점이 발생하는 경우는 a,c,d,h 인 경우 입니다. 이러한 두 선분의 교차점을 검사하는 방법으로는 다음과 같이 찾아 볼수가 있습니다. 1] 각 선분에 대해서 그 선분을 포함하는 양방향으로 무한한 연장선을 긋고 그 두 연장선의 일차방정식을 구한 후에 그로부터 교점을 계산한다. 그 교점이 원래의 두 선분상에 있으면 두 선분은 교차한다. 2] 위의 그림에서 a,c,d,h 인 경우를 살펴보면 다음과 같은 규칙을 찾을 수 있습니다. 1. 선분 AB를 기준으로 볼때 점 C 점 D가 서로 반대편에 존재 하는지 검사 선분 CD를 기준으로 볼때 점 A 점 B가 서로 반대편에 존재하는지 검사 2. 한 선분의 끝점이 다른 선분상에 존재 하는지 검사 3. 일직선상에 있으면서 한 선분의 끝점이 다른 선..

문제풀이)수평선에서 자기 자신과 가장 가까운 거리의 같은 색깔을 찾는 문제이다.가령 입력예 1 에서 0번의 색깔은 1이다 이것과 가장 가까운 색깔 1의 위치는 3 이다 따라서 0의 거리는 33번의 가장 가까운 거리는 0 번과 5번 중에서 가까운 5번이다 따라서 거리는 25번의 가장 가까운 거리는 3번 따라서 거리는 2 풀이1)색깔별로 바로 이전에 나온 위치를 저장해 놓고 자신의 위치에서 바로 이전의 같은색깔의 거리를 저장해 놓는다.만약 처음 나오는 경우는 무한값(최대값)을 설정해 놓는다.그리고 다음에 나오는 색상 (바로 이전에 나온 위치에서 바라보면 현재의 위치가 바로 이전에 나온 위치에서의 다음 위치이다.) 을 비교 하여 이전의 거리보다 짧다면 현재 위치의 거리를 갱신한다. 이렇게 하면 N번 만에 계산..

문제분석)이 문제는 모든 데이터를 찾아 가면서 가장 작은 값과 가장 큰 값을 찾아서 그 차이를 빼주면 됩니다. 일반적으로 가장 작은 값을 찾기 위해서는 min의 초기값은 가장 큰값보다 더 큰 수로 초기화 해 주어야 합니다. 여기서 학생들의 점수는 0~1000 사이라고 했으니 min 값을 1000 이상의 값으로 초기 화 한 후에하나하나 비교 하면서 min 보다 작은 값이 들어 오면 min 값을 갱신하는 형태로 처리하면 됩니다.max 값의 초기값은 가장 작은 값보다 더 작은 0 이하의 값으로 초기화 하면 됩니다.그리고 하나하나 비교하면서 max보다 큰 값이 나오면 max 값을 갱신하면 됩니다. 예제 소스는 네이버 블로그에 올렸습니다.하지만 예제 소스를 먼저 확인 하지는 마시고 먼저 충분히 고민한 후에 직접 ..