최대합 찾기 아래 그림은 숫자 삼각형을 보여준다. 맨 꼭대기에서 바닥에 까지 한 층에 하나씩 연결되는 길을 찾아내려 가는데 그 합이 최대가 되는 것을 구하려는 문제이다. 여기서 한 층씩 내려간다는 것은 대각선 방향으로 왼쪽 혹은 대각선 방향으로 오른쪽으로 내려가는 것이다. 아래 그림에서 최대가 되는 합은 얼마인가? 출처 : 정보올림피아드 2008년 초등부 12번문제 정답) 37 문제풀이) 정보/이산수학 2020.02.15
정사각형 찾기 16개의 점이 아래와 같이 놓여 있다. 점선으로 이은 두 점사이의 거리가 모두 같다고 할 때, 서로 다른 네 점을 이어 만들 수 있는 정사각형의 개수는 모두 몇 개인가? 출처: 정보올림피아드 2008년 초등부 11번 정답) 20개 정보/이산수학 2020.02.14
한붓그리기 도형 그리기 출처 : 정보올림피아드 2009년 초등부 15번 문제 정답) 3 문제풀이) 완전그래프는 모든 정점에 선이 연결되어 있어야 한다. 시작점과 끝점이 같기 위해서는 모든 정점의 연결선이 짝수이어야 한다. 따라서 최소 3개이 선을 빼야만 모두 짝수가 된다. 정보/이산수학 2020.02.13
쌓기나무 수 세기 출처 : 정보올림피아드 2010년 중등부 2번 문제 정답) 24 문제풀이) 최대값 : 맨아래 6개 중간 6개 맨 위 1개 = 13개 최소값 : 맨아래 6개 중간 4개 맨 위 1개 = 11개 정보/이산수학 2020.02.11
삼각형 넓이 구하기 출처 : 2012년 정보올림피아드 초등부 3번 문제 정답) 3.5 문제풀이) 전체에서 흰색 부분의 넓이를 빼면 다음과 같이 생각해 볼 수 있다. 삼각형 면적은 높이*밑변/2 이므로 1의 면적은 2*3/2 =3 2의 면적은 1*2/2=1 3의 면적은 1*3/2=1.5 전체 사각형 면적 3*3=9 따라서 9 - 3 - 1 - 1.5 = 3.5 정보/이산수학 2020.02.08
높이균형트리의 최소 노드수 구하기 출처 : 정보올림피아드 2012년 중등부 15번 문제 정답) 54개 문제풀이) 최소 노드 이므로 1 일때는 1 높이 2일때는 루트노드 1 + 왼쪽 노드 1 이다. 높이 3일때는 루트노드 1 + 왼쪽/오른쪽 2 + 자신의 높이 1 = 4이다. 높이 4일때는 루트노드 1 + 왼쪽/오른쪽 2 + 왼쪽 자식 2 + 오른쪽 자식 1 + 왼쪽 손자 1 = 7 그림을 그려 보면 바로 전 트리를 왼쪽에 갖다 놓은 후에 그 전전 트리를 오른쪽에 갖다 놓고 루트를 하나 올리는 형식이 된다. 이러한 규칙으로 테이블을 그려 보면 다음과 같이 그릴 수 있습니다 전항 + 전전항 + 현재 루트(1) 형식으로 구할 수 있습니다. 정보/이산수학 2020.02.07
수열의 갯수 구하기 출처 : 정보올림피아드 2012년 중등부 14번문제 정답 : 239 문제풀이) 두 수의 차이가 1이기 때문에 다음과 같이 생각해 볼수 있다. 첫째자리 1,2,3 이 올 수 있다. 둘째자리는 첫째자리가 1인 경우 1,2 첫째자리가 2인 경우 1,2,3 첫째자리가 3인 경우 2,3 이 올 수 있다. 이렇게 생각해 보면 끝나는 경우를 테이블로 그려 볼 수 있는데 다음과 같이 그려 볼 수 있다. 마지막 자리수가 1,2,3 으로 끝나는 경우 1번째 자리,2번째자리,3번째 자리 로 생각해 보면 2번째자리 1로 끝나기 위해서는 첫째자리 1,2 에서 가능하므로 2가지 2번째자리 2로 끝나기 위해서는 첫째자리 1,2,3 모두 가능하므로 3가지 경우 2번째 자리 3으로 끝나기 위해서는 첫째자리 2,3 에서 가능하므로 2가.. 정보/이산수학 2020.02.06