본문 바로가기
반응형

프로그래밍495

집합 기호와 명제 기호 간의 상호번역 드모르간 법칙에 의한 상반개념 집합 언어와 명제 언어를 서로 번역해 보자 우리는 전체집합을 설정했을 때 A가 아닌 나머지 구역이라는 뜻에서 A의 여집합을 설정할 수 있다. 이때 우리는 A와 A의 여집합이 완전히 상반된 개념이라는 것을 알 수 있다. 여기까지만 보면 여집합이라는 개념은 집합 한 개에만 적용되는 연산이라고 생각할 수도 있지만, 사실 여집합의 성질을 일반화시킨 것이 바로 드모르간 법칙이다. 즉, 집합의 연산에서도 상반개념들을 찾을 수 있다는 것이다. 그렇다면 드모르간 법칙을 이용하면 어떻게 되느냐. A의 상반개념은 A의 여집합 합집합의 상반개념은 교집합 전제집합의 상반개념은 공집합 이런 식으로 집합에서 상반개념을 확립할 수 있게 된다. 단, 집합의 연산 중 차집합은 항상 저렇게 형태를 바꿔서 .. 2023. 9. 8.
논리적 추론에 들어가기 앞서 논리적 추론 용어 공리(Axiom) 공리는 증명없이 참으로 받아드리는 명제를 의미한다. 페아노 공리계의 1은 자연수이다. 유클리드 기하학에서 '두 점이 주어졌을 때, 두 점을 지나는 직선이 있다.' 라고 하는 명제들은 증명할 수 없기에 공리라고 부리고 있다. 정의(Definition) 정의와 공리는 비슷해보이지만 다른 것이다. 대체로 정의는 용어에 대한 약속을 정의로 묶는 경우가 많다. 예를 들면 세 변으로 만들어진 도형을 삼각형이라고 하거나, 삼각형 중 한 내각의 크기가 90도인 삼각형을 직각삼각형이라고 부른다. 언제나 참인 것이 특징이다. 정리(Theorem) 증명을 통해 참인 것으로 밝혀진 것을 의미한다. 증명이 있지 않다면 이는 추측(Conjecture)라고 부르고 있다. 대표적인 정리는 우리가 .. 2023. 9. 7.
[프로그래머스 Programmers] 하노이의 탑 문제 설명 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다. 한 번에 하나의 원판만 옮길 수 있습니다. 큰 원판이 작은 원판 위에 있어서는 안됩니다. 하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다. 1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로.. 2023. 9. 7.
[프로그래머스 Programmers] 분수의 덧셈 문제 설명 첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요. 제한사항 0 2023. 9. 6.
최대공약수와 유클리드 호제법 최대공약수(Greatest Common Factor, Greatest Common Divisor) 말 그대로 공약수 중에서 최대인 수이다. 예컨대, 18의 약수는 1,2,3,6,9,18이고 54의 약수는 1,2,3,6,9,18,27,54이다. 이때 18과 54의 공통인 약수, 즉 공약수는 1,2,3,6,9,18이다. 이 공약수 중에서 가장 큰 18이 최대공약수이다. 최대공약수는 분수를 약분할 때 필요하다. 분모와 분자를 나눌 때 0이 아니라고 모두 나눌 수 있는 것은 아니다. 분모와 분자의 공약수이어야만 나눌 수 있다. 결국, 약분이란 분수의 분모와 분자를 두 수의 공약수로 나누는 것이다. 이때 공약수는 최대 공약수를 포함하는 것이므로 약분은 공약수로 나누는 방법과 최대공약수로 나누는 방법이 있다. 공약.. 2023. 9. 6.
동적 계획법(Dynamic Programming, DP) 동적 계획법이란? 동적 계획법(DP, 다이내믹 프로그래밍)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두고 재활용한다가 핵심이다. 동적 계획법 사용 이유 일반적인 재귀(Native Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 피보나치수열은 아래와 같다. 1, 1, 2, 3, 5, 6, 13, 21, 34, 55, 89, 144... 피.. 2023. 9. 1.

티스토리툴바