코딩 끝에 낙이 온다 코딩 끝에 낙이 온다

정렬된 수열에서 특정 수를 찾고자 할 때 사용되는 탐색 알고리즘. 학부 시간에 가장 첫번째로 배우는 탐색 알고리즘이 아닌가 한다. 수행원리상 이 알고리즘을 사용하기 위해선 오름차순으로 배열이 정렬되어 있어야 한다. 일반적으로 배열을 전부 순차적으로 탐색하는 방식보다 훨씬 효율적인 방식이다. 이진 탐색이라는 이름과 같이 배열을 반으로 쪼개어 수행한다. 간결한 코드이지만, 꽤나 훌륭한 성능을 보여준다. 수행 방식은 다음과 같다. 1.배열의 시작을 left, 배열의 마지막을 right으로 정한다. 2.left와 right의 중간 점을 mid로 정한다. 3.mid로 정한 값이 찾으려는 수보다 크다면 right을 mid-1로 정하고, mid로 정한 값이 찾으려는 수보다 작으면 left를 mid+1로 정한다. 4...

계수 정렬. 이름처럼 숫자를 세어 진행하는 정렬이다. 시간 복잡도는 O(n)으로 퀵 정렬 O(n log n), 합병 정렬(O(n log n)) 보다도 빠르다(!) 어떻게 이렇게 빠른 것일까?? 계수 정렬이 이루어지는 방식은 다음과 같다. 1.정렬하는 배열의 최대 값을 크기로 가지는 배열을 하나 생성. 2.정렬하는 배열을 순회하면서 각 수들이 등장하는 빈도를 각 배열의 인덱스에 저장. 3.각 빈도를 누적한 합을 저장한 배열을 새로 생성한다. 4.다시 정렬해야 하는 배열을 역순으로 순회하면서 어떤 수가 나오면 누적합 배열의 해당 인덱스로 간다. 5.누적합 배열에 저장된 값을 인덱스로 하여 정렬된 값이 들어간 배열에 값을 저장한다. 6.누적합 배열에 저장된 값을 1씩 빼준다. 7.럼 숫자를 세어 진행하는 정렬..

수열을 입력받고, 찾아야 하는 수들이 포함된 배열을 추가로 입력받아 수열 내에 수들이 포함되어 있는 지에 대한 여부를 1 또는 0으로 출력해야 하는 문제이다. n = int(input()) entries = input().split() m = int(input()) tofind = input().split() result =[0]*m for i in entries: for b in range(0,m): if int(i) == int(tofind[b]): result[b] = 1 for u in result: print(u) 우선 입력받은 수열을 반복문으로 전체 순회하고, 하나의 요소를 찾아야할 수열 중에 하나와 일치하는 지를 반복문으로 순회하여 판별하는 방식으로 진행. 결과는 당연히 시간 초과! impo..

수 정렬하기 2와 같은 문제이나 이번엔 메모리 제한이 8MB로 정해진 문제이다. 전에 사용했던 합병 정렬을 제출했으나 역시나 될리가 없었다. 질문 검색을 해본 결과 가장 많은 사람들이 사용하는 것이 계수 정렬이었다. 그래서 계수 정렬을 알아봤는데,꽤나 빠른 알고리즘이었다 n 시간 복잡도를 가지면서도, 아주 간결한 코드였다.다음은 내가 작성한 코드. 열심히 짠 코드였지만,역시나 메모리 초과. 이번엔 누적합을 제외한 코드를 제출해봤지만 역시나 실패였다. 지푸라기라도 잡아보자는 심정으로 파이썬으로 제출해봤다. 그런데 이게 왠걸?? 맞았다.이번으로 알게 된 교훈은 pypy는 빠르지만 메모리 소모가 크다는 것!

