정지 문제(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

비트연산자 &와 논리연산자 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

머신러닝과 컴퓨터의 문제 해결 방법 차이

1. 머신러닝의 정체? 개와 고양이가 뒤섞인 사진이 주어진 상태가 initial state이고 개와 고양이 사진을 완벽하게 분류한 상황이 바라는 terminal state 머신러닝 모델은 개와 고양이가 뒤섞인 사진을 받아 완전히 분류된 상태로 만들어주는 problem solving을 위한 도구    2. 컴퓨터의 deductive process 컴퓨터는 모든 가능한 조합을 고려하여 순간 최적인것이 나오면 update를 하고 다시 조합을 고려하는 것을 반복함 순간 순간에서는 최적을 고려했다고 하더라도 반드시 정답이라는 보장은 없지만 모든 경우를 다 고려한 최종 결과에서는 반드시 optimal한 결과 이 과정은 생각해보면 유한 상태 기계인 deterministic finite automata로 나타낼 수 있..

• format_list_bulleted 컴퓨터과학(CS)
• · 2024. 11. 19.
• textsms

컴퓨터과학에서 말하는 problem

1. definition problem이란 최종적으로 바라는 것과 현재 인식하는 것의 차이 machine learning 문제에서는 target과 prediction의 차이는 loss로 주어지고 이것이 문제 problem이다. loss를 0으로 보내려고하는 것이 problem solving이고 보낼 때 사용한 수단이 solution 2. example $x^{2} + 2x + 1 = 0$으로부터 x가 얼마인지 구하려는 문제가 주어졌다면 현재 인식하고 있는 상태인 $x^{2} + 2x + 1 = 0$이 initial state 최종적으로 구하고자하는 x=-1이 terminal state initial state와 terminal state의 차이가 problem initial state부터 한 단계, 한 ..

• format_list_bulleted 컴퓨터과학(CS)
• · 2024. 11. 12.
• textsms