Somnipathy

한컴 한글은 거의 안써서 잘 모르겠는데, MS Word 프로그램을 사용하여 문서를 작성하다보면 은근히 짜증나는 경우가 많다.

예를 들어, 의미없는 'dksfl'라는 영어를 쓰고싶다고 하자. Word에서 저 단어를 타이핑하면 띄어쓰기를 하자마자 '안리'로 자동고침을 한다.

자동으로 바뀔 때 마다 일일이 새로 타이핑하기도 귀찮고, 매우 짜증난다. 이 외에도, 일부러 대소문자를 틀리게 쓰는 경우 The -> tHE 같은 것도 자동으로 교정해주고, monday 같이 요일을 나타내는 단어는 Monday로 맨 앞 글자를 자동으로 대문자로 만들어버린다.

물론 교정해주는게 좋을 수도 있지만 귀찮을 때가 더 많다. 교정을 해주지 않더라도 이미 충분히 신경을 쓰고 타이핑하기때문에..

자동 고침을 막으려면 다음의 방법들이 있다.

• Word의 설정을 바꾸는 방법
• 상단에 [도구] 메뉴가 있는 구버전의 경우 [도구] 메뉴안에 '자동고침옵션' 에서 수정가능하다.
• 상단에 [도구] 메뉴가 없는 신버전의 경우 아래 그림과 같이 하면 된다.

• 잠깐 동안 임시로 막는 방법
•  키보드의 Insert 버튼을 눌러 삽입상태에서 겹쳐쓰기상태로 변경하면, 자동고침옵션이 적용되지 않는다.

한글은 잘 안써서 모르지만, 아마 한컴 한글에도 위와같은 설정이 존재할 것이니, 찾아보시는 게!

Rubik's Cube는 Erno Rubik이라는 아저씨가 처음 발명했다. 일반적인 형태는 3x3x3 정육면체 모양이고, 6면의 색깔을 모두 맞추는게 퍼즐의 목표다.

어릴 때 외삼촌이 가지고 온 큐브를 만진 적이 있지만, 본격적으로 큐브를 시작했던건 2004년이다. 엄마 졸라서 비싼거 사서 놀았었다. (지금은 큐브들 다 주변 사람들 나눠주고 하나도 없다 ㅠㅠ)

25주년 기념 큐브도 있었는데... ㅠㅠ

어쨌든 요즘 알고리즘 생각 -> 큐브 맞추는 알고리즘 -> 큐브 로 생각이 넘어오면서 간만에 추억에 잠겨 결국 큐브를 지르고야 말았다!! 무려 인터넷 판매샵에서 18900원에 파는;; 예전에 길들인 좋은 큐브들이 다 사라진 마당에 입문용 일반 큐브를 샀다간 마음에 들지 않을 것 같아서 요즘 제일 잘나간다는 큐브로 질러버렸다.

어쩐지 당분간은 큐브에 빠져서 살 것 같다. 더불어 나는 CS전공자니까 알고리즘을 이용해서 일반적으로 사람들이 많이 쓰는 프리드리히 해법 같은, 사람들이 보고 배울 수 있는 큐브 해법을 체계적으로 알고리즘을 통해 만들어 봐야겠다!

-- 여담 --

우리나라의 최초의 큐브 동호회가 있었다. 현재는 카페가 망하고 다른 카페가 활동이 많은 것 같지만, 우리나라의 한 중학교였나? 그곳의 수학선생님이 카페를 만들었었는데 나는 처음 그곳에서 큐브를 배웠었다. 우리나라에서 아마 어느정도 규모로 큰 동호회 중에 최초로 생긴 동호회일 듯?

그리고 나는 예전에 대구에서 살았는데, 대구 정기모임이 처음 생기던 날 그 정기모임에 내가 있었다! 하하하<del>아무도 안물었어</del>

어쨌든 그냥 그렇다고..

얼마전에 생각했던 Rubik's cube 해결 알고리즘을 고민하면서, 이곳 저곳을 찾아봤다. 찾아보다보니, 구현 자체보다는 그에 관련된 내용들을 많이 접하고 공부하는 게 더 중요하다는 생각이 들었다.

이번에 소개할 알고리즘은 A*(A star) algorithm이다. 이 알고리즘은 Shortest path problem을 푸는 데 주로 사용된다. A* 알고리즘은 다익스트라(Dijkstra) 알고리즘의 변형판 쯤된다.

우선, 해당 알고리즘을 소개하기전에, 다익스트라 알고리즘과 Best-first search에 대해 간단히 이야기해보자.

다익스트라 알고리즘과 Best-first search는 둘 다 greedy 알고리즘이며, 어쨌든 출발 지점에서 도착 지점까지의 가장 짧은 경로를 탐색하는데 사용된다.

둘 사이의 가장 중요한 차이점은 다음과 같다.

1. 다익스트라 알고리즘은 출발지점과 앞으로 선택할 지점 간의 거리를 기준으로 다음 선택지를 고른다.

2. Best-First search는 도착지점과 앞으로 선택할 지점 간의 거리를 기준으로 다음 선택지를 고른다.

그러니까, 대략적으로 다익스트라는 출발지를 중심으로 하고, 출발지와 도착지의 거리를 반지름으로 하는 범위에 있는 것들을 대부분 탐색하게 된다. 반면에, Best-first search는 도착지점으로 향하는 방향에 있는 녀석들만 탐색하게 된다. 따라서 best-first search가 다익스트라에 비해 수행시간이 훨씬 빠르다.

여기에서 best-first search는 문제점이 있다. 바로 다익스트라는 찾은 경로가 shortest path라는 것을 보장해주는 반면에 best-first search는 그렇지 않다는 것이다.

그렇다면 다익스트라가 최선의 방법일까? 그건 아니다.

A*알고리즘은 다익스트라 알고리즘을 보정해준다. 휴리스틱을 통해서.

휴리스틱이란, 쉽게 말해서 적당히 추측해서 괜찮은 방향으로 진행하는 것이다.

위의 두 알고리즘과 비교했을 때, A*알고리즘은 Best-first search가 탐색하는 범위 정도로 비슷하게 탐색을 하면서, 동시에 그 경로가 shortest path임을 보장해준다!! (짱짱맨이네)

A*알고리즘에서는 (현재까지 온 경로에 대한 정보 + 이후 경로를 통해 도착점까지 갈 추측된 정보)를 바탕으로 다음 선택지를 선택한다.

Rubik's cube 문제를 풀기 위해 A*알고리즘을 변형한 알고리즘을 누군가 만들었는데, 현재까지는 그게 제일 효율적인 듯 하다. 어쨌든 이런 저런 알고리즘들을 공부하고, 그 생각방식을 배워가면서 나만의 Rubik's cube 해법을 찾아봐야겠다.

A*알고리즘은 다음의 링크에서 엄청나게 잘~ 설명되어있으니, 이 포스트 내용이 부실하다고 생각되는 분들은 읽어보시길!

Introduction to A*

여담인데, 나는 2004년부터 한 2010년 정도 까지 rubik's cube를 취미생활로 했었다. 그동안 다양한 퍼즐도 많이 사고, 큐브도 많이 사고 그랬는데 나중에 안한다고 주변 지인들에게 다 나눠줬더니... 흠 막상 요즘 다시 하고 싶어지네.. 다시 살까