그래프 탐색 알고리즘에는 대표적으로 BFS 와 DFS 가 있다. 본 글에서는 아래 그래프를 가지고, BFS 와 DFS 의 탐색 알고리즘을 살펴본다. BFS 너비 우선 탐색을 BFS라 부르고, Breadth Frist Search 의 약자이다. 해당 노드와 같은 레벨(Level)의 노드를 먼저 탐색을 하기 때문에 붙여진 이름이다. 위 그래프를 예로 탐색 순서를 나열하면, 아래와 같은 순서로 탐색을 하게된다. A - B - C - D - E - F - G - H - I - J - K - L - M 코드 아래 코드는 unittest 기반으로 작성했다. 알고리즘은 bfs() 메소드를 참고한다. # -*- coding: utf-8 -*- import unittest def bfs(graph, start): """..
Palindrome 팰린드롬은 한국말로 회문이라고 한다. 회문은 거꾸로 읽어도 같은 문자열이 되는 문자열을 말한다. 예를들어서, "mom", "bob", "12321" 과 같은 문자열을 말한다. 팰린드롬을 확인하는 방법은 여러가지가 있겠지만, 큐와 스택의 특성을 이용하면 쉽게 찾을 수 있다. 큐는 FIFO 특징을 가지고 있고, 스택은 LIFO 특징을 가지고 있다. 큐와 스택에 대한 개념은 아래글을 참고한다. 2020/03/28 - [Algorithm] - 큐(Queue) 와 스택(Stack) 자료구조 로직(Logic) 큐와 스택에 각각 문자열을 담는다. 큐에서 꺼낸값과 스택에서 꺼낸값이 모두 같다면 회문이다. 예를들어서, 12321 이라는 회문이 있을때, 큐와 스택에 각각 담는다. => queue: 12..
이진 탐색 알고리즘 이진 탐색(Binary Search) 알고리즘은 순차 탐색 알고리즘보다 더 빠르게 탐색할 수 있다. 빠르게 탐색할 수 있는 이유는 둘로 분할(이분)하여 탐색하기 때문이다. 예를들어, 1000페이지까지 있는 책이 있을때 630페이지를 찾으려고 한다. 우리는 대충 책을 펼쳐서 페이지를 확인한다. 그때 500페이지라면 630 페이지는 500페이지보다 뒤에 있으므로 앞 페이지를 살펴볼 필요가 없어진다. 하지만, 이진 탐색을 하려면 위 예제와 같이 탐색할 데이터 그룹이 정렬이 되어 있어야한다는 조건이 있다. 코딩 반으로 나누어서 중간 값과 목표값(target)을 비교한다. 같다: 인덱스를 반환한다. 목표값이 중간값보다 작다: 중간값의 인덱스보다 작은 왼쪽에서 다시 찾는다. (오른쪽은 버려도된다..
파이썬 정렬 메소드 파이썬에서는 정렬을 할때 sort() 와 sorted() 메소드를 사용한다. sort() sort() 메소드는 리스트를 오른차순으로 정렬해준다. >>> data = [3, 6, 12, 7, 10, 99, 23, 5, 9] >>> data.sort() >>> data [3, 5, 6, 7, 9, 10, 12, 23, 99] sorted() sorted() 메소드는 오름차순으로 정렬 후 새로운 리스트를 반환해준다. >>> data = [3, 6, 12, 7, 10, 99, 23, 5, 9] >>> sorted(data) [3, 5, 6, 7, 9, 10, 12, 23, 99] 파이썬에서는 어떤 정렬 알고리즘을 사용할까? 흔히 알고리즘을 배우면 아래 5가지 정렬 알고리즘을 배운다. 선택 정..
정렬 정렬(sort)은 자료의 크기를 순서대로 나열하는 것을 뜻한다. 예를들어 아래와 같은 경우를 말한다. • 입력: 정렬할 리스트(예: [35, 9, 2, 85, 17]) • 출력: 순서대로 정렬된 리스트(예: [2, 9, 17, 35, 85]) 선택 정렬 정렬에는 여러가지 방법이 있는데, 본 글은 선택 정렬(Selection Sort)에 대한 내용이다. 다른 방법의 정렬 알고리즘은 아래 글을 참고한다. 2020/03/21 - [Algorithm] - 삽입 정렬 (Insertion Sort) 알고리즘 (with Python3) 2020/03/25 - [Algorithm] - 병합 정렬 (Merge Sort) 알고리즘 (with Python3) 2020/03/25 - [Algorithm] - 퀵 정렬 (..
중복을 제거할때는 set 집합을 이용한다. 집합의 특징 중복이 없다. (집합 내의 원소들은 서로 다른 원소를 가진다) 순서가 없다. (원소간의 순서를 가지지 않는다) 중복된 원소를 제거할때, 집합(set)을 이용하면 효율적이다. 예제. 동명이인 찾기 n 명의 주어진 이름들이 있을때, 동명이인인 이름을 찾는다. 예제 입력: Tom Mike Jerry Tom 예제 출력: Tom 코드 2가지 방법으로 풀어볼 수 있다. test1() 메소드와 같이 집합을 이용하는 방법. test2() 메소드와 같이 하나 하나 모두다 비교해서 답을 찾는 방법. # -*- coding: utf-8 -*- import unittest class Exam03(unittest.TestCase): """n 명의 주어진 이름들이 있을때, ..
최댓값 찾기 최댓값을 찾는 알고리즘 상당히 간단한 알고리즘이다. (하나하나 비교하면 됨) 하나씩 비교를 하다보니 시간복잡도는 O(n)이 된다. 코드 본 글에서는 unittest를 이용하여 알고리즘을 풀이합니다. 로직이 달라지는것은 아닙니다. 사실 파이썬에는 max() 라는 내장함수를 제공해주는데, max([5, 3, 2]) 안에 숫자로 구성된 리스트를 넣어주면 알아서 최댓값을 반환해준다. # -*- coding: utf-8 -*- import unittest class Exam02(unittest.TestCase): @classmethod def setUpClass(cls) -> None: cls.items = [10, 92, 4, 7, 44, 80, 98, 50, 74, 32] ...생략... def ..
본 글은 Python3.7 환경에서 진행합니다. unittest 로 작성되어 있지만, 알고리즘을 확인하는데는 문제가 없습니다. 단순히 더하는 방법 결론부터 이야기 하자면 이 방법은 비효율적이다. 1 부터 10 까지 더하는 알고리즘을 작성하면 아래와 같이 생각할 수 있다. 코드 test_sum 함수를 보자. # -*- coding: utf-8 -*- import unittest class Exam01(unittest.TestCase): def test_sum(self): """1 부터 n 까지 더하는 알고리즘""" answer = 0 # 정답 for _ in range(1, 11): answer += _ # 1 부터 10까지 더한다. self.assertEqual(answer, 55) if __name__..