Algorithm/이론8 [알고리즘] 이분 탐색 이분 탐색 탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식입니다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠릅니다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐색하는 것입니다. mid의 값은 (left + right)/2 으로 잡아주고 우리가 검색하고자 하는 값과 mid 값을 비교합니다. 순서로 말하자면 1.이분 탐색을 하고자 할 때 이미 정렬이 되어있어야 합니다.2. left, right로 미드값을 잡아줍니다.3. mid 값과 구하고자 하는 값을 비교 합니다.4. 비교할시 mid 값보다 구하고자 하는 값이 높으면 left를 mid+1로 만들어주고 낮으면 right를 mid-1로 만들어 줍니다. 5. left > right 가 될때까지 1~3번을.. 2016. 4. 6. [STL] sort 사용하기 sort 사용하기 sort는 말 그대로 정렬을 시켜주는 것이다. 가장 큰 장점은 그 상황에 맞는 가장 적절한 방법으로 정렬을 시켜주기 때문에 효율적이라고 합니다.sort의 몇가지 특징을 써보자면 1. #include 에 포함되어 있습니다. 2. 정렬 설정을 하는 여러 방법이 있습니다. 디폴트 값은 오름 차순입니다. 3. 정렬을 하는 방법으로는 연산자 오버로딩과 비교함수를 만드는 경우등이 있습니다. 4. 비교함수를 만들때 주의점은 const 를 사용해야하고 & 연산자를 사용해야 합니다 왜냐하면 비교를 하는 과정에서는 값의 수정이나 변경이 없다라고 가정하고 단순 비교만 하기 때문입니다.비교함수를 사용하여서 sort 사용하기 1234567//--------------------------------------.. 2016. 4. 5. [STL] vector 사용하기 vector 사용하기 vector는 배열을 동적으로 사용하는 것이라고 보면 된다. 즉 길이가 변화는 배열이라고 보면 된다. vector의 특징을 보자면 1. #include 에 존재2. 배열인데 길이가 동적으로 변한다.3. 순차적으로 삽입, 제거가 이루어진다.4. 구현이 쉽다. 5. 랜덤 접근이 용이하다. 정도가 있는거 같다. 나도 공부하면서 적기 때문에 모든 특성에 대해서 알지는 못하지만 내가 알게된 특징들을 중심적으로 적는다. 그리고 햇갈리는 것이 있다면 vector[] 와 vector()를 유의 해야한다. vector[] 는 vector 자체가 배열로 존재하는 것이고 vector()는 vector 하나의 사이즈인 것이다.vector의 주요 멤버 주로 사용하는 멤버를 설명하자면 1. clear() -.. 2016. 4. 4. [STL] pair 사용하기 pair 사용하기 좌표와 같이 x,y 로 쌍으로 이루어져서 표현해야하는 경우가 많다. 이미 STL에서 쌍으로 되는 데이터를 편하게 사용하게 pair라는 것을 제공해준다. pair는 두 자료형을 묶을 수 있다. 그 특징을 보자면1. #include 에 존재한다.2. 두 자료형을 묶을 수 있다.3. 첫번째를 자료형에 접근하기 위해서 first, 두번째 자료형에 접근하기 위해서 second로 접근이 가능하다.4. make_pair(a,b) 를 이용하거나 생성자를 이용하여서 만들 수 있다.5. pair안에 pair가 들어갈 수 있다. 위의 그림과 같은 느낌이다. 코드 예 pair에 pair 가 들어간 경우는 예를들어 pair a 로 정의하면 a.first.first, a.first.second 이런식으로 접근 .. 2016. 4. 4. [조합] nCr 쉽게 구하기. (수정 20190604) nCr 쉽게 구하기 (수정 20190604) 오랫만에 와서 살펴보니 코드와 예시를 든 이미지가 잘못되서 수정하였습니다 ㅜㅡㅜ nCr 같은 경우는 n개의 숫자에서 r개를 뽑는 경우의 수이다. 경우의 수를 구하는 경우에서 많이 사용한다. nCr의 수식은 아래와 같다. 즉 매번 이 수식을 사용한다는 것은 n! , r!, (n-r)! 를 사용해야 한다. 즉 여기서 말하고자 하는 것은 이 것을 매번 사용할때마다 구하지 않고 미리 다 구해놓아서 그 숫자를 사용하는 것이다. 이것을 1개를 뽑는것 부터 n개를 뽑는 것 까지의 조합을 쭈욱 정리하다 보면 숫자의 특성이 나올 것이다. 위의 것에서 보면 1개에서 뽑는 경우의 수에서 6개의 경우수를 뽑는 것을 쭈욱 나열 한 건데 여기서 숫자가 어떻게 나오는 지에 대한 일정 패.. 2016. 4. 3. [그래프의 표현] 인접 리스트 인접 리스트 그래프를 표현하는 방법중의 한가지 방법이다. 즉 링크드 리스트 ( 벡터) 를 사용한 배열로 그래프를 표현해 주는 방법이다. 인접 행렬과 달리 간선의 개수로만 검색하는것이 줄어들기 때문에 검색 속도가 빠르다. 즉 아래의 그래프를 표현해 준다면 다음과 같다. 어찌보면 인접 행렬이랑 뭐가 다르냐??? 라고 물어볼 수 있는데 그건 탐색의 시간에서 큰 차이를 보인다. 인접행렬의 같은경우는 접점의 개수 x 접점의 개수의 맵을 전부 탐색해야 되지만 인접 리스트는 간선의 개수만 탐색 해도 되기 때문에 차이가 난다. 왼쪽의 그림이 인접 행렬이고, 오른쪽은 인접 리스트인데 속도 면에서도 횟수의 차이가 명백히 나는 것을 볼 수 있다. 코드 구현 인접 리스트를 만드는 코드 구현 같은 경우는 매우 짧고 쉽게 만들 .. 2016. 4. 1. 이전 1 2 다음 728x90
