MZ 개발자

안녕하세요. 오랜만에 문어체로 시작하는데요, 학부동안 배운 알고리즘 또는 배우지 못한 다양한 알고리즘 및 자료구조 이론을 정리해보려고 합니다. 설명 과정에 틀린 부분이나 추가해야할 부분이 있으면 언제든지 답글 달아주시면 감사하겠습니다. 오늘 배워볼 알고리즘은 KMP 알고리즘입니다. 문자 검색을 하는 가장 기본적인 방법은 부르트포스 방법으로 순차적으로 패턴을 비교하는 방법이지만 이 방법으로하면 패턴(M)이 길어지거나 문자(N)가 길어진다면 O(NM)의 시간복잡도를 가지게 됩니다. (여기서는 부르트포스 방법은 설명하지 않겠습니다.) KMP (Knuth Morris Partt Algorithm) 앞서 언급했듯이 부르트포스 방법으로 구현한다면 시간 복잡도는 O(NM)입니다. KMP 알고리즘은 부르트포스 알고리즘..

문제를 어디서 많이 봤다고 생각했는데 작년에 실제로 테스트 봤던 문제였다. 당시에는 Python으로 문제를 풀었었다. 당시 작성했던 코드가 있는데 지금 보면 어떻게 풀었는지 알수가 없다. (뭔가 알고리즘 없이 맨해튼 거리로만 푼거 같은데 도저히 이해 불가능) def solution(places): answer = [0,0,0,0,0] for place_num,place in enumerate(places): person_location = [] flag =True for i,row in enumerate(place): for j in range(len(row)): if row[j]=="P": person_location.append((i,j)) for i in range(len(person_locatio..

하나의 회의실을 여러 회의가 사용하는데 각각의 시작 시간과 끝나는 시간이 주어진다. 회의를 잘 스케쥴링 하여 회의실을 사용할때 최대 몇개의 회의가 회의실을 사용할수 있는지 구하는 문제이다. 처음에 어렵게 꼬아 생각하여 시작 시간이 빠른 순서대로 정렬하고 끝나는 시간이 빠른 순서대로 정렬하여 두개를 어떻게 지지고 볶아 비교하려고 하였다.(생각해보면 다음 회의 시작 가능 여부는 이전 회의의 종료 시간에 따라 결정된다.) 따라서 끝나는 시간을 기준으로 정렬 하여 제일 일찍 끝나는 회의를 기준으로 다음 회의 시작 시간을 결정하면 된다. 한편 문제에서 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의 시작시간과 끝나는 시간이 같을 수도 있다. 라고 주어졌기 때문에 다음과 같은 반례가 생길 수 있다..