외판원 순회 문제 (Traveling Salesman Problem)는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 외판원 문제는 다음과 같이 설명할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다. 라는 문제에서 시작됩니다.
TSP Art Generator 를 사용하면 이 세상에 모든 길을 한 획으로 연결합니다. 그래서 어디에 사용되느냐… 방문지를 모두 찾아내기도 하지만 모두 선으로 연결하기도 합니다.
하여간 그런걸 뭐에 쓰느냐?
이거 알고보면 한 선입니다.
전체화면으로 놓고 눈으로만 따라가보세요 노안훈련용 #노안 #훈련 #집중력 #미로찾기
이제 본격적으로 외국인들 대상의 퍼즐을 만들고 있습니다. 이 전에도 만든다고 했지만… 일단 초등1~2학년 필수단어를 초성으로만 연결하는 게임인데 8방향으로 움직입니다.
찾을 단어 목록도 나오고 그 단어를 기준으로 8방향으로 움직여서 주변의 글자를 매칭하는 게임입니다. 그러니까 생각보다 장치를 많이 마련해야하고 데이터를 엄청나게 정리하고는 있지만 일단 종이랑 연필로도 풀 수 있게 만들고는 있는데 약간의 시간은 걸릴거 같습니다.
기존 사이트를 버리고 이런거나 다 모아보겠습니다.
계속 만들고 있던 미로찾기의 다음 단계가 한 선 다음은 페어 미로찾기입니다. 보통 미로찾기는 입구와 출구를 찾는 게임인데.
약간 다른 생각을 해봤습니다.
미로로 컬러링을 하는 새로운 컬러링 미로찾기 2페어 컬러링을 생각합니다. 많은 미로의 색상 미로가 되게 만들면 길이 컬러링의 결과가 됩니다. 모두 채워야만 가능하다면?
미로의 빈 공간이 없는 다른 장르가 됩니다.
미로찾기의 빈 공간을 다 채우는 미로찾기가 될테니까 아주 복잡하고 큰 그림도 그릴 수 있게 됩니다.
네모네모로직 같은 것도 가능은 하겠지만 일단 10가지 색상으로 진행할 수 있게 공간이 하나도 비워지지 않도록 작업하는데 머리 터지겠네요.
새로운 퍼즐, 미로 등등은 새로운 변형이 가능합니다. 대신 만드는 사람 머리를 많이 혹사해야 합니다. 정답이 무조건 하나가 되게 만들어야 하니까 가끔 아닌 문제를 만들면 많이 괴롭습니다.
슬슬 문제를 뽑아내기는 할텐데 이제 서브스크립션 같은걸 해볼까 합니다. 머리쓰는 과정과 문제도 아이들이 풀어보면 어떨까요? 새로운 퍼즐 제작에도 참여하고…
아~ 어른도 됩니다. ^^
어른템풀이니까…
한동안 고민하고 준비하던게 한글, 전세계 언어입니다. 그림으로 인식되는 언어의 모양이 워낙 많으니 이제 그걸 놀이로 기억하기 쉬운 내용을 담은 컨텐츠로 만들어볼 생각을 하고 있었는데 7학년 워크북이랑
한국어 배우려는 외국인에게 한글 퍼즐이나… 글자나오는 미로찾기를 만들었던 것을 새로운 작업에 맞춰 개발중이었습니다. 그런데 LLM으로 글자가 나오는 프로그램을 만들다가 생각보다 잘 못만들어서 사람만 못하다 라는 생각을 ?!?
하여간 MCP로 만들 수 있긴 한데 만드는데 계속 돈이 들어가서 인간이 조금씩 관여하는 방식으로 바꿨습니다. 아 눈아파…
하여간 새로운 시장으로 갑니다~ 그리고 온라인에서 동일한게 가능한 웹, 앱 등등을 다 만들고 기다리고 있어요. 힘들다 ㅠㅠ
4방향 미로찾기
수학의 쓸모 라는 글을 쓰면서 샘플로 만든 A* 알고리즘
사각형이라 쇼츠영상으로 올라갔는데 조회수가 5000대가 됐습니다. 사실 이런게 뭐 대단한 퍼즐도 아니고 집중력을 요하기는 하지만 완성도도 떨어지는데… 보시는 분이 있습니다.
알고리즘이 불러온거겠죠? 정말 대충올렸는데 신나네요…
그래서 이런것도 만들어봤습니다.
자수기 즉 CNC같은 기계와 연결할 수 있는 프로그램에서 한 줄로 모양을 만드는 과정을 만들어봤습니다.
시작하면 이 면적을 자동으로 채우고 그 다음에 어떤 위치에 바늘이 들어와야 하는지 뭐 그런걸 해야 와펜으로 예쁘게 만들 수 있겠죠? 대각선으로 만들거나 장비의 형태에 따라서 처리하는 방법이 다릅니다. 제가 2년째 하고 있는 일이 바로 기계용 폰트를 만드는거예요.
그 에디터를 열심히 만들고 있기는 한데 일단 이런 간단한 프로그램을 하고있습니다.
온라인으로 와펜을 만들 수 있는 것도 생각하고 있습니다. 브로더 1000만원짜리 장비사서 한 두번 샘플로 뭐 만들고 몇년 놀리다 팔아버린거 생각하면 그동안 뭐했나 라는 생각이…
미로 찾기 A* 알고리즘과 그 제자들의 활용법
항상 사람들이 이야기하는 건 그래서 수학이 뭐에 쓰이는 건데? 실생활에서는 계산만 잘하면 되는 거 아냐?라고 합니다. 그런데 잘 생각해 보면 수학은 의외로 많은 실생활에 쓰이고 있습니다. 1/n 술자리, 데이트 앱에서도 심리학에서도 말이죠~ 다만 그렇게 생각하느냐 그냥 넘어가느냐에 따라 이 세상이 달리 보입니다.
그래서 수학이 뭐에 쓰이는 건데 이제 아주 간단한 이야기부터 해볼 생각입니다. 현실에서 장난감도 세탁기도 청소기도 모두 디지탈화가 되면서 어떻게 움직이 그 원리는 무엇인지 그리고 그 생각의 끝에는 수학의 원리가 들어있다는 것을 찾아가는 과정을 수학식이 아닌 그냥 간단한 유틸리티나 퍼즐로 만들어볼 생각입니다.
A* 알고리즘(A* algorithm 에이 스타 알고리즘[*])은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프 탐색 알고리즘 중 하나입니다.
그래서 만들어본 게 한눈에 모서리에 누가 빨리 도달하는지를 찾는 간단한 퍼즐을 만들어봤습니다. 가운데서 탈출하는 것인데 가장 짧은 거리에서 탈출은 누가 할 것인지 같은 미로 찾기라기보다 판단력게임입니다. 최상단으로 탈출하려면 더 많은 길을 가야겠죠?
농담입니다. 출판사 창고에 있는 책을 빨리 찾아서 다음 창고로 가져다줘야 하는데 그걸 잘 모르는 로봇이 한 번에 많이 책을 수거해서 가져다준다면? 당연히 최단 경로에서 다 모은 다음에 집하하는 게 더 낫겠죠 한대면 모르겠지만 협력이 가능하다면 그런 걸 생각하고 있습니다. 창고선진화 하려면 퍼즐을 잘해야?
� 게임 캐릭터 길 찾기 (Pathfinding): 이게 아마 A* 알고리즘이 가장 유명하게 쓰이는 곳일 거예요!
게임 캐릭터(NPC)가 맵 안에서 이동하거나, 플레이어를 추격하거나, 특정 목표 지점까지 알아서 찾아갈 때, A*가 가장 효율적인 경로를 계산해 줍니다.
스타크래프트 같은 전략 시뮬레이션 게임에서 유닛들이 장애물을 피해 이동하거나, RPG 게임에서 몬스터가 플레이어를 따라올 때 등등! 게임에서 캐릭터가 똑똑하게 움직이는 뒤에는 A* 또는 그 변형 알고리즘이 있는 경우가 많아요. 복잡한 지형에서도 길을 잘 찾게 해 줍니다.
� 로봇/자율 주행 내비게이션:
공장이나 창고를 돌아다니는 로봇, 자율 주행 자동차 등이 주변 장애물을 피해 목표 지점까지 안전하고 빠르게 이동해야 할 때 A* 알고리즘이 활용됩니다.
청소 로봇이 집 안 구조를 파악하고 구석구석 청소 경로를 짤 때도 비슷한 원리가 사용될 수 있습니다.
�️ 지도 앱 / 내비게이션 시스템:
우리가 스마트폰 지도 앱이나 차량 내비게이션에서 ‘최단 경로’, ‘추천 경로’ 등을 검색하잖아요? A* 알고리즘 자체 또는 A의 아이디어를 바탕으로 발전된 알고리즘들이 출발지부터 목적지까지의 도로망에서 가장 효율적인 경로를 계산해 주는 데 사용됩니다. A의 ‘미래 예측(휴리스틱)’ 개념이 여기서 빛을 발하죠!
� 물류 배송 최적화:
택배 회사나 배달 서비스에서 여러 배송지를 거쳐 최종 목적지까지 가는 가장 효율적인 순서와 경로를 결정할 때 응용될 수 있습니다. (이건 ‘외판원 문제’와도 관련 있지만, A*는 여러 지점을 효율적으로 지나는 경로 탐색의 기초가 됩니다.)
� 인공지능 및 문제 해결:
로봇 팔이 여러 단계를 거쳐 조립 작업을 수행하거나, 특정 복잡한 퍼즐 게임(예: 15-퍼즐, 루빅스 큐브 상태 탐색 등)에서 목표 상태까지 가는 최소한의 단계를 찾을 때 A* 알고리즘이 상태 공간 탐색에 활용되기도 합니다.
요약하자면, A* 알고리즘은 “어떤 목표까지 가장 빠르거나 효율적인 길을 찾아야 하는” 거의 모든 분야에서 직간접적으로 사용될 수 있는, 아주 실용적이고 강력한 알고리즘이라고 할 수 있습니다! �
A* 알고리즘의 “과거 비용 + 미래 추정”이라는 핵심 아이디어가 워낙 강력하고 유용하다 보니, 다양한 상황과 요구사항에 맞춰 A*를 개선하거나 변형한 알고리즘들이 많이 파생되었습니다.
몇 가지 대표적인 파생 또는 관련 알고리즘들은 다음과 같습니다.
IDA* (Iterative Deepening A*):
문제점 해결: 오리지널 A*는 탐색 공간이 넓으면 메모리 사용량이 폭발적으로 늘어나는 문제가 있습니다.
해결 방식: IDA*는 정해진 비용 한계(threshold) 내에서만 깊이 우선 탐색(DFS)을 수행하고, 목표를 찾지 못하면 한계를 점차 늘려가며 탐색을 반복합니다. A*처럼 f(x)=g(x)+h(x) 값을 활용하지만, 메모리를 훨씬 적게 사용합니다. 메모리가 매우 제한적인 환경에서 유용합니다.
D* (Dynamic A*) 및 LPA* (Lifelong Planning A*):
문제점 해결: A*는 탐색 환경(예: 지도상의 장애물, 길의 비용)이 고정되어 있을 때 최적이지만, 환경이 실시간으로 변하거나 새로운 정보가 계속 들어올 때는 비효율적입니다. 환경이 변할 때마다 처음부터 다시 계산해야 하니까요.
해결 방식: D*나 LPA* 같은 알고리즘들은 환경이 변했을 때 변경된 부분만 효율적으로 업데이트하여 새로운 최적 경로를 빠르게 찾아냅니다. 로봇 내비게이션처럼 동적으로 변하는 환경에서 경로 계획에 많이 사용됩니다. D*는 초기 버전이고, LPA*가 이를 개선한 형태입니다.
Weighted A*:
목표 변경: 때로는 ‘가장 짧은’ 최적 경로보다 ‘빨리 계산되는’ 경로가 더 중요할 때가 있습니다.
해결 방식: Weighted A*는 f(x)=g(x)+w⋅h(x)와 같이 휴리스틱 h(x)에 가중치(w>1)를 줍니다. 이렇게 하면 미래 추정을 더 중요하게 여기게 되어 탐색하는 노드의 수가 줄어들어 계산 속도는 빨라지지만, 찾은 경로가 최적 경로가 아닐 수도 있습니다 (완벽하게 가장 짧은 길은 포기할 수 있습니다).
Bidirectional A*:
해결 방식: 출발지에서 목표지로 가는 탐색과 목표지에서 출발지로 거슬러오는 탐색을 동시에 진행해서, 중간에서 만나는 지점을 찾는 방식입니다. 탐색 공간을 줄여 탐색 속도를 높이는 데 효과적일 수 있습니다.
A*와 관련 깊은 다른 알고리즘들 (파생은 아니지만 비교 대상):
다익스트라 알고리즘 (Dijkstra’s Algorithm): A*의 휴리스틱(h(x))이 없는 경우(h(x)=0)와 같습니다. ‘과거 비용'(g(x))만 보고 탐색하며, 항상 최적 경로를 찾지만 A*처럼 ‘목표 방향’에 대한 정보가 없어 비효율적일 수 있습니다.
욕심쟁이 최우선 탐색 (Greedy Best-First Search): A*의 ‘과거 비용'(g(x))이 없는 경우(g(x)=0 또는 무시)와 같습니다. 오직 ‘미래 추정'(h(x))만 보고 가장 좋아 보이는 곳으로만 가는 탐색입니다. 계산은 빠를 수 있지만, 최적 경로를 보장하지 못하며 잘못된 길로 빠질 위험도 있습니다.
이처럼 A* 알고리즘은 기본적인 강력함 위에 다양한 문제 상황에 대처하기 위한 여러 변형 알고리즘들을 낳았고, 덕분에 게임, 로봇, 내비게이션 등 여러 분야에서 더욱 폭넓게 활용될 수 있게 되었답니다! �
https://product.kyobobook.co.kr/detail/S000212754141
제가 스도쿠, 매직아이, 다양한 퍼즐 개발자로 유명하지만 그래도 수학책은 써본적이 있긴합니다 3==3=333