Tigercow.Door

안녕하세요 .문범우입니다. 이번 포스팅에서는 hackerrank의 The Grid Search 문제를 풀어보았습니다.난이도는 Medium, rate는 약 75%입니다.문제 개념이나 이해자체는 크게 어렵지 않다고 생각되나 몇가지 고려할 부분들이 존재합니다. 제가 중요시 생각한 점은,먼저 탐색하고자 하는 P배열에 대해 그 첫번째 행이 G배열에서 존재할때만 실질적인 탐색문을 반복하는 것과그 첫번째 행이 G배열의 특정행에서 반복하여 존재할 수 있기 때문에 인덱스를 고려해가며 탐색하는 것 입니다. 보다 자세한 설명은 코드에 주석으로 달아 놓았습니다.궁금하시거나 코드를 보다 효율적으로 개선할 방법에 대해서는 댓글 및 카카오톡, 이메일을 통해 말씀해주시면 감사하겠습니다 :) 12345678910111213141516..

안녕하세요.이번 포스팅 부터 약 2-3회에 걸쳐 그리디 알고리즘(greedy algorithm)에 대해서 알아보겠습니다.내용에 대해 궁금한 점이나 피드백은 언제든지 댓글을 남겨주세요 :)1. 그리디 알고리즘(Greedy algorithm) 우리는 지난 포스팅에서 동적 프로그래밍(Dynamic programming)에 대해서 알아 보았습니다.단순히 모든 경우에 대해서 반복적으로 재귀호출을 통해서 탐색을 하는 Brute force의 방식보다, 각각의 경우에 대해 테이블을 만들어 필요할 때마다 테이블 값을 이용하는 동적 프로그래밍은 보다 좋은 시간복잡도를 나타냈습니다.하지만, 어찌되었든 간에 동적 프로그래밍 또한 탐색에 있어서 모든 경우에 대해서 탐색을 진행합니다. 이는 결국 필요하지 않은 케이스조차 검색하는..

안녕하세요. 이번 포스팅에서는 동적 프로그래밍(Dynamic Programming)에서의 최적 이진 검색 트리(Optimal Binary Search Tree)에 대해서 알아보겠습니다.1. 최적 이진 검색 트리 (Optimal Binary Search Tree) 최적 이진 검색트리를 보다 쉽게 이해하기 위해서 상황을 가정하며 설명드리겠습니다. 특정 문서에 중복이 허용된 여러개의 영어단어가 존재하는데 이를 한글로 번역해서 저장하는 프로그램을 필요로 한다고 가정합니다. 그렇다면 프로그램은 이를 수행하기 위해서 문서에 있는 각각의 영어단어에 접근하고, 이에 해당하는 한글 단어를 찾아야 합니다. n개의 영어 단어가 존재한다고 했을 때, 어떻게 해야 이를 효율적으로 수행하는 프로그램을 작성할 수 있을까요? 바로 ..

안녕하세요.이번 포스팅에서는 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보도록 하겠습니다.궁금하신 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)1. 최장 공통 부분 수열(LCS: Longest Common Subsequence) 먼저 최장 공통 부분 수열이 어떠한 것인지 알아보도록 하겠습니다.문제를 이해하기 위해 다음을 가정합니다. X = Y = 이러한 두 수열 X, Y가 있습니다. 이때, 는 X와 Y의 공통 부분 수열입니다.X = Y = 위에서 X 수열과 Y 수열에 밑줄을 쳐놓은 부분을 통해 는 X와 Y의 공통 부분 수열이라는 것을 알 수 있습니다.꼭 연결되어 있어야 하는 것이 아니며, 단지 단조 증가하는 수열로써 존재하면 되는 것이죠.그렇다면 ..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 자연수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최소값을 출력한다. 예제 입력 : 2예제 출력 : 1 예제 입력2 : 10예제 출력2 : 3 처음에는 알고리즘을 단순하게 생각했다가 바로 틀려버린 문제입니다.먼저 최종 정답으로 통과한 코드는 아래와 같습니다. 123456789101112131415161718192021222324a ..

안녕하세요. 문범우입니다.이번 포스팅부터 Introduction to Algorithm (3rd Edition) 책의 15장. 동적 프로그래밍(ch15, dynamic programming)에 대해서 이야기하려 합니다.매주 1~2번 정도 포스팅 될 예정이며, 공부를 하면서 내용을 정리해서 올리기 때문에 잘못된 정보나 지식이 포함되어 있을 수 있으니 참고용으로 확인해주시고, 잘못된 내용에 대해서는 피드백 주시면 감사하겠습니다.오늘은 동적 프로그래밍에 대한 개요와 동적 프로그래밍의 막대 자르기(Rod Cut)에 대해서 알아보겠습니다.1. 동적 프로그래밍(Dynamic programming) 동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합하여 문제를 해결합니다.이때, 프로그래밍이란 것은 코딩을 ..

안녕하세요.이번에는 python을 이용한 CSP algorithm 중 하나인 Einstein's puzzle(아인슈타인 퍼즐) 해결 코드를 작성해 보겠습니다. 먼저 아인슈타인 퍼즐에 대해 소개해 드릴게요.아인슈타인의 퍼즐은 아래와 같은 문제입니다. * 문제의 배경1. 색깔이 서로 다른 5채의 집이 일렬로 지어져 있다.2. 각 집에는 서로 다른 국적의 사람이 살고 있다.3. 다섯 사람은 서로 다른 음료를 마시고, 서로 다른 담배를 피며, 서로 다른 동물을 기른다. * 15개의 정보1. 영국인은 빨간 집에서 산다.2. 스웨덴인은 개를 기른다.3. 덴마크인은 차를 마신다.4. 초록집은 하얀집의 왼쪽 집이다.5. 초록집에 사는 사람은 커피를 마신다.6. 펠몰 담배를 피는 사람은 새를 기른다.7. 노란집에 사는 ..