my devlog;

MySQL ERROR 해결 과정 클론 코딩을 위해 IntelliJ로 MySQL을 연결하던 중 error 1045(28000) 때문에 localhost에 연결할 수 없다는 에러를 마주하였다. 구글링을 하면 나오는 에러의 원인은 다음과 같다. 아이디 또는 패스워드가 맞지 않음. user에 지정된 접속가능한 host가 아님. MySQL Workbench로 비밀번호를 새로 지정하고, host도 확인한 후였기 때문에 나는 양쪽 다 해당되지 않는 상황이었다. 결국 에러를 해결하지 못하고 MySQL server를 지웠다가 다시 설치하였는데 그 과정에서 다음과 같은 사항이 에러의 원인이었을 수도 있다는 생각이 들었다. 바로... 다른 task가 3306 port를 사용 중이었던 것이다! 이 사실을 MySQL serve..

해싱이란 ? 키값으로 직접 배열에 접근하는 것이 아니라, 키값을 해시 함수에 넣어서 나온 해시값을 가지고 해시테이블에 접근하여 원소를 탐색, 삽입, 제거하는 기법 예를 들어 array, binary, bubble, file, digit, direct, zero, bucket을 저장하려고 할 때, 첫 번째 글자를 키값으로 사용하여 a는 0, b는 1, c는 2와 같은 해시값을 할당한다. 해시값은 해시 테이블의 인덱스, 버킷 번호에 해당하기 때문에 각각의 값을 순서대로 삽입하면 해시 테이블은 다음의 그림과 같이 구성된다. 'bucket'은 주어진 슬롯이 다 찼기 때문에 해시 테이블에 삽입할 수 없고, 이와 같은 현상을 오버플로우라고 한다. 이러한 오버플로우를 해결하는 방법에는 크게 1. 개방주소법 , 2. ..

이진 트리, 이진 탐색 트리 개념 참고 : hyunah-home.tistory.com/entry/%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%84%B1%EC%A7%88-%EC%9A%B4%ED%96%89%EA%B3%BC-%EC%9D%91%EC%9A%A9-%EC%88%98%EC%8B%9D%ED%91%9C%ED%98%84-%ED%8A%B8%EB%A6%AC-%EC%9D%B4%EC%A7%84%ED%8A%B8%EB%A6%AC%EB%A1%9C%EC%9D%98-%EB%B3%80%ED%99%98%EB%B2%95-%EC%9D%B4%EC%A7%84%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC 이진트리의 성질, 운행과 응용; 수식표현 트리, 이진트리로의 변환법,..

