왜 알고리즘을 공부하는가? 가장 큰 이유는 취업. 특히 해외 기업은 전화인터뷰나 1차 인터뷰로 알고리즘과 관련된 문제풀이를 시키는 경우가 많다. 실무에서는 쓸 일이 없지만, 그래도 이런 부분은 항상 갈고 닦아놔야 나중에 큰 도움이 된다. 그리고 두번째 이유로는, 구글 코드잼에 참가해보고 싶은 욕심. 맨날 해야지 해야지 하면서 당일만 되면 귀찮아서 넘겨버리곤 했었다. 어떻게 공부할 것인가? 유명한 알고리즘 사이트로는 국내에선 백준과 프로그래머스, 해외에서는 리트코드가 있다. 개인적으로 프로그래머스는 문제의 퀄리티가 굉장히 좋아서, 잘 정돈된 문제를 풀고 싶을때 좋다고 생각한다. 리트코드는 문제가 굉장히 다양하고 많은데, 잘 큐레이션된 문제들을 한눈에 모아서 풀고 싶다면 돈을 내야하더라. 아마 알고리즘 첫 ..
Parametric Search (파라메트릭 서치) [개요]이진탐색의 응용 버전.최소값이나 최대값 등의 최적해 문제를 구할 때 유용하게 쓸 수 있다.혹자는 이것을 최적화문제 = 이진탐색 + 결정문제 (Yes or No) 로 쪼개는 것이라고 표현하기도 한다. [기본 뼈대]1. 이진탐색을 이용해 임의의 값 계산(보통 mid값이다)2. 이 값은 문제의 조건을 만족합니까 안합니까? 3. 문제 조건을 만족할시 일단 저장해두고 범위를 좁혀가면서 최적화된 해에 도달 [전제 조건]이 서치를 적용하려면 해의 구간이 연속적이어야한다.만일 mid가 문제의 조건을 만족한다면, [Left,mid] 혹은 [mid,Right] 범위에 있는 해는 모두 문제의 조건을 만족할 만한 '가능성'을 가지고 있어야한다.당연한 얘기긴 한데, 5..
그래프의 정점을 모두 한번씩 방문하는 알고리즘을 순회 알고리즘(Traversal Algorithm)이라고 한다.크게 두가지 종류가 있는데,하나는 깊이 우선 탐색(DFS,Depth First Algorithm)이고, 하나는 너비 우선 탐색(BFS,Breadth First Algorithm)이다. 1. 깊이 우선 탐색 (DFS) 인접한 정점이 존재한다면 계속 한 우물만 깊게 파고드는 타입. 만약 인접한 정점이 존재하지 않는 정점(이른바 막다른 길)을 발견한다면, 이 전에 있었던 정점으로 돌아가서 또 새롭게 팔 우물(..)이 있는지 살펴본다.일단 "길이 있으면 가고 본다!!" 라는 막무가내 타입이기 때문에,①인접해있고 ②한번도 방문한 적이 없다면 , 바로 해당 정점으로 탐색하러 가면 된다. 재귀 함수만 안다면..
알고리즘의 꽃, 그래프. G=(V,E) 로 표현한다.V는 정점을, E는 간선을 의미한다. 크게 방향성 유무(Directed,Undirected)와 사이클 존재 유무(Cyclic,Acyclic)로 구분하는 듯 하다.최소신장트리 알고리즘, 순회 알고리즘 등 많은 알고리즘이 그래프에서 파생되어 나온다. 1. Graph.h 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#ifndef GRAPH_H#define GRAPH_H #include #include enum VisitMode {Visited,NotVisited}; typedef int ElementType; typedef struct t..
1. qsort() C언어 stdlib에서 제공해주는 퀵소트 함수 비교함수를 따로 만들고qsort(배열,배열의 크기,배열 요소 하나의 크기,비교함수)에 인자를 알맞게 넣어주면 된다. 123456789101112131415161718192021222324252627282930#include #include int compare(const void* a,const void* b){ int* aa=(int*) a; int* bb=(int*) b; return *aa - *bb;} int main(){ int arr[]={5,4,2,1,7,8}; int i; int size=sizeof(arr)/sizeof(arr[0]); for(i=0;i
데이터 집합이 오름차순 정렬되어 있다는 전제 하에 1. 탐색 범위를 절반(1/2)씩 줄여나가면서2. 중앙요소 값을 계속해서 비교.3. 집합의 크기가 n이라 할 때, 최대 비교 횟수 x = Log2n (예 : 1000개의 데이터 집합 내에서 최대 10번의 탐색으로 원하는 대상을 찾을 수 있다) ======================================================== 12345678910111213141516171819202122232425/* DataSet [] : 데이터 집합 정보 Size : 데이터 집합의 크기 Target : 찾고자 하는 탐색 대상 */ElementType BinarySearch(ElementType DataSet[],int Size,ElementType ..
*자기 구성 순차 탐색법 : Self-Organizing Sequential Search: 자주 사용되는 항목을 데이터 집합의 앞쪽에 배치시켜 순차 탐색의 효율을 높인다: 자주 사용되는 항목을 어떻게 선별하는가에 따라 다음 3가지로 나눔 (전진 이동법, 전위법, 빈도 계수법) ============================================================ 링크드 리스트 기준으로 작성. 앞서 SLL 코드들이 구현되어있다고 가정하고 추가할 부분만 구현 1. 전진 이동법 (Move To Front) 탐색된 항목을 데이터 집합의 맨 앞으로 "한번에" 보내버린다. 123456789101112131415161718192021222324252627 Node* SLL_MoveToFront(..
미리 정렬되어있거나 역순으로 정렬되어있는 경우 최악의 성능: N(N-1) / 2: 버블 정렬이나 삽입 정렬(최악)의 성능과 동일하지만 이런 경우가 일어나는 일은 흔치 않다: 재귀호출의 깊이 x 비교횟수: 평균적으로 nlog2n: 정확히는 1.39log2n -------------------------------------------------------------------------------------------------내 방식대로 구현한 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include void QuickSort(int DataSet[],int Left,int Right){ ..
최악의 경우로 정렬되어있는 경우엔 버블 정렬과 총 비교횟수가 같으나 ( n(n-1)/2 ) ,최선일 경우엔 (n-1)번의 비교만 이루어지기 때문에 평균 비교횟수로 따지면 버블정렬보다 살짝 더 낫다. ( 평균 비교횟수 = (n^2+n-2)/4 ) memmove(&a,&b,c) : b에 있는걸 a로 이동시키되 c만큼의 크기를 옮긴다 (#include ) ------------------------------------------------------------------------------------------------ 123456789101112131415161718192021222324252627282930313233343536373839#include #include void InsertionSor..
정렬 알고리즘의 일종.성능이 몹시 구리다. 비교해야하는 데이터의 크기가 N개라고 치면 총 N(N-1)/2 번 의 비교가 수행됨 ----------------------------------------- 1234567891011121314151617181920212223242526272829303132333435#include // 총 비교 횟수 = (n-1) + (n-2) + (n-3) + .... + 3 + 2 + 1 void BubbleSort(int DataSet[],int Length){ int i=0,j=0,temp=0; for(i=0;i
- Total
- Today
- Yesterday
- 싱크대 단수
- 사마귀광고 제거
- 마민재쉐프
- 스파관광 파트4
- 4E표시
- 겨드랑이 지방종
- 아난티앳강남
- 급수에러
- 스파 파트 4
- 친구들호캉스
- 드럼세탁기 고장
- 스텐팬 갈색
- 혐오광고 제거
- 자취요리
- 스파투어 파트4
- 스텐팬 탄 자국
- 겨드랑이 혹
- 타르코프 스파 투어
- 스텐팬 세척
- 구글애드센스 혐오광고
- 초간단 샤브샤브
- 타르코프 스파 관광
- 자취 집들이
- 스텐팬 갈변
- 구글애드센스 광고차단
- 스시이마
- 건강검진 겨드랑이
- 겨드랑이 초음파
- 겨울철 동파
- 물이 안나와요
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |