같은 빅 오 표기법을 가진 알고리즘이라도 저마다의 속도가 다 다르다. 해당 장에서는 왜 각기 다른 알고리즘들이 같은 빅 오로 일반화 되어 표기되는지 설명이 되어 있다. 5.1 선택정렬 더보기 선택정렬은 모든 배열을 하나씩 확인하며 배열 속 어떤 값이 최솟값인지 확인하고, 최솟값과 가장 첫번째 인덱스의 교환이 이루어 진다. 버블정렬과 달리 검색, 교환이 이루어지지만 교환은 한 사이클에 1회만 이루어 지기때문에 버블 정렬보단 빠른 알고리즘이다. 실제로 버블 정렬과 선택정렬 모두 O(N^2)의 알고리즘이지만 실제로는 O(N^2/2)의 성능을 보인다. 5.3 선택정렬의 효율 더보기 버블정렬은 모든 값을 순회하며 (N-1) + (N-2) + (N-3) .... +1 과정과 교환과정 N을 거치기 때문에 O(N^2)..
앞서 빅 오에 대해 공부를 하였다. 빅 오를 사용하면 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 수 있고 내가 만든 알고리즘이 일반적으로 쓰이는 알고리즘에 비해 빠른가 느린가를 판달할 수 있는 척도가 된다. 4.1 버블 정렬 더보기 정렬되어있지 않은 배열을 오름차순으로 정렬하는 기본적인 정렬알고리즘인 버블 정렬이 있다. 버블정렬은 배열 내 연속된 두 항목을 가르킨다.(최초에는 첫번째와 두번째 원소) 2 1 3 5 두 항목중 좌측의 값이 큰 경우 두항목을 서로 바꿔준다. 이후 다음 두 항목을 가르킨다. 1 2 3 5 값이 정상적이면 교환없이 다음으로 넘어간다. 1 2 3 5 마지막까지 반복하면 하나의 패스스루가 끝나고 패스스루간 교환이 이루어졌기때문에 추가적인 패스스루를 실행한다. 버블정..
앞선 장에서 여러 효율성을 N 또는 N+1 단계와 같은 표기법을 사용했지만 이러한 방법은 너무 장황하기 때문에 알고리즘의 효율성을 간결하고 일관된 언어로 설명하기위해 형식화된 표현법을 빅 오 표기법 이라 부른다 3.1 빅 오 더보기 기본적으로 선형검색의 경우 최악의 경우 N단계가 필요한 기법이고 이를 빅 오 표기법으로 표시하면 O(N) 위와 같이 나타낸다. O(N)은 알고리즘에 N단계가 필요하다는 뜻이다. 또한 읽기와 같이 데이터의 갯수와 상관없이 항상 일정한 단계(읽기의 경우 1단계)가 필요한경우는 O(1) 위와 같이 표기한다. O(1)같은 경우는 배열의 원소의 개수와 상관없이 항상 같은 단계를 필요로 하기때문에 "가장 빠른" 알고리즘 유형으로 분류하고 상수시간을 갖는 알고리즘이라 부르기도 한다. 3...
2.1 정렬된 배열 더보기 알고리즘? 어떤 과제를 완수하는 명령어 집합 정렬된 배열? 배열의 값이 순서대로 정렬된 상태를 유지하는 배열을 뜻한다. 2.2 정렬된 배열의 검색 더보기 정렬된 배열에선 값이 배열에 들어있지 않을 때 검색을 더 빨리 멈출 수 있다. ex) [3,17,75,80,202] 의 배열속 22를 찾는다 가정하면 75까지 도달하면 22가 더이상 오른쪽에 존재할 수 없기 때문에 검색을 멈출 수 있다. -> 특정 상황에서 전형적인 배열보다 정렬된 배열에서 검색의 단계수가 더 적게 걸린다. 하지만 찾으려는 값이 가장 마지막이거나 마지막보다 큰 수이면 일반 배열과 동일한 단계가 걸릴 수 있다. 2.3 이진검색 더보기 ※ 이진검색은 정렬된 배열에서만 사용이 가능하다. 배열속 중간지점을 통해 상/하..
/* 글을 작성하기에 앞서 본 게시판의 글은 "누구나 자료구조와 알고리즘 개정2판" ㅡ제이 웬그로우 저, 심지현 옮김 ㅡ 책을 통해 개인적으로 공부하고 기록을 위해 작성하는 글이다. 나는 좋은개발자란 무엇일까, 좋은개발자가 되기 위한 과정은 무엇이 있을까를 고민하다 역시 기본적인 역량을 잘 갖추고 있는 개발자가 좋은 개발자가 아닐까 라는 생각에 대학시절 스쳐가듯 배웠지만 기억속에서 희미하게 남아있는 자료구조와 알고리즘에 대해 기초적인 역량을 다지고자 책을 구입했고 공부를 시작하게 되었다. */ 1.1 데이터 더보기 - Data? = 데이터란 일반적으로 모든 유형의 정보를 망라하는 용어이다. 데이터의 조직에 따라 코드의 실행속도에는 큰 영향을 미치게 된다. - 자료구조 = 자료구조란 데이터를 조직하는 방법..