컴퓨터의 창시자 폰 노이만이 개발한 정렬 알고리즘. 퀵 정렬과 함께 O(n log n)의 시간복잡도를 가지는 빠른 알고리즘 중의 하나이다. 퀵 정렬과 마찬가지로 분할 정복을 이용하는 알고리즘으로 최악의 경우 n^2의 시간복잡도를 가지는 퀵 정렬과 달리, 병합 정렬은 모든 경우에 n log n의 시간복잡도를 보장한다. 대략적인 절차를 설명하면 다음과 같다. 1.들어온 배열을 우선 반으로 쪼갠다.(홀수인 경우 반올림 또는 반내림한다) 2.나뉘어진 부분 각각을 다시 크기가 1이 될 때까지 재귀적으로 쪼갠다. 3.요소가 하나가 되면, 나뉘어진 부분끼리 비교하여,합치는 동시에 정렬을 진행한다. 4.위 과정을 재귀적으로 되돌아가 나뉘어진 부분을 각각 다시 정렬하며 합친다. 5.전부 합쳐지면 최종적으로 정렬된 배열이..

무작위로 입력된 소문자 영단어를 길이 순으로 정렬하되 같은 길이면 사전순으로 나열해야하는 문제이다. 단, 길이가 같으면 한 번만 출력해야 한다. import time import math def mergesort(entries): if isinstance(entries,list) and len(entries) > 1 : pivot = math.floor(len(entries)/2)-1 first = mergesort(entries[:pivot+1]) second = mergesort(entries[pivot+1:]) return merge(first,second) else: return entries def merge(first,second): unit=[] if not isinstance(first,l..

앞서 소개한 Espresso 테스팅 프레임워크를 실제로 적용해보려고 갖은 노력을 다해보았다. 지금 진행하고 있는 프로젝트가 MVC 디자인 패턴에 맞춰서 개발되고 있기 때문에, 기능이 동작할 뷰를 우선적으로 만들어야겠다는 생각에 뷰에 대한 테스트를 먼저 작성하기로 했다. 우선은 텍스트 뷰와 에딧텍스트 이미지 버튼등의 갖가지 뷰들을 배치하였고,이들이 뷰 상에서 동작해야할 테스트를 작성하려고 했는데 시작부터가 난관이었다. onView로 각 뷰를 찾아내서 perform하는 것까지는 쉬웠으나, 내가 원하는 속성을 check하는 것이 큰 골칫거리였다. 나는 특정 버튼이 눌리면 다른 레이아웃이 꺼지도록 의도하고 싶어서 visibility 관해 체크해보고 싶었으나, ViewAssertions에는 세 가지 메소드 밖에는..

Git을 사용하다 보면 한 번쯤은 그럴 때가 있을 것이다. 우리가 주로 변경사항을 커밋할 때에는, 어떠한 기능이 완성되거나 완료되었을 때 주로 하기 때문에 지금 작업하고 있는 내용이 있는데, 다른 브랜치로 체크아웃 해야 할 때, 변경이 완료되지 않았을 때, 커밋하기는 애매한 상황이 되어버린다. 그렇다고 지금까지 변경한 내용을 커밋하지 않으면, 저장되지 않기 때문에 다시 작업해야만 한다. 이럴 때에 이용되는 것이 바로 stash다. stash는 현재까지 Working Tree에서 작업한 내용을 커밋하지 않고, 별도의 저장소에 저장하는 명령어이다. 그러므로 stash 명령어를 실행하면, Working Tree가 HEAD의 위치로 돌아가 깨끗해진다. 이러한 점은 다른 브랜치에서 rebase를 실행하거나 병합 ..

https://cishome.tistory.com/119

브랜치란? 개인이 깃을 통해 버전 관리를 하는 상황에서, 어떠한 기능을 처음 개발하는데 도중에 문제가 생겼다고 한다면 그저 지금까지 해왔던 변경사항들을 버리고 이전으로 되돌아가면 해결이 되겠지만, 회사 업무 등과 같이 여러 사람들과 함께 협업해서 진행해야하는 프로젝트라면 이야기가 많이 달라진다. 예를 들어 어떤 대형 프로젝트를 개발 중에 한 사람이 새로운 기능을 개발해서 변경 사항을 커밋했는데, 전체 프로젝트에 그 내용이 적용되어 그 프로젝트를 개발 중인 다른 사람들에게도 그 영향이 미치게 되었다. 그런데 그 기능이 심각한 오류를 일으킨다면, 전체 프로젝트에도 문제가 생겼다면 통합 버전을 사용하던 모든 사람들에게도 영향이 가버리고,잘 진행되던 프로젝트는 마비 상황에 이르게 될 것이다. 이러한 상황을 막기..