정지 문제(Halting Problem) - 최고의 컴퓨터도 만들 수 없는 프로그램이 존재한다

1. 정지 문제(Halting problem) 프로그램을 만드는 사람이라면 누구나 이런 생각을 한다. "내가 만든 프로그램을 실행하면 정상적으로 종료될지, 무한 루프를 돌지, 실행하지 않고 아는 방법이 있을까?" 그러면 내가 짠 프로그램 D가 정상적으로 종료되는지, 무한 루프를 도는지 검사해주는 또 다른 프로그램 H를 만들면 되는거 아닌가? 그러한 프로그램 H가 존재한다고 가정해보자. H는 분석할 프로그램 D와 프로그램 D의 입력 I를 입력으로 받고, D가 정상적으로 종료하면 True 무한루프를 돌면 False를 유한 시간 내에 return하는 함수이다. 어떤 프로그램 P는 프로그램 H에 다음과 같이 물어본다."프로그램 D에 입력으로 프로그램 D를 주면 어떻게 되냐?" 만약 H가 정상적으로 종료된다라고 ..

• format_list_bulleted 컴퓨터과학(CS)
• · 2026. 7. 14.
• textsms

보이어 무어의 과반수 투표 알고리즘(Boyer-Moore Majority Vote Algorithm)

크기 n인 배열에 있는 원소들 중에서, 개수가 n//2 + 1개 이상인 원소가 하나 존재한다고 하자. 즉, 절반을 넘는 개수를 가진 원소가 무조건 하나가 있을때 이 원소를 찾고 싶다. 어떻게 찾을 수 있을까? 예를 들어 [2,2,1,3,2,2]에서 2는 개수가 4개있고 크기 6인 배열에서 이것이 과반수 이상의 원소이다. 가장 쉬운 방법은 O(N)으로 배열을 순회해서 각 원소의 개수를 모두 찾아 hash에 저장해둔다. 이 hash에서 가장 원소의 개수가 많은 원소를 찾으면 된다. 이러면 시간복잡도 O(N)에 공간복잡도 O(N)에 찾을 수 있다. class Solution: def majorityElement(self, nums: List[int]) -> int: h = {}..

• format_list_bulleted 컴퓨터과학(CS)
• · 2026. 6. 25.
• textsms

프로베니우스의 동전 문제(Frobenius coin problem)와 슈어의 정리(Schur's theorem)

1. 프로베니우스의 동전 문제(Frobenius coin problem) 서로 다른 두 동전 x원, y원이 있을때, 이 두 동전을 각각 적당한 개수를 사용하여, 만들 수 없는 금액중 가장 큰 값은? 이 문제의 정답을 프로베니우스의 수(Frobenius number)라고 부른다. 예를 들어 3원, 5원짜리 동전으로 만들 수 없는 가장 큰 금액은 7원이다. 이 말은 8원 이상의 금액은 무조건 만들 수 있다는 뜻이다. 주의할 점은 7원 밑의 금액 중에서 1,2,4원은 만들 수 없다는 것은 자명하다. 프로베니우스의 수는 x,y가 서로소(최대공약수가 1)일때만 존재한다. 이때, 프로베니우스의 수는 xy - x - y임이 알려져있다. 2. 일반화된 문제 일반적으로는, n개의 동전 $a_{1}, a_{2},...,..

• format_list_bulleted 정수론
• · 2026. 3. 30.
• textsms

어떤 정수의 밑을 2로 하는 로그값 $log_{2}x$을 정확하게 구하는 방법

어떤 정수 n이 주어졌을때, n보다 작거나 같으면서 가장 가까운 2의 거듭제곱이 필요할때가 있다 구체적으로 $2^{x} = n$을 만족하는 정수 x를 찾고 싶을 때가 있다. 제일 쉬운 방법은? import mathn = int(input())print(int(math.log2(n))) 근데 얘는 문제가 n이 엄청 크면 실수오차 발생으로 틀릴 수 있다는거 이를 피하는 방법은 2씩 직접 곱해서 찾는 방법이 있고 import mathn = int(input())x = 0v = 1while v n: break x += 1 print(x) 그런데 이 방법은 O(logN)이다. 메소드 중에 bit_length()라는 메소드가 있다 어떤 정수를 이진수로 표현할때 그 이..

• format_list_bulleted 알고리즘/비트마스킹
• · 2026. 3. 25.
• textsms

비트연산자 &와 논리연산자 and의 차이점(단축 평가)

1. 비교대상 비트연산은 왼쪽 오른쪽 정수들의 비트 단위별로 비교 > 5 & 3은 5 = 101이고 3 = 011이고 3개의 비트 각각을 비교해서 결론을 낸다. 1 & 0 = 0, 0 & 1 = 0, 1 & 1 = 1이므로 5 & 3 = 001 = 1이다. 논리연산은 불리언 값 True, False끼리 비교 > 5 and 3하면 5와 3은 컴퓨터에서 True로 인식하여 결과는 True가 된다 2. 단축평가 논리연산은 단축평가를 한다. 중간에 전체 결론이 확실하게 나면 그 뒤의 연산은 수행하지 않는다. 비트연산은 단축평가를 하지 않는다. 반드시 모든 비트 단위들을 비교한다. 예를 들어 5 and 0 and 3은 5 and 0 = 0이고 여기서 and 더 해봤자 무조건 0이므로 0 and 3을 평가하지 ..

• format_list_bulleted 컴퓨터과학(CS)
• · 2026. 1. 4.
• textsms

원형 큐(circular queue)와 큐(queue)의 차이점?

1. 큐(queue) 선형 자료구조 먼저 들어간 데이터가 먼저 나오는 자료구조(First In First Out) 큐에 자료를 넣는 것을 enqueue 큐에 자료를 빼는 것을 dequeue라고 부른다 front, rear 포인터가 무조건 뒤로만 이동하여, 앞부분의 데이터가 삭제되면 다시 삽입할 수 없다는 단점이 있다 front 포인터는 삭제할 위치 rear 포인터는 삽입할 위치 여기서 10을 넣으면 다시 20을 넣으면 다시 30을 넣으면 이제 10을 제거하면 다시 20을 제거하면 여기서 40을 넣으면... 앞에 들어가는게 아니고 뒤에 들어가는데 이렇게 앞에 공간이 비어있음에도 활용하지 못하는 단점이 있다 2. 원형 큐(circular queue) 큐의 끝과 시작을 연결한 ..

• format_list_bulleted 컴퓨터과학(CS)
• · 2026. 1. 3.
• textsms