programming

API를 사용하지만 막상 제대로 알아본 적이 없어서 정리해본다.1 API  API는 컴퓨터나 컴퓨터 프로그램 사이의 연결이다.  일종의 소프트웨어 인터페이스이며 다른 종류의 소프트웨어에 서비스를 제공한다. 그러니까 일반 사용자가 사용하는 것은 아니고, 개발자들이 어떤 프로그램을 개발할 때 사용하는 용도이다.  API를 사용하는 이유는 단순하다. 그게 시간도 단축되고, 편리하기 때문이다. 내가 원래 개발해야하는 부분을 남들이 개발해놓은 것을 사용하면 훨씬 효율적일 것이다. 다만 API는 내가 만드는게 아닌 만큼 사용법이 바뀔 수도 있으니 그 때마다 프로그램을 수정해야한다.2 OpenAPI OpenAPI는 누구나 사용할 수 있도록 공개해놓은 API이다. 보통 함수로 어떤 요청을 보내면 서버에서 요청을 처리 ..

1 정규분포 정규분포는 연속확률 분포 중 하나이다. 사람의 키나 몸무게 등이 정규분포를 따르며 거의 웬만한 자료들이 정규분포를 따른다.  정규분포는 평균과 표준편차를 알면 그릴 수 있는데 평균($\mu$)은 정규분포의 중앙을 의미하고 표준편차($\sigma$)는 얼마나 자료가 펴져있나를 의미한다.2 표준정규분포 표준정규분포는 정규분포에서 평균이 0이고, 표준편차가 1일 때를 의미한다. 이 것만으로 의미가 있지는 않고 정규화를 통해 의미를 가진다.3 정규화 정규화는 기존 정규분포를 표준정규분포로 바꾸는 것을 의미한다. 정규화를 하는 방법은 정규분포를 따르는 모든 자료에 평균을 빼고 표준편차로 나누면 된다.  이렇게 바꿈으로써 서로 다른 평균과 표준편차를 가지던 데이터를 직접 비교할 수 있게된다. 그리고 데..

1 z-score   z-score는 기존 분포를 표준정규분포를 따르도록 바꾼 후에 신뢰구간 바깥의 데이터는 이상치로 판별하는 방식이다. 신뢰구간이 99%인 경우에는 평균에서 3*표준 편차만큼 떨어진 구간까지 정상값이라고 생각하고 신뢰구간 95%는 평균에서 2*표준 편차만큼 떨어진 구간까지 정상값이라고 생각한다.  간단한 방법이고 편리하지만 자료의 분포가 정규분포를 따른다는 가정하에 쓰는 방법이기에 자료가 정규분포를 가질 때만 제대로 사용할 수 있다.2 IQRIQR은 사분위수를 이용해서 중앙값을 탐지하게 된다.  IQR은 3사분위수에서 1사분위수을 뺀 값이고,  3사분위수+1.5*IQR~1사분위수-1.5*IQR 사이를 제외한 값을 이상치라고 판별한다. 3 주의점 이상치를 처리하면 좋지만 만약 가진 자료가..

1 우선순위 큐우선순위 큐는 말 그대로 큐이긴 큐인데 우선순위를 부여하는 큐이다. 보통 크기순으로 우선순위가 부여되며 우선순위가 더 큰 것이 있다면 더 느리게 들어왔더라도 먼저 나온다.  보통 구현을 할 때 이진트리를 이용해 구현을 하게 된다. 삽입할 때는 이진트리를 채울 때 깊이가 가장 낮고 제일 왼쪽부터 노드를 채운다. 그 후 부모 노드와 자식 노드를 비교해서 부모 노드보다 자식 노드가 우선순위가 더 높다면 위치를 바꾼다. 방금 전에 한 것을 루트 노드까지 반복한다.  삭제할 때는 제일 마지막에 있는 그러니까 깊이가 가장 깊으면서 제일 오른쪽에 있는 노드와 루트 노드를 변경한다. 그 후에는 루트 노드였던 것을 삭제하고, 현재 루트 노드는 지금 우선순위 큐 규칙과 맞지 않을 것이니 부모 노드와 자식노드..

