2번에서 "공간을 소비해야 하는" 것은 hash table을 이야기하는 것 같은데, 그냥 간단하게 각각의 bucket에 linked list를 달아놓으면 bucket 갯수만큼 (혹은 그 이상) 원소가 들어있어도 별 문제없이 테이블을 사용할 수 있습니다. (물론 이건 하나의 예일 뿐이고 다른 방식의 hash table도 얼마든지 가능합니다만...)
그러니까 그냥 "메모리를 몇 % 더 사용할 것인가"와 "linked list를 평균적으로 얼마나 짧게 만들어서 최대한 빨리 원소를 찾을 것인가" 사이에서 절충해야 하는 문제인데, 거의 모든 경우 라이브러리에서 제공하는 디폴트 설정을 사용하시면 그냥 됩니다. 이게 문제가 될 정도로 메모리 사용량을 튜닝해야 하는 경우는 진짜 특수한 상황이고 평소에 거의 일어나지 않습니다.
실제 써먹는 용도라기보다 그냥 이론적으로 궁금하신 거면 Data Structure에 대한 괜찮은 교재를 찾아서 hash table 부분을 열심히 읽어보시면 됩니다.
알고리즘이 부족해서 공부를 하고 있는 중입니다. 알고리즘과 프로그래밍에 대한 부분은 다음 댓글로 쓰겠습니다.
>4. 주어진 명제의 크기를 비교하는 문제에서 A > B, B > C, C > A ... 이와 같이 체크를 한다면 사용자가 체
>크한 문제가 모두 거짓이 되는데, 어떻게 하면 이것이 진실인지 거짓인지 판별할 수 있는지 궁금합니다.
집합론 (Set theory) 앞 부분에 문장이나 조건의 참 (True)과 거짓 (False)을 결정하는 방법이 있습니다. 공리 (Axiom) 몇개 정의하고, 이것들을 바탕으로 복잡한 상태나 조건 (집합)의 참과 거짓을 판단하는 규칙들을 만들어요. 이런 규칙들에 AND, OR, 기타 논리 연산들도 들어갑니다.
위 문제를 조건과 결론으로 나누면 아래 세 문장입니다.
1) A > B: A가 B보다 크다
2) B > C: B가 C보다 크다
3) C > A: C가 A보다 크다
1)과 2)는 조건, 3)은 결론
1)과 2)에 따르면
A가 B보다 크고, B가 C보다 크니, A > C가 됩니다.
그런데 3)에서 C가 A보다 크다고 했으니, 조건 1)과 2)가 틀리거나 결론 3)이 거짓이 됩니다.
1)과 2)가 틀리려면 연산자 > (~보다 크다)가 거짓이여야 하는데, 그럴려면 집합론에서 이 연산자 >를 정의하기 위해 쓴 공리 중 하나가 거짓임을 증명해야 됩니다.
집합론 테두리 안에서 위 문제의 결론은 거짓입니다. 왜냐면 1)과 2) 조건에 따르면 결론은 A > C 로, C가 A보다 작습니다.
반대로 < (~보다 작다) 연산자를 쓴 문제 A < B, B < C, C < A는 참입니다.
만일 1)과 2)가 OR (또는) 관계라면 3)가 참인지 거짓인지 논리적으로 판단을 못합니다.
A가 B보다 클수도 있거나 B가 C보다 큰 조건이면
A가 B보다 크지만 B가 C보다 작을 수도 있습니다.
...
다른 건 잘 모르겠고...
2번에서 "공간을 소비해야 하는" 것은 hash table을 이야기하는 것 같은데, 그냥 간단하게 각각의 bucket에 linked list를 달아놓으면 bucket 갯수만큼 (혹은 그 이상) 원소가 들어있어도 별 문제없이 테이블을 사용할 수 있습니다. (물론 이건 하나의 예일 뿐이고 다른 방식의 hash table도 얼마든지 가능합니다만...)
그러니까 그냥 "메모리를 몇 % 더 사용할 것인가"와 "linked list를 평균적으로 얼마나 짧게 만들어서 최대한 빨리 원소를 찾을 것인가" 사이에서 절충해야 하는 문제인데, 거의 모든 경우 라이브러리에서 제공하는 디폴트 설정을 사용하시면 그냥 됩니다. 이게 문제가 될 정도로 메모리 사용량을 튜닝해야 하는 경우는 진짜 특수한 상황이고 평소에 거의 일어나지 않습니다.
실제 써먹는 용도라기보다 그냥 이론적으로 궁금하신 거면 Data Structure에 대한 괜찮은 교재를 찾아서 hash table 부분을 열심히 읽어보시면 됩니다.
...
답변감사합니다.
3번은 앙케이트 내용을 변경하는 방식이 있다는건 알고 있습니다.
예를들어서
1번에 "당신은 어떤 디저트를 가장 좋아합니까?"라는 질문을 넣고..
한 18번쯤에 "당신이 제일 선호하는 디저트는 무엇입니까?"라는 식으로 질문을 넣는 방식입니다.
성실하게 앙케이트에 응한다면 이러한 질문은 서로 같은 답을 고르게 되어 있구요.
무언가 선호하는 항목과 그러지 않은 항목의 보기를 동일하게 했는데, 이 둘의 선택이 동일하다면 성실하게 응했다 볼 수 없겠지요?
이러한 질문을 복수개 넣어 신뢰도를 산출하는 방식이 있습니다.
...
답변감사합니다.
재미 있는 주제를 공부하고 계시는군요. 2번은
재미 있는 주제를 공부하고 계시는군요.
2번은
비교 대상이 있어야 대답을 해 드릴 수 있을것 같습니다.
추가로, 해쉬도 데이터의 모양 및 수에 따라 사용할 수 있는 해쉬의 구현 방법이 다양합니다.
4번은..
명제에 거짓이 있는지를 찾는 방법이 아니긴 하지만
주어진 명제에 맞는 입력값을 찾는 라이브러리는 있습니다.
https://github.com/Z3Prover/z3
"입력값을 못찾으면 명제에 거짓이 있을 수도 있다." 정도는 추론을 할 수 있지 않을까요?
답변 감사합니다!
답변 감사합니다!
...
웬만하면 일단 답이 달린 질문은 지우지 않으시는 게 좋아요. 답을 달아준 사람들이 싫어합니다.
==========
제가 요즘 계속 고민하고 있는 문제 중 하나인데
이 분야에 대해 깊게 공부하지 못해서 조언이 필요합니다.
1. 다이나믹 프로그래밍을 연습하고 있는데 어떻게 해야할 지 감이 안잡힙니다. 점화식을 세우는 것이 어렵습니다. 이럴 경우에 이론적인 접근이나, 수학적 지식을 키우기 위해 수학 공부를 해야하는지 아니면 계속 DP문제들을 풀어보면서 방법을 찾는 것이 맞는지 궁금합니다.
2. 해쉬코드를 사용하는 이유가 빠른 검색을 하기 위해서지만, 대신 공간을 소비해야하는 것으로 알고 있습니다. 이 때 어떤 방법을 사용하면 공간 소비를 획기적으로 줄일 수 있다고 하는데 잘 모르겠습니다.
3. 메일로 사용자에게 설문조사를 보내는데 사용자들이 설문조사를 열심히 할 수도 있지만, 대충 할 수도 있어서,
이 설문조사 결과가 진실인지 거짓인지 판별하는 알고리즘이 있다고 들었습니다.
4. 주어진 명제의 크기를 비교하는 문제에서 A > B, B > C, C > A ... 이와 같이 체크를 한다면 사용자가 체크한 문제가 모두 거짓이 되는데, 어떻게 하면 이것이 진실인지 거짓인지 판별할 수 있는지 궁금합니다.
이것은 어떤 분야고, 어떤 책을 보면 공부할 수 있다 라는 짤막한 내용도 좋습니다.
어떤 형태로든 이 질문에 대해 한 수 가르쳐 주시면 감사히 받아들이겠습니다.
==========
알고리즘이 부족해서 공부를 하고 있는 중입니다.
알고리즘이 부족해서 공부를 하고 있는 중입니다. 알고리즘과 프로그래밍에 대한 부분은 다음 댓글로 쓰겠습니다.
>4. 주어진 명제의 크기를 비교하는 문제에서 A > B, B > C, C > A ... 이와 같이 체크를 한다면 사용자가 체
>크한 문제가 모두 거짓이 되는데, 어떻게 하면 이것이 진실인지 거짓인지 판별할 수 있는지 궁금합니다.
집합론 (Set theory) 앞 부분에 문장이나 조건의 참 (True)과 거짓 (False)을 결정하는 방법이 있습니다. 공리 (Axiom) 몇개 정의하고, 이것들을 바탕으로 복잡한 상태나 조건 (집합)의 참과 거짓을 판단하는 규칙들을 만들어요. 이런 규칙들에 AND, OR, 기타 논리 연산들도 들어갑니다.
위 문제를 조건과 결론으로 나누면 아래 세 문장입니다.
1) A > B: A가 B보다 크다
2) B > C: B가 C보다 크다
3) C > A: C가 A보다 크다
1)과 2)는 조건, 3)은 결론
1)과 2)에 따르면
A가 B보다 크고, B가 C보다 크니, A > C가 됩니다.
그런데 3)에서 C가 A보다 크다고 했으니, 조건 1)과 2)가 틀리거나 결론 3)이 거짓이 됩니다.
1)과 2)가 틀리려면 연산자 > (~보다 크다)가 거짓이여야 하는데, 그럴려면 집합론에서 이 연산자 >를 정의하기 위해 쓴 공리 중 하나가 거짓임을 증명해야 됩니다.
집합론 테두리 안에서 위 문제의 결론은 거짓입니다. 왜냐면 1)과 2) 조건에 따르면 결론은 A > C 로, C가 A보다 작습니다.
반대로 < (~보다 작다) 연산자를 쓴 문제 A < B, B < C, C < A는 참입니다.
만일 1)과 2)가 OR (또는) 관계라면 3)가 참인지 거짓인지 논리적으로 판단을 못합니다.
A가 B보다 클수도 있거나 B가 C보다 큰 조건이면
A가 B보다 크지만 B가 C보다 작을 수도 있습니다.
Devuan 1.0 (Debian without systemd)
amd64 station: AMD FX(tm)-6100 Six-Core Processor, 8 GB memory, 1 TB HDD
amd64 laptop: HP Touchsmart
글쇠판: 세벌 최종식, 콜맥 (Colemak)
댓글 달기