노는 게 제일 좋아

삽입 정렬은 딱 느낌에도 삽입해서 만드니까 삽입정렬이다. 하지만 역시 느리다. 말로 표현하자면 #include int main(void){ int i, j, temp; int array[10] = {1,3,5,7,9,10,8,6,4,2}; for(i = 0; i = 0 && array[j] > array[j + 1]) { //이미 정렬되어 있는 상태라면 while문을 안들어감 temp = array[j] //크면 옆의 인덱스와 값을 바꾼다. 때문에. 바꿔진 값에 대해서도 while문 안에서 계속 비교해서 위치를 알려준다. array[j] = array[j+1] array[j+1] = temp; j--; } } return 0; ..

이번에 버블정렬은 가장 가까운 것과 비교해 작으면 왼쪽으로 크면 오른쪽으로 보내는 정렬이다. 구현하기는 딱봐도 쉽다. 하지만 딱봐도 정렬 드럽게 안될 것 같다. #include int main(void){ int i, j, temp; int array[10] = {1,3,5,7,9,10,8,6,4,2}; for(i = 0; i array[j+1]){ // 다음 인덱스와 비교해서 왼쪽에 있는 값이 더 크면 temp = array[j] array[j] = array[j+1] array[j+1] = temp; // 오른쪽으로 보냄 // 결국 맨 오른쪽 값이 가장 큰 값이 됨. } } } return 0; } 각 싸이..

정말 정말 고대하고 기대하고 기다렸던 매우 아주 심히 중요한 정렬을 배울 단계과 왔다. 사실 해싱에서 살짝 건드리기는 했지만 해싱은 조금 달라보여서 다르게 정리했고 여기서는 진짜 데이터를 정렬하는 시간을 가져보자. 정렬이란 어떠한 기준을 삼아서 오름차순 또는 내림차순으로 자료를 나열하는 것이다. 어떠한 기준이란 대부분(숫자)가 대신한다. 여기서 다시 레코드랑 필드를 다시 정의해볼건데 복습이라고 생각하자 ㅎㅎ 어차피 데이터 배우면 항상 나옴 결국 저기 key 값이 기준이 되어서 정렬을 하는 거시다 ㅎㅎ 그런데 어떻게 정렬할 것이냐????????? 를 이제부터 알아볼 건데 여러가지의 방법이 있다. 그니까 정렬마다 장단점이 있어서 그렇게 여러 방법을 고안해낸 것이다. 모든 경우에 대해 최적인 정렬 알고리즘은 ..

