728x90 공부/알고리즘28 버블 정렬 복습(Bubble Sort) 오늘은 버블 정렬에 대해 배워 보았습니다. 분명 1,2 학년때 다 한건데 3학년이 된 지금에서야 다시 복습을 하는게 바보같다는 생각이 들 때도 있지만 지금이라도 열심히 해야지라는 생각이 듭니다. 버블 정렬은 O(N^2) 인 세개의 정렬(선택,버블,삽입) 중에서도 가장 비효율적인 정렬입니다. 버블정렬은 무조건 옆에 요소와 비교하고 교환합니다. 여기서 무조건 교환을 하기 때문에 알고리즘의 비효율적인 부분이 커집니다. 애를 들어 설명해보겠습니다. 3 1 4 5 2 라는 배열이 존재합니다. 첫번째 첫번째 3 을 옆에 요소 1과 비교 합니다. 1이 더 크기 때문에 교환합니다. 1 3 4 5 2 그리고 두번째 수 3을 다시 4와 비교한 후 크면 교환합니다. 여기선 4보다 작기 때문에 교환을 하지는 않습니다. 1 3.. 2020. 5. 27. 선택정렬 복습 복습이라고 적은 이유는 이 노트가 컴공들의 선생님 같은 존재인 '나동빈' 선생님의 알고리즘 기초 강의를 보고 작성하는 거기 때문입니다. 선택정렬을 정렬 중에서 가장 기본이고 가장 비효율적인 정렬이라고 할 수 있습니다. 말로 풀어보자면 '가장 작은 수를 선택해서 앞에 수와 바꾼다' 인데요. 일단 가장 작은 수를 선택하기 위해서 배열을 다 돌아야하기 때문에 말로만 들어도 좀 비효율적인 느낌입니다. 그럼 예시를 들어보겠습니다. 다음과 같이 정렬되지 않은 배열이 있습니다. 3 4 1 5 2 배열을 쓱 보고 가장 작은 수를 선택합니다. 1입니다. 그럼 첫번째 수인 3과 교환해줍니다. 1 4 3 5 2 이제 1은 신경쓰지 않아도 됩니다. 2번째 수인 4부터 시작해서 가장 작은 수를 찾아봅니다. 처음부터 봐도 끝까지.. 2020. 5. 26. 탐욕 알고리즘(Greedy Algorithm) 안녕하세요. 부산 공수니 입니다. 오늘은 탐욕 알고리즘에 대해 알아보겠습니다. Dynamic Programming과 Divide and Conquer 과 더불어 중요하다고 판단이 되는 알고리즘입니다. 단어의 부정적인 부분 때문에 탐욕 알고리즘을 안 좋다고 생각할 수도 있지만 사실 탐욕 알고리즘이 효율적이고 간단한 경우도 많습니다. : 미리 정한 기준에 따라 가장 좋아보이는 답을 선택 ! 이는 동적 프로그래밍과 더불어 최적화 문제를 푸는데 사용됩니다. 상대적으로 탐욕 알고리즘이 설계하기 더 쉽습니다. 물론 이게 최적화된 알고리즘인지에 대한 증명이 반드시 필요합니다 .동적 프로그래밍은 재귀 관계식을 세워서 입력사례를 더 작은 입력사례로 분할하짐나 탐욕 알고리즘은 입력사례를 분할하지 않습니다. 그저 더 좋아보.. 2020. 5. 21. 서로소 집합 데이터 구조_Abstract Data Type 안녕하세요. 부산 공수니 입니다! 오늘은 서로소 집합 데이터 구조에 대해 알아보겠습니다. 그리디(Greedy) 알고리즘에서 크루스칼(kruscal) 알고리즘에서는 초기 자기자신의 마디(vertex))만 포함된 서로소 부분집합들을 만들고 모든 마디들이 같은 집합에 속할 때까지 되풀이 하여 부분 집합을 합병(merge) 합니다. 이 알고리즘 구현을 위해 서로소 집합에 대한 데이터 구조가 필요합니다. 추상 데이터구조(abstract data type)은 데이터 객체와 그 객체에 대한 연산으로 이루어집니다. 여기선 U 라는 구성요소의 전체영역(universe) 로 시작합니다. ( 글씨가 이쁘지 못한 점 양해 부탁드립니다.) 이 멤버로 부터 집합을 만드는데 필요한 프로시저가 makeset입니다. for(each .. 2020. 5. 20. 이전 1 ··· 4 5 6 7 다음 728x90
