정지 문제란 무엇인가?처음 프로그래밍을 할 때, 누구나 한 번쯤은 프로그램을 작성한 후 예상치 않게 컴퓨터가 멈추거나, 프로그램이 끝없이 실행되는 상황을 경험했을 것입니다. 여러분이 고심 끝에 작성한 코드가 실행되길 기대했는데, 프로그램이 멈추지 않고 계속해서 실행된다면 어떤 기분이 들까요? 심지어 이 프로그램이 여러분의 컴퓨터 자원을 모두 소모해 다른 작업도 방해한다면 단순히 불편함을 넘어서, 시스템 성능에 큰 문제를 일으킬 수 있습니다. 그러므로 프로그램을 작성할 때, 프로그램이 주어진 입력값에 대해 반드시 종료 될지(정지 문제), 혹은 계속해서 실행 될지(무한 실행 문제)를 미리 판별하는 것이 매우 중요합니다. 프로그램의 정지 여부를 미리 판단할 수 있다면, 예상치 못한 오류를 줄이고, 시스템의 안..

여러분은 파티를 준비하고 있고, 초대할 손님 명단을 작성 중입니다. 파티가 즐겁게 진행되려면 몇 명을 초대해야 할까요? 여기서 핵심은 초대된 사람들 사이의 관계입니다. 모든 손님이 서로 잘 아는 사이라면 이야깃거리가 금방 고갈될 수 있습니다. 반대로, 모든 손님이 서로 모르는 사이라면 어색한 분위기가 형성될 수도 있죠. 따라서, 손님들 사이의 관계가 적당히 섞여 있는 것이 중요합니다. 그렇다면, 이 균형을 유지하면서도 파티가 흥미롭게 진행되려면 어떻게 해야할까요? 이런 질문을 던져봅시다. 적어도 3명이 서로 알거나, 3명이 서로 모르는 그룹이 생기도록 하려면 최소 몇 명의 손님을 초대해야 할까요? 파티 플래너 문제와 그래프앞서 본 문제를 파티 플래너 문제라고 부릅니다. 이 문제를 이해하기 위해서는 그래프..

임의의 자연수를 하나 가져옵니다. 짝수라면 2로 나누고 홀수라면 3을 곱하고 1을 더합니다. 만약 그 수가 1이 되면 멈추고, 아니라면 위 과정을 반복합니다. 이 과정을 반복하면 항상 마지막 수는 1이 나오게 됩니다. 컴퓨터로 2^68까지의 자연수를 확인해본 결과 성립했지만 아직 모든 자연수에 대해 성립하는지 증명은 되지 않았습니다. 한 번 도전해보시겠습니까? 콜라츠 추측(Collatz conjecture)은 1937년에 처음으로 이 추측을 제기한 로타르 콜라츠의 이름을 딴 것으로 3n+1 추측, 울람 추측, 혹은 헤일스톤(우박) 수열 등 여러 이름으로 불립니다. 생각을 바꾸어보면 1부터 출발해 콜라츠 추측의 역과정을 진행하며 수형도를 만들어보았을 때 모든 자연수가 나오는지 확인해보는 방법도 있습니다. ..

여기 만원이 들어 있는 투명한 상자 A와 불투명한 상자 B가 있습니다. 여러분들은 A, B 두 상자 모두 가져가거나 B상자만 가져갈 수 있습니다. 그런데 저는 여러분이 미래에 어떤 선택을 할지 정확히 알고있습니다. 여러분들이 미래에 두 상자 모두 가져간다면 전 B 상자를 비워두고 여러분이 B 상자만 가져간다면 전 B상자에 100만원을 넣어두겠습니다. 제가 돈을 넣을지 말지 선택하고 떠난 이후 여러분이 할 수 있는 최선의 선택은 무엇일까요? A,B 둘다 가져 가실건가요? 아니면 B만 가져가실 건가요? 선택하셨나요? 1 ) 상자 A, B를 모두 가져간다. 저는 이미 돈을 넣어두고 떠났기에 여러분이 선택을 할 때 B 상자에 들어있는 돈의 액수는 이미 정해져 있습니다. 다른 말로 여러분이 어떤 선택을 하든지에 ..

Sum 1/n^s는 수렴할까요? 아니면 발산할까요? P급수 판정법에 의해 s>1이면 급수는 수렴하고 s