저번 글을 너무 힘들게 써가지고,, 이건 좀 간단하게 해야 것습니다. 앞에 배운 Dijkstra와의 차이점은 얘는 실행하면 모든 정점사이의 최단경로를 한꺼번에 찾아준다는 것인디 어떻게 구성하느냐? 2차원 배열 A를 이용하여 3중 반복을 하는 루프로 구성 하는데 이게 무슨말이냐 하면은 그냥 반복한다는 것이다.ㅋㅋ •배열 A의 초기 값은 인접 행렬 weight •인접 행렬 weight 구성 1. i==j이면, weight[i][j]=0 2. 두 정점 i, j 사이에 간선이 존재하지 않으면, weight[i][j]=∞ 3. i, j 사이에 간선이 존재하면, weight[i][j]는 간선 (i, j)의 가중치 말보다 더 간단히 하자면 이런식이라는 것인데 조금 어려울 수 있으니 풀어서 설명해보자면 Ak [i][j..

이제 우리가 가장 친숙한 가중치 그래프의 응용이 나올건데 바로바로 최단경로( shortest path) 를 배울겁니다. 보통 최단 거리, 최소 시간, 최소 비용 등등 뭐 가중치마다 다르게 설정되니까 각각 알아내면 되겠지? 아무튼 얘가 우리가 실생활에서 접하는 진짜 필요한거지 ㅋㅋㅋ 이런식으로 설정되어 있다면,,? - 경로1: (A,B,C,D): 비용 = 7 + 4 + 2 = 13 - 경로2: (A,E,B,C,D): 비용 = 3 + 2 + 4 + 2 = 11 - 경로3: (A,F,B,D): 비용 = 10 + 6 + 10 = 26 경로1이 최소비용을 가진 경로고 사용자에게 추천을 하겠지?? 이제 들어가기 전에! 여기에도 MST와 비슷하게 2가지 알고리즘이 있어,,, 우선 이름을 알아보자면 Dijkstra 와..

이제 Prim 알고리즘에 대해서 알아볼 시간을 가질건데 짧게 말하자면 하나의 정점부터 시작하는 것은 같지만 앞에 배웠던 Kruskal과 다르게 트리에서 확장시켜 나가는 것이다. Kruskal은 그냥 간선을 오름차순으로 고르면서 나갔다면 Prim은 선택한 정점들이 기준이 되는것이다. 즉 n-1번 수행하면 n개의 정점과 이어져서 반복이 끝나고 최소비용 신장트리가 완성될 것이다. 알고리즘은 이렇게 되고 ㅊ은 오타인데 ㅋㅋㅋ 이미 넣어서 귀찮음 그림으로 표현하자면 이런식이다. 코드로 알아본다면 조금 추가해야할 부분이 생기는데 현재까지의 정점들 중에서 가장 가까운 정점을 찾는 과정인데 그래야 트리 기준으로 MST를 만들지 그치? 그래서 dist[]라는 배열을 쓸건디 dist[i]는 현재의 MST에서 i번째 정점까..

그래프에 대해서 많이 배웠는데 이제 진짜로 적용하려면 가중치 그래프라는 것을 배워야한다. 영어로는 위에 제목에 써놨다. 가중치 그래프라는 것은 간선에 비용이나 가중치가 추가된 그래프를 말하는데 이는 정점 사이의 연결상태뿐만 아니라 연결에 필요한 비용까지 함께 표현할 수 있다. 여기서 비용이란 꼭 돈이아니라 무엇이든 될 수 있는거다. 정말 돈이 될 수도, 아니면 간선의 길이가 될 수도 있는 것이다. 이렇게 도로를 표현하는 그래프에서는 도로의 길이를 표현하면 좋겠지?? 뭐 이렇게 지도로도 쓰일 수 있고, 사실 네트워크같은 곳에 많이 쓰인다고 한다. 예를 들어 지도에서 최단거리를 가고싶다..? 그렇다면 목적지까지 경로에서 가중치의 합이 가장 적은 경로가 가장 최단거리가 되겠지?? 우선 그렇다면 가중치 그래프를..

탐색을 배웠는데, 이제 탐색도 응용해봐야 하는데 이게 좀 중요한 내용이다. 연결 성분이라는 것인데 connected component 라고 한다. 최대로 연결된 부분 그래프를 말한다. 연결성분을 찾기 위해서는 앞에서 배웠던 깊이, 너비 우선 탐색을 모두 이용할 수 있는데 상관없다. 그렇지만 예를 들어서 깊이 우선 탐색을 해보자 먼저 임의의 정점을 선택, 깊이우선탐색을 통해 연결되어 있는 모든 정점을 출력한다. 더 이상 연결된 정점이 없으면 그래프에서 아직 방문되지 않은 다른 정점을 선택해 반복한다. 이 과정을 그래프의 모든 정점이 방문될 때 까지 방문하면 모든 연결 성분을 찾을 수 있다. 연결 성분 탐색을 위해서는 각 정점마다 저런식으로 111 22 이렇게 저장하려면 저러한 번호를 저장할 공간이 필요한데..

그래프의 탐색은 가장 기본이라고 할 수 있을거야. 그럼에도 조금 나중에 배우는 이유는 제일 중요해서 그래 기본이 가장 중요한거지 그래프에서 탐색은 특정한 것을 찾는다기보다는 "시작 정점부터 차례대로 모든 정점들을 한 번씩 방문" 을 의미해 또한 연결되었는지 안되어있는지가 중요한 회로같은 경우 탐색만으로도 문제를 발견할 수 있는거지 •도로망 예: 특정 도시에서 다른 도시로 갈 수 있는지 여부 •전자회로 예: 특정 단자와 다른 단자의 연결 여부 우선 탐색에는 2가지 정도가 있어. 1. 깊이우선탐색(Depth First Search) DFS 2. 너비우선탐색(Breadth First Search) BFS 이렇게 2가지가 있는데 비교는 이제부터 할거야 1. 깊이우선탐색 깊이부터 가자 갈수 있을 때까지 계속 가다..

이번에는 배열이 아닌 연결리스트로 구현할건데 뭐 그래프의 목적 자체는 똑같으니까 그렇게 어렵지는 않아. 오히려 더 쉬울수도 있다? 이런식으로 만드는거다? 어 근데 연결리스트에는 순서가 있는데 어떻게 하냐고?? 순서는 상관없어ㅋㅋㅋㅋ 그리고 무방향그래프인 경우에는 조금 번거로운게 a와 b가 이어져있다면 b와 a도 이어져있는 거겠지?? 그래서 그런 것 또한 고려해줘야할 필요가 있지. 이런 식으로 간선 없는 것들도 이렇게 표현하고 방향그래프면 이렇게 할 수 있고 그러면 코드랑 같이 보자. 이런식으로? 짤 수 있어 이제 무방향일 때는 간선 2개 만들어야하는 것도 잊지말고 이런식으로 짜면 된다 이제 더 연산에 대해 알아볼건데 탐색은 조금 특별해서 다음 글에서 알아보자.. 내가 쓴 코드가 전부가 아니니,, 원하는 ..