CS/Algorithm (52) 썸네일형 리스트형 패스트캠퍼스 챌린지 20일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. Prem's Algorithm 구현 오늘은 대표적인 최소 신장 트리 알고리즘으로 Prem's Algorithm을 구현했다. 프림 알고리즘은 시작 정점을 선택하고, 정점에 인접한 간선들 중 최소 간선으로 연결된 정점을 선택, 해당 정점에서 다시 최소 간선과 정점을 선택해나가며 트리를 확장해나가는 방식이다. Kruskal's Algoritm과 차이점 둘 모두 탐욕 알고리즘을 기초로 하여 구현되었지만, 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택하면서 연결해나가지만, 프림 알고리즘은 특정한 정점을 선택한 뒤에 이에 맞춰 연결해나가는 방식이다. 알고리즘 구현 알고리즘을 구현하기에 앞서 col.. 패스트캠퍼스 챌린지 19일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. kruskal 알고리즘의 첫 번째 단계에서 필요한 자료형으로 딕셔너리를 생성해준다. parent는 독립적인 원소들의 집합으로, 초기화를 해줄 때 그래프의 각 정점들이 입력되고, rank에서는 이 정점들의 높이 값을 0으로 초기화하여 입력시켜준다. kruskal에서 그래프의 모든 정점들을 독립적인 원소에 대한 집합과 나눠진 원소들에 대한 rank 값을 초기화한다. find 함수는 path compression 기법을 사용한다. 노드 자신과 부모 노드의 값을 확인한다. 같다면 그대로 노드 자신이자 부모 노드의 값을 반환한다. 다르다면 조건문을 통해 값을 입력한다(하지만 똑같은 값을 입력하는데 왜 .. 패스트캠퍼스 챌린지 18일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 신장트리 Spanning Tree라 불리우기도 한다. 원래의 그래프의 모든 노드가 연결되어 있으면서도 트리의 속성을 만족하는 그래프이다. 본래의 그래프의 모든 노드를 포함해야하며 모든 노드는 서로 연결되어 있다. 하지만 사이클이 존재하지 않아야 한다. 최소 신장 트리 Minimum Spanning Tree, MST라고 불리운다. 가능한 Spanning Tree 중, 간선의 가중치 합이 최소인 Spanning Tree를 의미한다. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘 가중치 그래프에서 최소 가.. 패스트캠퍼스 챌린지 17일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 오늘은 개념 학습으로 병합 정렬부터 최단 경로 문제까지 빠르게 학습해보았다. 내일은 나머지 개념 강의를 들은 후 자료구조에서부터 복습할 예정이다. 병합 정렬(merge sort) reculsive call를 활용한 정렬 알고리즘이다. 병합 정렬 알고리즘은 리스트를 절반으로 잘라 비슷한 크기로 두 부분을 나눈다. 그리고 이 리스트를 다시 재귀적으로 합병 정렬을 이용해 정렬한다. 다음 두 부분의 리스트를 하나의 정렬된 리스트로 합병한다. 시간 복잡도 분석 병합 정렬의 시간 복잡도 O(n log n)인데 이에 대한 분석은 쉽지 않다고 한다. 분할하는 과정에서 log n개의 단계로 생성되어 O(log.. 패스트캠퍼스 챌린지 16일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 퀵 정렬(quick sort) 정렬 알고리즘의 꽃이라고 한다. 기준점이 되는 피봇(pivot)을 선택하고, 이보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킨다. 이렇게 되면 피봇을 기준으로 작은 값, 피봇, 큰 값으로 세 분류로 나눠지는데 이는 다시 재귀함수로 적용해서 분류되는 데이터가 1개가 될 때까지 계속 반복한다. 이렇게 분류시켜 나누면 다시 역으로 합치는 과정을 거치면 정렬이 끝나게 된다. 코드로 구현한 값이다. 퀵 정렬은 reculsive call로 구현해야하는데 아직 낯선 개념이라 애를 좀 먹었다. 먼저 수도 코드를 작성한 뒤 기준 점을 잡고, 이를 기준으로 데이터를 비교해서 값.. 패스트캠퍼스 챌린지 15일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 오늘은 기본 정렬 알고리즘을 비롯해서 재귀 용법, 동적 계획법과 분할 정복에 대해서 공부했는데 평소보다 많은 시간을 투자했다. 알고리즘을 비롯해서 공부할 과목이 여러가지다 보니까 노력이 분산되는 느낌이 들어 이번 주부터는 알고리즘에 집중하기로 결정했다. 특정 수준에 오르면 다른 과목도 함께 공부할 예정이다. 삽입 정렬(Insert Sort) 삽입 정렬은 값을 삽입시키며 데이터를 정렬하는 알고리즘이다. 정렬은 두 번째 인덱스(A)에서부터 앞 인덱스의 값과 비교하는 것으로 시작된다. 앞에 있는 데이터(B)와 비교했을 때 해당 값(B)이 더 크다면 이 값을 뒤 인덱스로 보내고 작은 값이 앞으로 삽입.. 패스트캠퍼스 챌린지 14일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 알고리즘 연습방법 알고리즘을 익히기 위해서는 잘 작성된 알고리즘을 이해하고 스스로 만들어 봐야한다. 이를 위해 강의에서 추천하는 연습 방법은 다음과 같다. 1. 연습장과 펜을 이용한다. 2. 알고리즘 문제를 읽고 분석해서, 간단한 경우에서 복잡한 경우로 순서대로 생각한다. 3. 가능한 알고리즘이라면 구현할 알고리즘을 세부 항목으로 나눈다. 4. 데이터 구조나 사용할 변수를 정리하고 코드화한다. 5. 각 문장을 코드 레벨로 적는다. 6. 데이터 구조나 사용할 변수가 어떻게 변하는지 적으면서, 임의 데이터로 코드가 정상 동작하는지 검증한다. 글로는 와닿지 않아 참고할만한 영상을 찾아봤다. http.. 패스트캠퍼스 챌린지 13일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 힙이란 무엇일까? 힙은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조이다. 완전 이진 트리(Complete Binary Tree)로 노드를 삽입할 때 좌측 최하단의 노드에서부터 차례대로 삽입한다. 힙을 사용하는 이유는 시간 복잡도 때문이다. 기존의 배열에서는 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(n)이 소요되지만, 힙의 경우에는 O(log n)이 소요되므로 효율성이 좋다. 우선순위 큐처럼 최댓값 또는 최솟값을 빠르게 찾기 위한 자료구조 및 알고리즘 구현에 활용되어진다. 힙의 구조 힙은 최댓값을 구하기 위한 구조(Max Heap)와 최솟값을 구하기 위한 구조(Min Heap)로 분.. 이전 1 2 3 4 5 6 7 다음
