알고리즘

안녕하세요! 오늘은 BigInteger 를 사용하는 방법에 대해 이야기해보기위해 하노이탑의 문제를 예시로 들려고 합니다. 특히, BigInteger 를 사용할 때 주의해야 할 점들과, 입력값이 매우 큰 경우(예: 100)에 대한 처리 방법에 대해 살펴보겠습니다. https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net BigInteger 사용의 핵심 이유 input : 100 output : 1267650600228229401496703205375 자바에..

회의실 배정 성공 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 ..

안녕하세요 오늘은 파이썬으로 푸는 간단한 DFS 문제를 소개해드립니다. DFS자체가 간단한 알고리즘은 아니지만 이해하신 분들에게는 쉬우며 아직 이해 도중에 있는 분들은 연습 삼아 풀어볼 만한 문제인 것 같네요. 문제 n * m 크기의 이차원 영역의 좌측 상단에서 출발하여 우측 하단까지 뱀에게 물리지 않고 탈출하려고 합니다. 이동을 할 때에는 반드시 아래와 오른쪽 2방향 중 인접한 칸으로만 이동할 수 있으며, 뱀이 있는 칸으로는 이동을 할 수 없습니다. 예를 들어 과 같이 뱀이 배치되어 있는 경우 실선과 같은 경로로 탈출을 할 수 있습니다. 이때 뱀에게 물리지 않고 탈출 가능한 경로가 있는지 여부를 판별하는 코드를 작성해보세요. 입력 형식 첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 ..

안녕하세요 오늘은 완전 탐색 알고리즘 문제를 하나 가져와 봤습니다. python은 사용하면 사용할수록 정말 편하고 잘 만든 언어라는 게 느껴지네요 시작하겠습니다. 문제 n×n크기의 이차원 영역에 파묻힌 금을 손해를 보지 않는 선에서 최대한 많이 채굴하려고 합니다. 채굴은 반드시 [그림 1, 2]과 같은 마름모 모양으로 단 한 번 할 수 있으며, 마름모 모양을 지키는 한 [그림 3]와 같이 이차원 영역을 벗어난 채굴도 가능하지만 이차원 영역 밖에 금은 존재하지 않습니다. 여기서 마름모 모양이란 특정 중심점을 기준으로 K번 이내로 상하좌우의 인접한 곳으로 이동하는 걸 반복했을 때 갈 수 있는 모든 영역이 색칠되어 있는 모양을 의미합니다. [그림 1]은 K가 1일때의 마름모 모양이고, [그림 2]는 K가 2일..

기계 학습의 목표 PLA를 알아보기 전에 우리는 기계학습의 최종적인 목표를 알아야 합니다. 우리는 진정한 target function(목표 함수) f가 무엇인지 모르는 문제를 가지고 있습니다. 여기서 함수란 내가 설계한 인공지능이 내가 생각하는 대로 움직이기 위한 수식을 함수라고 말할 수 있겠습니다. 그리고 목표 함수란 우리가 도출해낼 수 있는 최상의 함수를 말합니다. 그래서 기계학습을 통해 대략적인 가설 함수 g(완벽한 함수)에 근접하는 대략적인 f를 찾는데에 목표가 있습니다. 즉 f ≈ g를 만족하는 것입니다. 아래에 PLA는 성능은 떨어지는 알고리즘이지만 머신러닝의 아이디어를 보여주는데 의미가 있습니다. Perceptron Learning Algorithm (PLA) PLA는 인공신경망의 아이디어를..