안 쓰던 블로그

완전 탐색이란? 번호 자물쇠를 푸는 가장 단순한 방법이 무엇일까요? 바로 모든 경우의 수를 넣어보는 것입니다. 아주 간단한 원리지만 자릿수가 늘어날 때마다 경우의 수는 기하급수적으로 많아지기 때문에 평범한 사람의 머리로는 빠르게 풀어내지 못합니다. 하지만 컴퓨터는 가능합니다. 컴퓨터의 빠른 계산 능력을 이용하여 모든 경우의 수를 전부 탐색하는 방법, 바로 완전 탐색 입니다. 완전탐색은 답을 무조건 찾아낼 수 있지만 시간이 최고로 많이 듭니다. 시간이 많이 들면 시간 제한이 문제가 됩니다. 모든 문제는 위와 같이 시간과 메모리 제한이 주어지는데, 그렇기 때문에 완전 탐색을 하더라도 시간 제한 안에 풀 수 있는 적은 탐색 범위가 주어졌을 때 사용 가능한 알고리즘입니다. 완전 탐색의 종류 완전 탐색에는 어떤 ..

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/..

깊이 우선 탐색 = DFS트리의 순회와 같이 모든 정점들을 순서에 따라 방문하는 알고리즘을 탐색 알고리즘이라 합니다. 탐색 중에 가장 널리 쓰는 것이 깊이 / 너비 우선 탐색입니다. 일단 깊이 우선 탐색부터 하겠습니다. DFS는 한 마디로 >현재 정점과 인접한 간선을 보고 안 간 곳을 따라가다 갈 곳이 없으면 돌아가는 탐색< 입니다. 동작 과정은 이러합니다.이런 그래프가 있을 때 a-b-f-h 로 들어가고 h에서 b로 가야 되는데 이미 방문한 노드라 무시되고 f로 돌아갑니다.g-f-b-c-d-c-e까지 하고 e에서 a로 가야 되는데 역시 방문한 노드라 무시됩니다. c-b-a 순으로 돌아가면 탐색이 끝납니다. 코드는 재귀함수로 간단히 할 수 있습니다. chk배열은 정점을 방문했는지 체크하는 배열map배열이..

그래프 개념큐와 스택은 대개 선형으로 구성된 자료를 프로그램으로 표현하기 위해 고안되었고, 앞 발표에서 다룬 트리는 선형으로 표현하기 힘든 구조인 계층 구조를 표현하기 위해 고안된 자료 구조입니다. 그러나 그래프는 부모 자식 관계에 제약이 없기 때문에 좀 더 일반적이고 현실 세계의 문제를 푸는 데 유용하게 사용됩니다. 현실 세계의 문제는 보통 도로망, 사람 관계, 웹사이트 링크 관계 등등이 있습니다. 그래프 정의>어떤 자료나 개념을 표현하는 정점들의 집합과 정점을 연결하는 간선들의 집합으로 구성된 자료 구조무방향 그래프간선에 방향성이 없다화살표가 없는 간선들로 이루어져 있으며 순서가 없다 커플 >방향 그래프각 간선에 방향이 있는 그래프 짝사랑, 일방 통행 도로 >루프 그래프한 노드에서 출발한 간선이 다시..

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로 얇은 ..