안 쓰던 블로그

2015 시도예선 중고등부 문제 1.8진법이라는 것은 1~10까지 곱한 수를 8로 계속 나누면서 나누어떨어지는 횟수를 의미한다. 물론 전부 계산할 필요는 없고 소인수분해해서 나누면 된다.소인수분해하면 2^7*x가 나오니까 8=2^3 이 2번 나온다. 2.두 정점을 연결하는 간선 1개를 추가하면 연결된 정점에 대한 차수는 A쪽과 B쪽에 2개가 증가한다. 즉 모든 정점의 차수의 합(연결된 다른 정점의 수의 합)은 항상 짝수임을 알 수 있고 차수의 합이 홀수인 경우를 찾으면 1번 3.확통 문제. 1씩 넣어두고 네 정수를 합쳐서 6을 만든다. 4H6 = 84다른 방법도 있는데 두 자리에 1씩 넣어두고 남은 두 자리 맨 앞+ 맨 끝수 = 8인 경우를 세보면(1,7) (2,6) ... (4,6) ... (1,7) ..

1. 평균값이니까 x y z는 자연스럽게 차이가 일정한 수로 정해진다. 2.나머지가 반복된다. 3.센다. 4.거리가 같은 사실을 가지고 방정식을 세운다. 거속시 문제 5. 이렇게 생긴 복면산의 경우 a+b+c 값을 보기에서 찾아 두고 푸는 게 빠름a+b+c를 했는데 a가 나왔다는 말은 b+c가 10이라는 의미고 a+b+c+1이 b라는 말은 b+c가 일단 10으로 올라가면 a+1은 b라는 의미가 됨. 백의 자리도 같은 이유로 a+1는 b니까 c는 1 이상이 될 수 없어서 1이 되고, b는 9가 된다.a는 8이 된다. 6.어느 한 줄에 있는 숫자들은 아무리 교환해도 한 줄에 있다.한 줄에 있지 않은 선택지가 정답 7.어떤 점에서 한 번 갔다가 다시 돌아오려면 2번이기 때문에 짝수번 이동해야 함 0~10을 직..

1. 계산 2.원래는 1~9가 몇 번 나오는지를 셌는데 그렇게 세니까 복잡하다.그냥 1이 몇 개 2가 몇 개 이런 식으로 세는 게 좋다.나올 수 있는 자리는?_??_?__ 이렇게 네 가지이고1은 한 자리에 1개 두 자리에 10개 + 9개 나오고 3번째 자리 1개 가능하니까 21개2는 1개 / 19개 만 가능하니까 20개3도 20개... 해서 1만 빼고 20개씩 나온다(1~9)*20 + 1 = 901 3.철수 110 바퀴 = 330030, 25, 40의 최소 공배수 = 6003300 보다 작은 600의 배수를 찾아 세면 됨5개 4.이진탐색, 나눠보면 10번 5.해보면 나옴1 –2 –3 –1 2 3 이 반복된다 6.그냥 확통 문제 1, 2 최소 182, 3 최소 111, 3 최소 13 이니까 1+2+3-1/..

1. (1.1점) 12^2017 을 8진수로 표기할 때 가장 오른쪽에 나타나는 연속된 0의 개수는 몇 개일까? 12에 2가 몇 개?12=(2^2)*3의 2017승이고 8은 2^3이다.3은 아무리 곱해봤자 0이 나올 수가 없기 때문에 3 없다고 치고 2^2^2017 = 2^4034임2^4034를 8로 바꿔보면 2*(8^1344)가 나오고 8에 n승에서 n이 0의 개수를 의미한다 2. (1.2점) 다음의 그래프에서 모든 간선의 길이가 1일 때 정점 p에서 정점 z까지 도달하는 가장 긴 경로의 길이는? 나가는 간선만 있는 노드를 지우고 도착지부터 거꾸로 올라가면 된다 3. (1.3점) 지구에서 달까지의 거리는 384,400km이다. 여러분에게 폭이 1cm이면서 길이가 충분히 길면서 두께는 0.1mm로 얇은 ..

[두부모판 자르기](backtracking 기법)KOI 두부 공장에서 만들어내는 크기가 n*n(n은 11이하의 자연수)인 두부 모판이 있다.이 모판을 1*1크기의 단위두부가 2개 붙어있는 형태의 포장단위 (즉, 1*2 혹은 2*1크기)로 잘라서 판매한다.그런데 두부제조 공정상 모판에 있는 각 단위두부의 품질은 A, B, C, F급으로 분류되고, 잘려진포장단위의 두부 가격은 이 포장단위에 있는 두 개의 단위두부의 품질에 따라서 다음과 같이 정해진다. A B C F A 100 70 40 0 B 70 50 30 0 C 40 30 20 0 F 0 0 0 0 포장 단위에 있는 두 단위두부가 [A, A]급이면 100원을 받고, [A, B]급이면 70원을 받는 식이다.F급이 하나라도 있으면 한 푼도 받을 수 없다.두..

7차시 동적테이블의 응용2 [색상환 문제] N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003으로 나눈 나머지 출력 빨간색부터 시작하면 인접한 연지, 주황을 선택 못하게 되니 빨강-> 다홍부터 시작하고 빨간색이 아니라면 주황색부터 하면 됨 탐색함수solve(a, b)=현재 a번 색상에 대해 고려하는 상태이며, 지금까지 규칙에 맞도록 b개의 색깔을 이미 선택한 상태 -> X빨간색을 선택하면 나오는 문제를 인식할 수 없음 solve(a, b)=현재 a번 색상에 대해 고려하는 상태이며, 지금까지 규칙에 맞도록 b개의 색깔을 이미 선택했고, c가 참이면 마지막색을 고를 수 없는 상태 1234567891011121314151617181920212..

1차시 관계기반 알고리즘 설계정보/과학 분야의 수학적 귀납법은 문제 증명이 아닌, 문제 해결의 방법으로 쓰이고 있다.수학의 수학적 귀납법-1. P(1)이 성립함을 보인다.2. P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다. 정보/과학 분야의 수학적 귀납법-1. 입력값이 n인 문제의 해를 f(n)으로 정의한다. (이 부분이 다르다)2. f(1)을 직접 구하여 출력한다.3. f(k)를 이미 구해두었다고 가정하고 f(k)를 통해 f(n)을 구하여 출력한다. 2차시 재귀함수의 설계[숫자 뒤집기]방법1. solve(n)을 이용한 재귀호출을 이용1. n을 입력받고2. n%10 출력, solve(n/10) 호출3. n이 0이 아니면 반복 12345int solve(int n){ if(n==0) retu..