선돌이의 코딩하우스

문제 설명 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘..

신장 트리와 크루스칼 알고리즘이란 것을 많이 들어는 봤는데 자주 까먹어서 정리해놓으려고 한다. 신장 트리란 ? 하나의 그래프가 있을 때 모든 노드를 포함하면서, 사이클이 존재하지 않는 부분 그래프를 의미한다. 따라서 다음과 같이 하나의 그래프에 대한 여러가지 신장 트리가 존재한다. 크루스칼 알고리즘이란? 알고리즘 문제를 풀다보면 최소한의 비용으로 신장 트리를 찾는 문제를 많이 봤을 것이다. 예를 들어 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있도록 하려고 할 때 최소 비용을 구하는 문제. 크루스칼 알고리즘의 순서는 이러하다. 1.모든 간선에 대하여 오름차순으로 정렬 2.간선을 순차적으로 확인하며 사이클 체크 2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 2-2. 사이클이 발생하..

문제 개미 전사는 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을의 식량창고는 일직선으로 되어 있는데 식량창고는 일직선으로 이어져있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 메뚜기 정찰병은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 개미 전사는 식량창고 N에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하라. 예를 들어 식량창고 4개가 아래와 같이 존재한다고 가정하자. [1,3,1,5] 이때 개미 전사는 두 번째..

이진 탐색이란? 1. 재귀를 이용한 이진탐색 def binary_search(arr,target, start,end): if start > end : return None mid = (start+end)//2 if arr[mid] == target: return mid elif arr[mid] > target : binary_search(arr,target,start,mid-1) else : binary_search(arr,target,mid+1,end) 2. 반복문을 이용한 이진 탐색 def binary_search(arr,t,start,end): while start t : end = mid -1 else : end = start +1 이진 탐색의 시간 복잡도 : O(logN) 한 번 탐색 할 때마다..

문제 동빈이는 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1) 이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N, M (4 m-1: continue elif maze[nx][ny] == 0 : continue elif visited[nx][ny] == True: continue else :..