본문 바로가기

컴퓨터공학기초 개념/알고리즘 개념38

Brute-Force 알고리즘(완전탐색) 1. Brute-Force 알고리즘이란? - 브루트 포스 알고리즘은 이름의 뜻 처럼, 무식하게 푸는 방법이다. - 브루트 포스 알고리즘은 모든 경우의 수를 파악하여 문제를 푸는 방법이다. 이를 완전탐색이라고 부르기도 한다. - 예를 들어, 4자리 비밀번호를 푸는 문제가 있다면 0000부터 시작해서 비밀번호가 맞을 때까지 모든 조합을 확인해보는 방법이다. 2. Brute-Force(완전탐색)을 푸는 방법 - 완전탐색 문제를 푸는 알고리즘은 다음과 같다. ▶ 순열 ▶ 백트래킹 ▶ BFS - 문제의 접근 방법에 따라 활용할 수 있는 방법이 위의 3가지로 나뉜다. 3. 완전탐색을 구현하기 전에 - 완전탐색을 구현할 때는, 다음의 요소들을 주의해야 한다. ▶ 입력과 출력의 제한을 파악하자. - 모든 경우의 수를 .. 2021. 8. 18.
람다(lambda)란 무엇인가? - 알고리즘 공부를 하다보면 람다(lambda)라는 식을 자주 접하게 된다. - 도대체 람다가 무엇인지 같이 알아보자. 1. 개념 람다는 어떤 함수의 매개변수로 다른 함수를 넣고 싶을 때 사용한다. 람다는 anonymous function 이라는 명칭을 갖고 있다. 선언 없이 또는 이름 없이 사용할 수 있는 함수다. 람다의 특징은 일회성이다. 함수의 선언부가 없으므로, 한번 사용하면 그걸로 끝이다. 람다의 핵심은 지연실행 또는 지연연산이다. 이는 필요할 때만 호출하여 사용하는 방식으로 메모리상의 불필요한 연산을 줄인다는 것을 의미한다.(장점) 2. 사용법 - 예시코드를 보면서 사용법을 익혀보자. print((lambda x, y, z : x + y + z)(1, 1, 1)) a) anonymous fun.. 2021. 4. 16.
Algorithm - 알고리즘 핵심정리 1. 정의 알고리즘이란? 어떤 문제를 해결하기 위해 사용되는 풀이과정을 말한다. 즉, 문제해결방법이다. 수학에서 한 문제에 대해 여러가지 풀이법이 존재하는 것처럼, 프로그래밍 또한 한 문제에 대해 여러 풀이법이 존재한다. 여러가지 풀이법 중 가장 효율이 좋은 방법을 어떤 문제에 대한 알고리즘이라고 한다. 수학의 공식처럼, 특정 형태 또는 구조를 갖는 프로그래밍 문제에는 공식화된 알고리즘이 존재한다. 2. 알고리즘의 종류 a) 정렬(Sort) 1. 버블정렬(Bubble) 인접한 두 데이터의 크기를 비교하여 정렬하는 알고리즘 2. 선택 정렬(Selection) 주어진 데이터 중 최소값을 찾아 순서대로 정렬하는 알고리즘 후보군 중 최소값을 찾아낸 후, 맨 앞의 데이터와 교체한다. 교체된 맨 앞의 데이터를 제외.. 2020. 10. 7.
Algorithm - 자료구조 핵심정리 1. 정의 a) 자료구조란? 대량의 데이터를 효율적으로 관리하기 위해, 데이터를 저장 및 정렬하는 방식을 말한다. 데이터를 어떤 방식으로 저장하고 정렬하느냐에 따라 추출 방식 등 데이터를 처리 및 조작하는데 필요한 코드가 달라진다. 2. 자료구조 (Data Structure) a) 배열(Array) 한가지 데이터 타입의 데이터를 순차적으로 저장 및 정렬하는 자료구조 각 데이터마다 index를 부여하여 데이터 검색에 용이(장점) 배열은 크기가 고정적(단점) 데이터가 삭제되면 배열 전체의 데이터를 재정렬(단점) b) 큐(Queue) FIFO(First In, First Out)방식으로 데이터를 저장 및 정렬하는 자료구조 FIFO방식으로 인해 데이터 삭제시, 재정렬이 필요없다. 운영체제(OS)에서 프로세스 스.. 2020. 10. 6.
Advanced Algorithm - Backtracking 1. 백트래킹이란? - 완전탐색 알고리즘의 하나다. - 완전탐색을 하는 도중, 현재의 탐색이 무의미하다고 판단이되면 되돌아가는 알고리즘이다. - 그래서 퇴각 검색이라 부르기도 한다. 2. 백트래킹의 로직 - 백트래킹은 제약조건 만족 문제(Constraint Satisfaction Problem)에서 해를 찾기 위한 전략이다. 해를 찾기위해서 어떤 후보군을 대상으로 제약조건을 체크하다가 해당 후보군이 제약조건을 만족할 수 없다고 판단되면, 그 즉시 backtrack(다시는 해당 후보군을 체크하지 않을 것을 표시)한 후, 다른 후보군으로 넘어가는 방식으로 최종적으로 최적의 해를 찾는 전략이다. 백트래킹 전략에 의해 연산의 대상이 되는 후보군이 적어지고, 그만큼 시간복잡도가 줄어드는 것이다. a) 어떻게 구현.. 2020. 10. 5.
Advanced Algorithm - MST(Improved Prim's Algorithm)(6) 1. 개선된 프림 알고리즘이란? - 기존의 프림 알고리즘에서 파생된 알고리즘으로, 개선된 프림 알고리즘은 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식이다. 그렇다면 무엇이 개선되었을까? - 이전 포스팅에서 다뤘던 기본적인 프림 알고리즘은 간선을 기준으로, 간선의 개수에 따른 while문의 반복회수를 측정하여 E log E 만큼의 시간복잡도를 갖는다. - 이와는 다르게, 개선된 프림 알고리즘은 노드를 기준으로 하여 E log V 만큼의 시간복잡도를 갖는다. 그래프는 노드의 수 보다 간선의 수가 더 많기 때문에 그 차이만큼 반복회수가 줄어들어 알고리즘의 시간복잡도가 개선됨을 의미한다. 2. 개선된 프림 알고리즘의 로직 - 개선된 프림 알고리즘은 노드마다 key값을 갖고 있는 것이 특징이다. 로직.. 2020. 10. 4.
Advanced Algorithm - MST(Prim's Algorithm)(5) 1. 프림 알고리즘 코드구현 a) 기본그래프 구현 - 중복된 간선 정보를 제거한다. ex) (7, 'A', 'B')와 (7, 'B', 'A')는 동일하다. myedges = [ (7, 'A', 'B'), (5, 'A', 'D'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (5, 'C', 'E'), (7, 'D', 'E'), (6, 'D', 'F'), (8, 'E', 'F'), (9, 'E', 'G'), (11, 'F', 'G') ] b) 프림 알고리즘 로직구현 1. 그래프의 모든 간선정보를 저장한다. (adjacent_edges) 2. 임의의 노드를 선택하여 '연결된 노드 집합' 이라는 리스트에 삽입한다. (connected_nodes) 3. 2단계에서 선택된 노드.. 2020. 10. 3.
Advanced Algorithm - MST(Prim's Algorithm)(4) 1. 프림 알고리즘이란? - 대표적인 최소신장 알고리즘 중 하나이다.(Kruskal's Algorithm & Prim's Algorithm) a) 크루스칼 알고리즘과 프림 알고리즘의 비교 크루스칼 알고리즘은 전체 간선을 가중치 기준으로 오름차순 정렬하여, 낮은 가중치를 가진 간선이면서 동시에 사이클이 발생하지 않는 노드를 연결시켜 MST(최소신장트리)를 구하는 알고리즘이다. 프림 알고리즘은 어떤 노드와 인접한 노드의 간선만을 대상으로 하여, 인접노드 중에서 간선의 가중치가 가장 작은 간선을 선택하여 해당 인접노드를 연결하는 방식으로 MST를 구한다. 두 알고리즘 모두 탐욕 알고리즘을 기반하고 있다.(당장을 위한 최소비용을 선택하여 결과적으로 최적의 솔루션을 찾음) b) 프림 알고리즘의 로직 임의의 노드를.. 2020. 10. 2.
Advanced Algorithm - MST(Kruskal's Algorithm)(3) 1. 크루스칼 알고리즘의 구현 1) 기본 그래프의 구현 - 아래의 그림과 같은 기본 그래프를 딕셔너리를 이용하여 구현한다. mygraph = { 'vertices':['A', 'B', 'C', 'D', 'E', 'F', 'G'], 'edges':[ (7, 'A', 'B'), (5, 'A', 'D'), (7, 'B', 'A'), (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'), (8, 'C', 'B'), (5, 'C', 'E'), (5, 'D', 'A'), (9, 'D', 'B'), (7, 'D', 'E'), (6, 'D', 'F'), (7, 'E', 'B'), (5, 'E', 'C'), (7, 'E', 'D'), (8, 'E', 'F'), (9, 'E', 'G'), (6, .. 2020. 10. 1.

티스토리툴바