이번에는 그래프 탐색 알고리즘을 알아보자. 그래프 탐색 알고리즘은 미로 찾기 등등 여러가지 문제로 코딩 테스트에 등장하기도 한다. 바로 시작해보자. 우선 우리가 알아볼 그래프는 일단 이런 모양이다. A와 B, C, D를 각각 노드라고 부르고, 이러한 모양을 너무 대충 그렸지만 트리라고 부른다. A는 B와 연결되어 있다. B는 A, C, D와 연결되어 있다. C는 B와 연결되어 있다. D는 B와 연결되어 있다. 라고 표현할 수 있겠다. 자 그럼 파이썬으로 위 그래프를 표현해보자. graph = { 'A': ['B'], 'B': ['A', 'C', 'D'], 'C': ['B'], 'D': ['B'] } 딕셔너리에 key는 각 노드를, value에는 해당 노드에 연결되어 있는 노드를 저장하는 형태이다. 이게 ..

오늘은 Palindrome(회문) 찾기 알고리즘을 알아보자. 바로 시작해보자. 먼저 Palindrome(회문)이 무엇인가. 회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다. 즉, '기러기', '다시 합창합시다', '일요일', 'mom', 'wow'와 같이, 앞으로 읽어도 뒤로 읽어도 같은 단어나 문장 등등을 뜻한다고 한다. 그렇다면 Palindrome(회문) 찾기 알고리즘이란, 어떤 단어, 문장이 있을 때, 그 단어나 문장이 앞으로 읽어도 뒤로 읽어도 동일한가. 를 알아내는 알고리즘이 되겠다. 흠. 본능적으로 생각난 알고리즘을 작..

이번 시간에는 지금까지 알아본 여러가지 알고리즘의 성능을, Big O (빅오) 표기법으로 정리하면서 어떤 알고리즘이 더 효율적인 알고리즘인지 정리해보자. 바로 시작해보자. + 이 글에서는 알고리즘의 시간 복잡성만을 다룬다. + 시간 복잡성을, 입력값과 연산 횟수를 비교하며 알아볼 것이다. 우선 여태까지 알아본 알고리즘과 빅 오 표기법을 정리해보자. 1 ~ 10까지의 총 합을 구하는 알고리즘, O(1) 이분 탐색 알고리즘, O(log n) 최댓값, 최솟값 탐색 알고리즘, O(n) 병합 정렬 알고리즘, O(n log n) 삽입 정렬 알고르짐, O(n의 제곱) 하노이의 탑, O(2의 n제곱) - 이 알고리즘은 다루지 않았다. 그래서 이게 무슨 차이일까. 그래프를 보여주고 싶었지만, 표로 만족하도록 하자. n은..

이번에는 이분 탐색 알고리즘에 대해 알아보자. 이분 탐색 알고리즘을 작성, 구현해볼 것이다. 용어부터 찾아보자. 이분 탐색 알고리즘이란, 이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. 이라고 한다. 정리를 해보자면, 정렬된 리스트에서 특정..

이번에는 퀵 정렬을 알아보자. 이름은 퀵(Quick)이지만 빠르다는 의미는 아니다. 물론 상황에 따라 다른 정렬 알고리즘(삽입 정렬)보다 빠를 수는 있다. 바로 알아보자. 우리는 앞서 병합 정렬 알고리즘을 알아보았다. 빠르게 요약하자면, 정렬할 리스트를 절반으로 자르는 과정을 반복하여 가장 작은 단위서부터 비교 정렬하여 병합하는 방식이었다. 그러면 갑자기 왜 병합 정렬 이야기를 꺼내느냐. 지금 알아볼 퀵 정렬 역시 정렬할 리스트를 절반으로 자르는 과정을 반복한다. 근데 병합 정렬처럼 그냥 절반으로 자르는 것이 아닌, 하나의 기준 값을 가지고 두 개의 리스트로 자른다. 무슨 말인고 하니. nums = [5, 2, 1, 4, 0, 3, 9, 8, 7, 6] 오늘도 출현한 nums List로 퀵 정렬 알고리즘..

이번에 알아볼 알고리즘은. 병합 정렬 알고리즘이다. 저번에 살펴보았던 리스트 클래스 안의 sort 메서드의 작동 알고리즘이다. (물론 c 언어로 구현되어 있고, 약간의 튜닝이 들어간 듯 보이지만.) 적어도 O(2의 제곱)보다는 빠르니, Python 개발자들도 이 알고리즘을 베이스로 선택한 것이 아닐까. 몹시 궁금해진다. 너란 놈. 이 시간만을 기다렸다고. 병합 정렬이란, 합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. 이라고 적혀있다. 말로 설명하기 사실 조금 복잡하다. 위키백과에 첨부된 GIF를 ..

오늘 알아볼 정렬 알고리즘은. 삽입 정렬 알고리즘이다. 삽입 정렬이란, 말 그대로 하나씩 자리를 찾아 삽입하여 정렬한다는 것이다. 무슨 말인고 하니, nums = [5, 2, 1, 4, 0, 3, 9, 8, 7, 6] 이렇게 생긴 nums List로 삽입 정렬 알고리즘을 작성해 보자. 정렬한 데이터를 저장할 List를 만든다. nums List에서 맨 앞의 값을 빼낸다. 새로운 List에 저장한다. nums List에서 맨 앞의 값을 뺴낸다. 새로운 List에 들어간 값을 순회하며 값을 비교한다. 크다면 다음 위치로, 작다면 그 자리에 삽입한다. 새로운 List에서 가장 큰 값이라면 마지막에 삽입한다. 다시 4번으로 돌아간다. 구현해 보자. nums = [5, 2, 1, 4, 0, 3, 9, 8, 7, ..

오늘은 선택 정렬 알고리즘에 대해 알아보자. 선택 정렬이란, 순차적으로 작은(또는 큰) 값을 골라내 정렬을 하는 것이다. 무슨 말인고 하니, nums = [5, 2, 1, 4, 0, 3, 9, 8, 7, 6] 이렇게 생긴 nums List로 선택 정렬 알고리즘을 작성해 보자. 정렬한 데이터를 저장할 List를 만든다. 순차 탐색 알고리즘을 사용해 nums List에서 가장 작은 값을 찾는다. 찾아낸 가장 작은 값을 새로운 List에 저장한다. 찾아낸 가장 작은 값을 nums List에서 지운다. 다시 2번으로 돌아간다. 구현해 보자. nums = [5, 2, 1, 4, 0, 3, 9, 8, 7, 6] sorted_num = [] for _ in range(len(nums)): min_index = 0 f..

오랜만에 돌아온 알고리즘 시간. 오늘은 순차 탐색(검색) 알고리즘에 대해 알아보자. 바로 시작해 보자. 순차 탐색(검색) 알고리즘이란, 순차 검색 알고리즘(sequential search algorithm), 또는 선형 검색 알고리즘(linear search algorithm)은 리스트에서 특정한 값을 찾는 알고리즘의 하나다. 이것은 리스트에서 찾고자 하는 값을 맨 앞에서부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 비효율적이지만, 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다. 그렇다. 말 그대로 List의 처음부터 끝까지 순서대로, 내가 원하는 데이터를 검색할 때 사용하는 알고리즘이다. 길이가 100인 List에서 0을 찾는..