탐색 : 여러 개의 자료 중에서 원하는 자료를 찾는 작업. 탐색 키로 항목을 서로 구별. 배열, 연결 리스트, 트리, 그래프, 해시 테이블 등을 사용 ① 순차 탐색 ▷ 아이디어 : 처음부터 마지막까지 하나씩 순차적으로 확인 ▷ 프로그램 int sequential_search(int key, int low, int high){ for(int i = low; i high) return -1; int middle = (low+high)/2; if (key == list[middle]) return middle; else if (key < list[middle]) return search_binary(key, low, middle-1); else return search_binary(key, middle+1, ..

참고 : 선택 정렬, 삽입 정렬, 버블 정렬https://hyunah-home.tistory.com/entry/%EA%B8%B0%EB%B3%B8-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%AC-%EC%82%BD%EC%9E%85%EC%A0%95%EB%A0%AC-%EB%B2%84%EB%B8%94%EC%A0%95%EB%A0%AC 기본 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 정렬 : 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것. 단순하지만 비효율적인 방법의 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 ① 선택 정렬 ▷ 아이디어 : 정렬된 리스트와 hyunah-home.t..

정렬 : 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것. 단순하지만 비효율적인 방법의 정렬 알고리즘 : 선택정렬, 삽입정렬, 버블정렬 ① 선택 정렬 ▷ 아이디어 : 정렬된 리스트와 정렬 안 된 리스트를 가정함. 정렬 안 된 리스트에서 최소값이나 최대값을 선택해 한쪽으로 몰아넣음. ▷ 알고리즘 ; 오름차순 정렬 기준 1. 오른쪽 리스트에서 최소값의 인덱스 선택 2. 오른쪽 리스트의 첫번째 수의 값과 최소값을 교환 3. 왼쪽 리스트 크기 1 증가, 오른쪽 리스트 크기 1 감소 4. 오른쪽 리스트가 소진될 때까지 1~3 과정 반복 ▷ 프로그램 void selection_sort(int list[], int n){ int least, temp; for (int i = 0; i < n-1; i++) {..

DAG(Directed Acyclic Graph) : 사이클이 없는 방향 그래프. DAG에서 에지 가 있다면 정점 u는 정점 v를 선행함. 위상 정렬(topological sort) : 방향 그래프 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 것. 선행관계가 없는 것은 뭐가 먼저 나오든지 상관이 없기 때문에 위상 정렬 결과는 여러 가지가 존재할 수 있음. ▷ 알고리즘 1. 진입차수가 0인 임의의 정점(선행자가 없는 정점)을 큐(혹은 스택)에 삽입 2. 정점 개수만큼 시행하는 반복문 생성 3. 반복문 내부에서는, 큐에서 정점을 하나씩 꺼내어 출력하고 출력한 정점에 붙어있는 에지들을 제거하여 진입차수 재계산 4. 진입차수를 재계산하여 진입차수가 0이 된 것은 큐에 삽입 위상정렬이 불..

최단 경로 : 그래프에서 정점 u로부터 정점 v로 가는 경로 중에서 에지들의 가중치 합이 최소가 되는 경로. 혹은 에지의 개수가 가장 적은 경로. 다익스트라 알고리즘 (Dijkstra Algorithm) : 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾을 수 있는 알고리즘. ▷ 아이디어 : 방문하지 않은 정점 중에서 가장 비용이 적은 에지로 연결된 정점을 방문. 시작 정점으로부터 해당 정점을 경유지로 하여 다른 정점을 방문하는 비용이 더 작다면, 최단 경로값을 갱신. 위의 그림에서 distance[u]가 distance[w]값보다 작아서 가장 비용이 적은 에지로 연결된 정점 u가 새롭게 추가되었다면(방문되었다면), 시작 정점 v로부터 해당 정점 u를 거쳐서 다른 정점인 w로 가는 비용을 계산한다..

스패닝 트리 (Spanning Tree) -> 연결 그래프 G의 스패닝(신장) 트리란, G의 모든 정점을 포함하는 부분 그래프로서의 트리. 모든 정점들이 연결되어 있어야 하며 사이클이 존재해서는 안 됨. n개의 정점을 갖는 스패닝 트리는 반드시 n-1개의 에지를 가짐. 최소 스패닝 트리(최소 신장 트리) -> 가중치 그래프의 스패닝 트리들 중에서 에지들의 가중치 합이 최소인 스패닝 트리. ▷ Prim의 MST 알고리즘 ○ 아이디어 : 스패닝 트리 집합의 인접 정점 중 최소 가중치로 연결된 정점을 추가하며 스패닝 트리 집합을 점진적으로 확장해 나가자! ○ 알고리즘 1. 임의의 시작 정점에서 출발. (대개 인덱스가 가장 작은 정점) 시작 정점을 스패닝 트리 집합(MST)에 추가. 2. MST에 인접한 정점 ..

▷ 개념 ○ 강한 연결 방향그래프(Strongly Connected Digraph) -> 어떤 두 정점을 잡든 간에 서로 연결이 되어 있는, 방향 경로가 존재하는 그래프. ○ 강한 연결 요소(Strongly Connected Component) -> 어떤 두 정점을 잡든 서로 도달할 수 있는 경로가 있는 부분 방향 그래프. 같은 강한 연결 요소에 속하는 정점들은 서로 이동할 수 있는 방향 경로가 반드시 존재함. 사이클이 발생한다면 무조건 SCC에 해당하며 강한 연결 방향 그래프는 강한 연결 요소가 오직 하나. SCC를 하나의 정점으로 고려하여 각 SCC를 위상 정렬할 수 있음. ▷ 알고리즘 ○ 타잔 알고리즘(Tarjan's Algorithm) · 개념 : 모든 정점에 대해 DFS를 수행하여 SCC를 찾는..