Tigercow.Door

안녕하세요. 문범우입니다.지난 포스팅에서 시간복잡도, 공간복잡도 등에 대해서 알아보며 Big-O 표기법에 대해서 살펴보았습니다.이번에는 실제로 특정 코드나 알고리즘을 대상으로 그 시간복잡도를 분석해보는 실습을 진행해보도록 하겠습니다. 아래에서 다루게 될 예제들은 ''코딩인터뷰 완전 분석"(게일라크만맥도웰 지음, 이창현 옮김)_인사이트출판 서적에서 일부 참고 및 발췌하였습니다. > N에 대한 정확한 사용 우리는 이전 포스팅에서도 그러했듯이 Big-O 표기법으로 나타낼때에 흔히 O(N), O(log N) 과 같이 나타냅니다. 그런데 이때 N에 대해 정확하게 이해하지 못하였다면 추후 잘못된 분석을 할 수 있습니다.아래와 같은 상황을 생각해보겠습니다. 여러개의 문자열로 구성된 배열이 있습니다. 이때 각각의 문자..

안녕하세요. 문범우입니다.최근 Java로 알고리즘 스터디를 시작하게 되었습니다.단순히 문제풀이 보다는 이론적인 내용들을 살펴보며 관련된 문제를 푸는 방식으로, 기초부터 다시 살펴보려합니다.이번에는 직접적인 알고리즘 내용에 앞서, 알고리즘 분석 즉 시간복잡도와 공간복잡도에 대해 이야기를 먼저 진행해보겠습니다. > 왜 알아야 하는가? Big-O 표기법은 알고리즘의 효율성을 나타내는 지표 혹은 언어이다.이를 통해 자신이 작성한 알고리즘이 이전보다 빨라졌는지 느려졌는지 판단하는데 도움이 될 것이다.물론 이 외에 다른 개발자들과 특정 알고리즘에 대해 이야기하거나 효율성 판단등에 의해서 Big-O 표기법을 통해 보다 원활하게 의사소통을 진행할 수 있다. 실제로 Big-O 표기법 이외에 다른 표기법도 있으나 이에 대..

안녕하세요. 문범우입니다.요새 많은 기업들이 공채시즌이 다가와서 그런지, 평소보다 알고리즘 문제풀이에 대한 학원이나 온라인강의에 대한 광고가 많아진 것 같네요. 요새보면 대부분의 기업에서 SW인원들은 다른 시험보다 코딩테스트를 중요시하고 있고 많은 사람들이 제일 까다로워 하는 부분인 것 같습니다. 요새 개인적으로 공부하는 기계학습이나, 리액트네이티브때문에 블로그활동을 자주못하고 있는데, 오랜만에 프로그래머스에 들어갔다가 2017년 카카오톡 블라인드테스트 1차 코딩문제를 공개해두었길래 이번주에 하나씩 풀어보려합니다. 처음에는 쉬운문제부터 풀어보려했는데.. 나중에 확인해보니 이번에 소개해드릴 '추석트래픽' 문제가 가장 어려웠다고 하네요. 프로그래머스에서 제공하는 작년 카카오톡 코딩테스트 문제는 아래에서 만나..

안녕하세요. 문범우입니다.이번 포스팅에서는 Java 언어를 통해서 '가장 긴 팰린드롬' 이라는 알고리즘 풀이를 풀어보도록 하겠습니다.해당 문제는 아래 프로그래머스 사이트에서 풀어보실 수 있습니다. https://programmers.co.kr/learn/courses/30/lessons/12904?language=java 1. 문제 접근 팰린드롬이란, 문자열을 거꾸로 뒤집었을때도 모양이 같은 것들을 말합니다.예를 들어, 'aba', 'aaddaa' 등도 팰린드롬이며 'asddfd' 라는 문자열에서는 'dfd'가 팰린드롬 문자열입니다. 해당 문제는 입력으로 주어지는 문자열에서 길이가 가장 긴 팰린드롬을 찾아서 그 길이를 반환하는 문제입니다. 팰린드롬에 대한 자세한 설명은 문제 또는 구글링을 통해 확인하실 ..

안녕하세요.이번 포스팅 부터 약 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의 공통 부분 수열이라는 것을 알 수 있습니다.꼭 연결되어 있어야 하는 것이 아니며, 단지 단조 증가하는 수열로써 존재하면 되는 것이죠.그렇다면 ..

문제다음 소스는 N번째 피보나치 함수를 구하는 함수이다. 1234567891011int fibonacci(int n) { if (n==0) { printf("0"); return 0; } else if (n==1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}Colored by Color Scriptercs fibonacci(3) 을 호출하면 다음과 같은 일이 일어난다.fibonacci(3) 은 fibonacci(2) 와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2) 는 fibonacci(1) (두 번째 호출)과 fibonacci(0) 을 호출한다.두 번째 호출한 fibonacci(1)..

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

이번 포스팅에서는 동적 프로그래밍의 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)에 대해서 알아보도록 하겠습니다.1. 행렬 체인 곱셈(Matrix-chain Multiplication) 이번 세번째 예제인 행렬 체인 곱셈(Matrix-chain Multiplication)문제는 n개의 행렬을 곱하는 것에 대한 문제입니다.먼저 행렬의 곱은 아래의 수도코드와 같은 방식으로 진행됩니다. 위의 수도코드를 보면 A행렬이 p*q이고 B행렬이 q*r일때, 이 두 행렬의 곱을 통한 새로운 행렬 C를 계산하는데 걸리는 시간은 수도코드의 8행에 따른 곱셈의 횟수, pqr번에 의해서 결정됩니다.예를들어, 아래와 같은 세개의 행렬이 있을 때, 두가지 방법의 곱셈이 가능할 것입니다. A1와 ..