기계는 정직하다

Programmers Lv.2 '리코쳇 로봇' 파이썬 코드 및 풀이 리코쳇 로봇이라는 보드게임에 나오는 유명한 알고리즘이다. 흔히 빙판길에서 목표지점까지 이동하는 형태로 옛날 고전게임 등에 퍼즐로 많이 등장한다. 조건파악 board의 크기 자체는 크지 않다. 그리고 ice slide 문제는 반복횟수가 그렇게 많지 않다. 접근 Ice Slide 문제는 BFS를 이용해 푼다! 탐색지점은 항상 상하좌우 방향의 네 곳이 된다. 각 방향의 탐색은 해당 방향으로 +1씩 계산하며 벽 또는 블럭이 나오기 직전 지점을 기록한다. 이동횟수가 적은 지점을 우선으로 하여 탐색을 반복하면 자연스럽게 BFS를 구형하게 된다. BFS와 별개로 각 방향을 탐색하기 위해 1차원탐색을 해야하기 때문에 구현이 조금 까다롭다. 의사코드 B..

프로그래머스 Lv.2 '혼자서 하는 틱택토' 파이썬 코드 및 풀이 조건파악 3x3 틱택토 게임인데 특별히 이 문제에서는 특정시점의 게임판만 보고 문제를 해결한다. 규칙대로 진행되지 않기 때문에 생각보다 논리력이 요구되는 문제인 것 같다. 3x3이기 때문에 코드 복잡도 측면에서 제한되는 부분은 딱히 없어 보인다. 접근 규칙대로 진행되지 않았다고 단정할 수 있는 몇 가지 케이스들이 있을 것이다. 그리고 이 문제는 해당 케이스들을 빠짐없이 확인하는 부분을 제대로 구현했느냐가 관건이다. 중간과정을 생략하더라도 반드시 지켜져야 하는 규칙과 그에 따른 반례를 다음과 같이 정리해보았다. 선공 후공 번갈아가며 진행되어야 하기 때문에 'O'의 개수는 'X'의 개수와 같거나 한 개 많아야 한다. 1. 순서를 지키지 않은 ..

ProgrammersLv.2 '미로 탈출' 파이썬 코드 및 풀이 대표적인 BFS문제, 근데 이제 경유노드를 곁들인 조건 파악 1. mpas는 최대 100x100이므로 N(max) = 10,000이다. 2. 경유노드(L:레버) 한 곳을 거쳐야 하므로 2N(max) = 20,000이며 시간복잡도 O(N)만에 풀면 된다. 접근 1. 최단경로를 구하기 위해 BFS로 푼다. 2. 경유노드가 있기 때문에 BFS를 두 번 한다. 의사 코드 시작점부터 L까지 BFS탐색 경로의 길이 저장 L부터 E까지 BFS탐색 최종 경로 반환 구현 from collections import deque def solution(maps): rows,cols = len(maps), len(maps[0]) r,c,distance = 0,0,..

AI기술의 발전 속도는 어마무시하다. 학계는 이러한 기술 발전을 이루기 위한 핵심요소 중 하나인 Multi-modality을 추구한다. 멀티모달을 훌륭하게 구현한 BEiT-3를 여러분들께도 소개하겠다. Multi-modality or Multimodal 모달리티(modality)는 사전적으로 '양식, (인체의 감각적) 양상'이라고 한다. 실질적인 의미의 modality는 기계가 이해할 수 있는 요소 혹은 요소들과 상호작용하는 방법이다. 텍스트, 이미지, 음성, 그리고 물리적 움직임 등 여러 채널의 요소들을 이해하고 학습할 수 있는 특성을 멀티모달(Multi-modal)이라고 한다. 기존의 AI와 다르게 Multi-modal AI 혹은 모델은 비교적 폭넓은 종류의 여러 데이터를 학습하고 그들 사이의 관계를..

vscode.dev는 VS Code를 브라우저에서 사용하도록 하는 웹앱이다. 설치가 필요 없으며 VS Code의 모든 기능을 거의 완벽히 수행한다. (공식 블로그 왈) 그러나 브라우저라는 근본적인 문제로 일부 익스텐션이 제대로 작동하지 않는 경우가 있다! 이번 포스팀에서는 내 PC에서 동작하는 Jupyter 서버를 vscode.dev에 연결하는 방법을 소개한다.Quick Start주피터 실행 시 Anaconda Prompt에 다음 커맨드 입력 후 나의 주피터 서버를 커널로 선택하면 된다.jupyter notebook --no-browser --NotebookApp.allow_origin_pat="https://.*vscode-cdn\.net"ORjupyter notebook --no-browser --N..

