Algorithm 26

알고리즘_시간복잡도 예제

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

알고리즘_시간복잡도, 공간복잡도, Big-O 표기법

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

#10_ 비밀지도(2017 카카오톡 블라인드테스트 1차)

안녕하세요. 문범우입니다.이번에 소개해드릴 알고리즘 문제는, 2017년 카카오톡 블라인드테스트 1차 코딩시험에서 나왔던 문제중 난이도가 제일 낮다는 소개된 '비밀지도' 문제입니다. 해당 문제는 프로그래머스를 통해, 아래 주소에서 만나보실 수 있습니다.https://programmers.co.kr/learn/courses/30/lessons/17681?language=python3 난이도가 가장 낮다고 소개된 만큼, 문제자체도 간단하고 풀이도 어렵지 않습니다.따라서 해당 문제는 추가적인 설명대신 코드만 첨부해드리도록 하겠습니다.추가적으로 궁금한 사항이 있으시면 언제든지 댓글 및 카카오톡이나 이메일을 통해서 연락주시면 바로 답변드리도록 하겠습니다. 123456789101112131415161718192021..

#9_ 추석트래픽(2017 카카오톡 블라인드테스트 1차)

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

JAVA #3_ The Grid Search

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

JAVA #2_ Lily's Homework

안녕하세요. 문범우입니다. 이번에는 Hackerrank의 문제를 풀어보았습니다.문제 이름은 Lily's Homework이며 Medium 난이도에 속해있습니다.생각외로 rate가 47% 정도로 좀 낮은편 입니다.해당 문제는 아래 주소에서 풀어보실 수 있습니다. https://www.hackerrank.com/challenges/lilys-homework/problem 코드에 주석을 통해 설명을 덧붙여 놓았기 때문에 추가적인 설명은 생략하겠습니다.해당 코드는 아래 github 주소에서도 확인할 수 있습니다. https://github.com/doorBW/algorithm_practice 보다 궁금한 점이 있으신 분들은 댓글 및 이메일, 카카오톡을 통해 연락주시면 바로 답변드리도록 하겠습니다 :) 123456..

#8_ 야근 지수(정확도 o, 효율성 o, 프로그래머스 level3)

안녕하세요. 문범우입니다. 오랜만에 파이썬으로 풀이한 재밌는 알고리즘 문제를 가져왔습니다.알고리즘 문제는 프로그래머스의 알고리즘 연습에 나온 야근 지수 문제이며 해당 문제는 아래 주소에서 풀어볼 수 있습니다.문제에 대한 설명도 해당 주소에 나와있기에 문제에 대한 설명은 생략하겠습니다.https://programmers.co.kr/learn/courses/30/lessons/12927 사실 예전에 매우 간단히 풀이한 문제인데다시 확인해보니 문제 개편이 되면서..테스트 케이스가 매우 까다롭게 변했더라구요.그래도 정확도 통과는 비교적 무난했지만, 효율성 테스트에서 계속 막혀 씨름을 하다가 마침내 풀게되었습니다.코드와 함께 간단한 해설을 첨부합니다.추가적으로 궁금하신점이 있으신분들은 이메일이나 카카오톡으로 언제..

Java #1_ 가장 긴 팰린드롬 길이 구하기

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

알고리즘 #11_ KNN 최근접 이웃 알고리즘이란?

안녕하세요. 문범우입니다. 이번 포스팅에서는 분류나 회귀에서 사용되는 KNN(K - Nearest Neighbors) 알고리즘에 대해서 알아보도록 하겠습니다. 1. KNN(K - Nearest Neighbors) KNN, K-최근접 이웃 알고리즘은 특정공간내에서 입력과 제일 근접한 k개의 요소를 찾아, 더 많이 일치하는 것으로 분류하는 알고리즘입니다. 말로 이해하는 것보다 아래 그림을 통해 이해하는 것이 훨씬 쉬울 것 입니다. 위의 그림과 같은 좌표공간을 예시로 확인해보겠습니다.위에서 파란색 점으로 되어 있는 그룹을 A그룹이라고 생각하고, 주황색 점으로 되어 있는 그룹을 B라고 하겠습니다.이때 우리는 별 모양으로 표시된 입력값이 A그룹에 속하는지, B그룹에 속하는지를 알고 싶습니다. 그리고 이럴때 사용되..

#7_ Forming a Magic Square by python(파이썬으로 마방진 만들기)

안녕하세요. 문범우입니다.오랜만에 재미난 알고리즘 문제를 풀게되어 포스팅하게 되었습니다.문제의 출처는 HackerRank 이며 아래의 주소입니다. https://www.hackerrank.com/challenges/magic-square-forming/problem 문제설명에 대한 전문은 위의 링크에서 확인하실 수 있으며, 제 github에서도 확인하실 수 있습니다.https://github.com/doorBW/hacker_rank_algorithm_practice 문제에 대해서 간단히 설명드리면 아래와 같습니다. - Forming a Magic Square 먼저, Magic Square는 마방진이라고 이야기하겠고, 마방진에 대한 규칙은 다음과 같습니다.3*3 형태를 가지는 마방진 행렬에서는 1부터 9까..

728x90