ComDoc ComDoc

게임의 룰 단순한 룰의 게임을 하나 만들어 보겠습니다. 어디서 본 게임인데 이름을 모르겠네요. 막대기 게임이라고 해두죠. PS) 검색해 본 결과 이 게임은 NIM 게임 중 하나입니다. ex) 배스킨라빈스31 게임 2인용 게임입니다. 10개의 빈칸이 있습니다. 교대로 빈칸을 채웁니다. 한쪽부터 순서대로 차곡차곡 이어서 채워야 합니다. (=stack) 빈칸을 두는 것은 안됩니다. 한 번에 1에서 3개까지 채울 수 있습니다. 쉬는 것(0개)은 안됩니다. 마지막 칸을 채우는 사람이 이기는 겁니다. 코딩1 : 랜덤 말보다는 코드가 더 편한 것 같습니다. 알고리듬으로 처리해야 할 부분을 일단은 랜덤으로 두었습니다. from random import randint AI = True HUMAN = False class..

https://comdoc.tistory.com/entry/python-8-puzzle-problem-1-BFS-DFS 앞서 우리는 맹목적 탐색의 한계를 경험했으니 그에 대한 대안을 찾아보자. 8 퍼즐을 자주 해보면 본인만의 풀이법이 생긴다. 본인의 경우 고등학교 때 연예인 사진을 이용한 퍼즐 게임을 만든 적 있고.. 번호가 연결된 블록끼리 회전을 하면서 필요한 블록을 채우거나 필요 없는 블록을 빼는 방식으로 퍼즐을 풀었던 기억이 있다. 사전에서 heuristic(휴리스틱)을 찾아보면 '체험에서 (스스로 발견하는)'이라는 뜻을 가지고 있다. 이렇게 heuristic 한 방법을 사용하는 탐색법을 heuristic search method(경험적 탐색법)라고 한다. 위키 백과에는 다음과 같이 설명되어 있다,..

[파이썬] 8-퍼즐 문제 다음 그림과 같이 8개의 숫자와 빈칸을 이용해 숫자를 정렬하는 퍼즐을 말한다. 위 그림과는 달리 아래 모양으로 정렬하도록 하겠다. 빈칸은 0으로 표기. 1 2 3 4 5 6 7 8 0 맹목적 탐색법의 대표적인 두 가지 방법으로 맹목적 탐색의 문제점을 알아본다. (1) 너비 우선 탐색(BFS, Breadth-first search) 너비 우선 탐색: comdoc.tistory.com/entry/24-graph-width-first-search 최단 경로 찾기: comdoc.tistory.com/entry/25-그래프-최단-경로-찾기 비교적 잘 작동하는 코드지만, 탐색이 길어지면 에러가 발생한다. (본인의 PC에서는) marked의 원소가 181440개를 초과되면 에러가 발생한다. ..

제 블로그에서 가장 인기 있는 글이 해시더군요. 해시가 나온 김에 간단한 블록체인을 만들어 보겠습니다. '블록체인의 의미', '블록체인이 어떻게 데이터의 보안을 유지하나' 까지만 이해할 수 있게 아주 가볍게 만들어 보겠습니다. (네트워킹 쪽은 pass) 블록체인이 암호화폐에서만 쓰이는 게 아니라 유통 과정을 기록하는 등에도 사용되니까 위 두 개념만 알아도 꽤 써먹을 데가 많습니다. 선수학습: 해시 파이썬 해시 라이브러리 import hashlib h = hashlib.sha256() h.update(b'Genesis') print(h.hexdigest()) 81ddc8d248b2dccdd3fdd5e84f0cad62b08f2d10b57f9a831c13451e5c5c80a5 파이썬 해시 라이브러리의 사용법을..

폰 노이만 선생님이 만드신 합병 정렬. 퀵 소트와 같이 분할 정복 알고리듬을 사용합니다. 퀵 소트와는 달리 안정 정렬입니다. 안경잡이 개발자님이 설명을 잘해주셨네요. 좋아요 한번 누르고 나왔습니다. https://blog.naver.com/ndb796/221227934987 설명대로 코딩해 보았습니다. # merge sort 2020-10-12 # https://comdoc.tistory.com def merge_sort(nums): if len(nums) < 2: return nums center = len(nums) // 2 left, right = nums[:center], nums[center:] return merge(merge_sort(left), merge_sort(right)) def me..

호어 선생님이 만드신 빠른 정렬~! 분할 정복 알고리듬을 이용합니다. (머지 소트도 분할 정복이죠.) 불안정 정렬입니다. ([A1, A2]를 'A를 기준'으로 '숫자를 무시'하고 정렬했을 때 A1, A2의 순서가 바뀔 수 있습니다.) [A, B, A, C, A]를 정렬하면 [A, A, A, B, C]가 되는데.. A, A, A 간 순서가 어떻게 되든 무슨 상관이냐 라고 생각할 수 있는데.. [A1, B2, A2, C1, A3]의 경우 두 번째 숫자를 기준으로 정렬한 뒤, [A1, C1, B2, A2, A3]를 첫 번째 문자를 기준으로 한 번 더 정렬해서, [A1, A2, A3, B2, C1]를 만들어야 할 경우도 있습니다. (스프레드 시트 작업에서 많이 씁니다. ) 불안정 정렬로는 이런 작업이 어렵습니다..

더보기 대칭키 암호화 일반적으로 암호라고 하면 떠올리는 방식입니다. 암호문을 생성할 때, 복원할 때 같은 키를 사용합니다. 난수표나 시저 암호도 대칭키 암호화죠. 장점은 단순하기 때문에 빠르다는 것. 단점은 빠르다는 것 외에는 모두 다입니다. 보내는 사람 받는 사람이 같은 키를 가지고 있기 때문에 분실에 취약하다는 점이 있습니다. 2명이 가지고 있으면 사고 날 확률도 2배... 대칭키는 비밀을 유지하기 위해서 개인별 암호가 필요합니다. (여러 명의 스파이에게서 보고를 받을 때... 스파이마다 암호가 달라야 스파이 사이에도 비밀이 유지됩니다.) 암호 관리가 힘듭니다. 문서에 대한 인증이 필요할 때 공인 인증 기관이 필요합니다. 이런 단점을 극복하고자 공개키 암호화가 나왔습니다. 공개키 암호화 수학적인 쌍을..

몬테카를로 방법(Monte Carlo Method): 무작위수와 모의 실험을 통해 문제를 해석, 해결. ---------- 위 그림에서 원의 반지름을 r 이라고 하면, 원의 면적은 pi * r ** 2 (파이 * r의 제곱)입니다. 정사각형(한 변이 2 * r)의 넓이는 (2 * r) ** 2입니다. 위 '정사각형'에 랜덤으로 점을 찍을 때 '원의 중심과의 거리가 r 이하인 점'의 확률은 '(원의 면적) / (정사각형의 면적)' 입니다. 이것을 이용해서 원주율(pi)를 구할 수 있습니다. 정사각형에 랜덤으로 점을 찍을 때, 내접하는 원의 중심과의 거리가 r 이하인 점의 확률 = (원의 면적) / (정사각형의 면적) = (pi * (r ** 2)) / ((2 * r) ** 2) = (pi * (r ** 2..