Programmers Lv.2 '호텔 대실' 파이썬 코드 및 풀이 조건 파악 1. N은 최대 1,000이므로 시간복잡도 O(N^2)만 되어도 풀 수 있다. 2. book_time[i]의 각 원소가 HH:MM이기 때문에 그대로 정렬해도 원하는 결과를 얻을 수 있다. 접근 1. 모든 객실의 타임테이블을 알아야 하는 것은 아니다. 필요한 최소 객실의 수는 즉, 동시에 이용하는 최대 객실의 수이다. 2. 위 그림과 같이 시간축을 따라 이용중인 객실의 수를 세보면 최대값을 알 수 있을 것이다. 3. 로직은 예약자를 입실시켜서 이용중인 방이 늘어나는가 아닌가 이 두 가지를 구분하는 것이다. 4. 이용중인 최대 객실의 수를 알아내는 것이기 때문에 이용중인 객실이 줄어드는 것은 고려할 필요가 없다. 의사코드 입실시각을..

Programmers Lv.2 '빛의 경로 사이클' 파이썬 코드 및 풀이 딱 봐도 어려워 보이는 문제이다. 차근차근 제약조건을 뽑아내서 접근 방법을 좁혀보자. 시간복잡도 grid는 최대길이 500인 것이 최대 500개 모여있는 것이다. 표현하자면 최대 500x500 크기의 행렬이 될 것이다. 모든 지점을 탐색한다고 할 때 N은 최대 250,000이다. 시간복잡도 O(N) 혹은 O(NlogN)까지도 가능할 것 같다. 자료구조 사이클의 갯수와 경로의 길이를 알기 위해 우리는 프로그램적으로 빛을 이동시켜야 하고 이 경로를 기록해야 한다. 경로를 만들면서 몇 개의 지점을 지났는지, 한번 사이클이 완성되면 또 지나지 않은 경로는 어디에 있는지 알아야 한다. 다행히도 빛의 경로는 들어오는 것과 나가는 것이 일대일대..

AI투자도 손실이 발생하던데, 폭락장에서도 살아남는 AI는 어느것일까? 본 글에서는 요즘 유행하는 알고리즘투자의 길잡이가 될 '코스콤 로보어드바이저 테스트베드센터'를 소개한다. 이미 판매중인 투자상품을 비교하는 내용이 아니니 참고바란다. 퀀트 들어가기에 앞서 오해의 소지를 방지하기 위해 프로그램을 이용한 주식매매에 대해 설명하겠다. AI투자는 결코 새롭게 등장한 것이 아니다. 수십년 전부터 퀀트라는 이름의 과거의 축적된 데이터와 고도화된 수학적 방법론을 바탕으로 주식투자를 하는 방법이 있어왔다. 과거의 데이터를 분석하는 과정에 요즘은 거의 머신러닝을 이용하고 있으니 AI투자와 같은 맥락으로 봐도 무방하다. 그러나 시판되는 상품의 알고리즘이 기계를 통한 학습에 의해 도출된 것인지 아니면 사람이 계산한 고도..

Programmers1 Lv.2 '유사 칸토어 비트열' 파이썬 코드 및 풀이 조건 파악 유사 칸토어 비트열의 길이는 5^n 이므로 최대 13자리 수이다. 한편, r < l + 10,000,000은 r - l < 10,000,000이므로 하다못해 l부터 r사이의 구간만 탐색한다 해도 그 길이가 최대 10^7이다. 따라서 이 문제는 시간복잡도 O(N)만에 풀어야 한다. 유사칸토어비트열을 구하고 또 구간을 탐색하면 시간초과가 발생할 것이다. 접근 풀이의 목적은 유사 칸토어 비트열을 구하는 게 아니라 특정 구간의 1의 개수를 알아내는 것이다. 패턴을 파악하면 비트열을 구하지 않아도 개수를 알 방법이 있을 것이다. 한편, 1의 개수를 구하는 함수를 count(from,to)라고 할 때 count(l,r)은 cou..

엄밀히 말하면 jQuery.ajax({}) 안에 올 수 있는 Settings를 정리한 것이다. jQuery 도큐멘테이션 들어가면 다 나온다. 내가 써 본 것만 정리해봤다. ​ 각 설정은 키/값의 맵으로 명시하며 (옵션):(값) 형태로 작성한다. 옵션 사이에는 쉼표를 붙이면 된다. ​ $.ajax({ url:"/home/search.do", contentType:"application/json; charset=UTF-8", type: "POST", data: JSON.stringify({ 'search' : search }), dataType:"json", success : function(data){ resultHtml(data); } }) async (default: true) 비동기 요청인지 동기 요..