1 유니온 파인드 유니온 파인드란 어떤 한 노드와 다른 노드가 같은 그래프에 있는지 확인하기 위한 알고리즘이다. 유니온 파인드는 속도를 빠르게 하기 위해서 기존 그래프를 한 개의 노드에 전부 연결된 모양으로 바꾼다. 그러면 2개의 노드가 같은 그래프에 속해 있다면 중심의 노드에 둘 다 연결되어 있을 것이니 중심의 노드가 같은지만 확인하면 된다.  구현 방식은 배열을 이용해서 하게 된다. 배열은 arr[n] 형태로 arr[k](k 그래프를 합칠 때는 간선으로 연결된 노드 번호 2개를 받는다.  그리고 각 노드가 연결된 그래프에서의 중심 노드를 찾는다. 중심 노드를 찾는 방법은 배열에서 노드의 번호와 중심 노드의 번호가 같다면 중심 노드이다. 그래서 중심 노드를 찾으면 2개의 중심 노드가 나올건데 만약 둘의..

1 플로이드 워셜 플로이드 워셜은 모든 정점 쌍 사이의 최단거리를 구하기 위한 방법이다. 음수 가중치인 간선이 있을 때에도 사용이 가능하지만 음수 가중치로 사이클이 만들어질 경우에는 사용할 수 없다.   구현은 다이나믹 프로그래밍을 이용하여 한다. 시간복잡도는 $O(N^3)$이다.  플로이드 워셜 알고리즘은 거쳐가는 정점을 기준으로 최단거리를 구한다. 먼저 1번 노드만을 거쳐간다고 할 때 모든 정점 쌍 사이의 거리를 구한다. 그 후에 1, 2번 노드를 거쳐갈 때도 구하고, 1, 2, 3번 노드를 거쳐갈 때도 구하는 것을 반복해서 모든 노드를 거쳐갈 때 최단거리를 구하게 되면 모든 정점 쌍 사이의 최단거리를 구할 수 있다. 2 예제바뀐 곳은 느낌표를 썼다. 초기상태0623inf60infinf32inf0in..

1 다익스트라 다익스트라를 배우기 전에 우선순위 큐를 배워야 한다. 다익스트라는 모든 간선의 가중치가 음수가 아닐 때 특정 노드에서 다른 모든 노드로 갈 때 최단거리를 구하기 위한 방법이다. 시간복잡도는 O(E + VlogV)이다. (E : 노드의 수, V : 간선의 수)  2개의 자료구조를 이용한다. 특정 노드에서 다른 노드로 갈 때의 거리를 기록하는 배열이 하나 필요하다. 이 배열의 무한대의 값으로 초기화한다. 그리고 우선순위 큐가 필요하다. 작동방식은 먼저 시작노드를 큐에 삽입한다. 큐에 삽입할 때는 (노드 번호, 추출한 노드까지의 거리+간선의 가중치)로 삽입한다. 다만 처음에는 (노드 번호, 0)으로 넣는다. 큐 안에서 노드를 꺼내고 배열에 기록된 거리보다 더 짧다면 기록한 후 꺼낸 노드와 연결된..

1 DFS DFS는 그래프를 탐색하는 방법 중 하나인데 깊이를 우선으로 탐색하는 기법이다. 동작 방법 - 노드를 방문했을 때는 방문을 했다는 표시를 남기고 선택한 노드를 스택에 넣는다. 1. 시작할 노드를 선택하고 방문한다.  2. 그 노드에 연결된 노드중 하나를 선택한다 . 그러면 그 노드에도 연결된 노드가 있을 것이니 연결된 노드에 방문한다. 3. 그 후에 더 이상 방문하지 않았던 노드가 없을 때 스택에서 현재 노드를 빼고 젤 위에 있는 그 전 노드에서 방문하지 않았던 노드에 방문한다. 4. 이 행동을 스택이 모두 빌 때까지 반복한다. 2 예 노드 1부터 DFS를 해보겠다. 노드 1 방문 후 스택에 삽입 스택의 최상단에 있는 노드 1과 연결되면서 방문하지 않았던 노드 3 방문 후 스택에 삽입 스택의 ..

1 BFS BFS는 그래프를 탐색하는 방법 중 하나인데 너비를 우선으로 탐색하는 기법이다. 동작 방법 - 노드를 방문했을 때는 방문을 했다는 표시를 남기고 선택한 노드를 큐에 넣는다. 1. 시작할 노드를 선택하고 방문한다.  2. 큐에 들어간 노드를 하나 꺼내고 그 노드와 연결된 방문하지 않았던 노드를 방문한다. 3. 큐가 빌 때까지 반복한다.  BFS는 가중치 없는 그래프일 때 최단거리를 구하는 용도로 사용된다.  DFS에 비해 큐를 사용하기 때문에 메모리를 더 잡아먹는다.2 예 위의 그림과 같은 그래프가 있다고 하자. 노드 1부터 BFS를 시작하겠다. 노드 1 방문 후 큐에 삽입 큐에서 노드 1 추출, 노드 1과 연결되면서 방문차지 않은 노드 3과 노드 4 방문 후 큐에 삽입 큐에서 노드 3 추출, ..

1 이분 탐색 이분 탐색은 정렬된 배열에서 값을 찾기 위한 알고리즘으로 값을 배열의 중간값과 비교하고 값이 놓일 수 없는 절반을 제거하고 나머지 절반에 대하여 검색을 계속하는 것을 값을 찾을 때까지 한다. 그림으로 나타내 보면 아래와 같다.2 시간복잡도 시간복잡도는 O(log n)으로 첫 항부터 끝 항까지 탐색하는 순차 검색 알고리즘의 시간복잡도인 O(n)에 비해 훨씬 빠르다.   3 코드#include int main() { int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} int left, right mid; int val = 8; // 찾을려는 값 while (left arr[mid]) { // 찾을려는 값이 더 크다면 ..