알고리듬 BFS(Breadth-first search)를 알아보겠습니다. BFS는 너비 우선 탐색인데요. 2진 트리가 있을 때 너비를 우선 탐색하는 것을 말합니다. BFS는 Queue 자료구조를 이용하여 쉽게 탐색할 수 있습니다. ​ 아래와 같은 트리가 있다고 봅시다. 너비 우선 탐색은 내려가기 전에 너비를 한 번 쫙 훑어보는 것을 말합니다. 탐색 순서는 이렇게 됩니다. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 뭐 사람에 따라서는 이렇게 하기도 하겠죠. 1 -> 3 -> 2 -> 6 -> 5 -> 4 -> 7 어떤 식으로 하든 같은 계층에 있는 노드를 다 방문하기 전에는 아래로 내려가지 않는다는 점 꼭 기억해 주세요. 코드로 한 번 보겠습니다. Python에서 deque을 사용합니다. queue는 스레드를 신경 쓰고, deque는 스레드를 신경 쓰지 않기 때문에 속도적인 측면만 필요하다면 queue보다는 deque을 사용하는 게 좋습니다. 12 번째 줄처럼 탐색에 사용할 deque(덱)를 하나 만듭니다. 13 번째 줄처럼 root를 집어 넣습니다. 15 번째 줄에서 덱이 비어있지 않다면 계속 탐색을 하도록 합니다. 16 번째 줄에서 현재 덱에 들어있는 크기를 구하고, 18 번째 줄처럼 그 크기만큼 반복합니다. 19 번째 줄처럼 덱에 들어있는 노드를 꺼내어 다음에 탐색할 왼쪽, 오른쪽 노드들을 덱에 넣습니다. 끝. 카테고리: Algorithm

알고리듬 Find a minimum distance in the array를 알아보겠습니다. 배열 안에서 어떤 지점에서 원소들 간의 거리가 최소인 경우를 알아봅시다. 1, 3, 9, 13, 105 이런 배열이 있다면 가장 최소가 되는 지점은 중앙값(Median)입니다. 위의 값은 9를 기점으로 각 원소의 거리를 측정하면 가장 짧습니다. 114가 가장 짧은 거리입니다. 만약 짝수 일 때는 어떻게 될까요? 가운데 양옆의 값의 평균을 구합니다. 그게 중앙값이 됩니다. 6이 중앙값이 되고, 거리는 18이 최소가 됩니다. 한 가지 재미있는 것은, 3~9 사이에 아무 값을 넣어도 거리는 최소라는 겁니다. 그 이유는 바로 6이 중앙값이지만, 3과 9 사이에 값들은 3 하고 가까워지면 동일하게 9에서 멀어지므로 값이 유지되고, 반대로 9와 가까워지면, 3 하고 멀어지면서 동일하게 유지됩니다. 코드로 봅시다. 3 번째 줄에서 중앙값을 구합니다. 끝. 카테고리: Algorithm

알고리듬 linked list reverse order를 알아보겠습니다. ​ 링크드 리스트는 다음 구조체의 주소를 가지고 있는 구조체의 집합입니다. ​ 그림으로 보면 아래와 같습니다. 이 linked list를 역순으로 어떻게 만드는지 알아보겠습니다. ​ 노드는 이렇게 정의되어 있습니다. reverse_order라는 함수를 만듭니다. 이전 값을 연결해야 하므로 previous_node를 만들고, None을 넣습니다. 왜냐하면, 역순으로 보면 head가 마지막이기 때문입니다. current_node가 None이 아닐 때까지 반복합니다. 37 번째 줄에서 next_node에는 current_node의 next를 넣습니다. 38 번째 줄에서 기존의 current_node의 next의 연결을 끊고 previous_node로 연결합니다. 39 번째 줄에서 current_node를 previous_node로 만듭니다. 40 번째 줄에서 current_node를 next_node로 만들어주어 반복합니다. 끝나면 42 번째 줄에서 마지막 값이 저장된 previous_node를 반환합니다. 숨겨진 코드 때문에 아래 코드는 여러분 컴퓨터에서는 작동하지 않을 겁니다. 그냥 결과만 보여드릴게요. 끝. 카테고리: Algorithm

알고리듬 Dijkstra algorithm without direction을 알아보겠습니다. ​ Dijkstra(다익스트라, 데이크스트라) 알고리듬은 최단거리를 구할 때 사용합니다. 각 지점 간의 거리를 계속해서 업데이트합니다. 이번 시간에는 방향성이 없는 경우를 다룹니다. ​ 개념은 간단합니다. 모든 경우에 대해서 경로 업데이트를 진행합니다. 이전에 지나갔던 길 보다 더 적은 값을 발견하면 다시 그 경로를 전체 탐색합니다. 더 이상 적은 값을 발견하지 못하면 프로그램은 종료되고 우리는 가장 최단 거리를 알게 됩니다. ​ ​ 다음과 같은 지도에서 3 -> 5로 가는 최단 경로를 구해봅시다. 각 지점 간의 관계는 다음과 같이 표시하기로 합니다. [시작 지점, 시간, 도착 지점] 예를 들어 3 번 지점의 경우 [3, 2, 1], [3, 5, 4]로 표현될 수 있습니다. ​ 지점은 총 5 개가 있고, 출발 지점은 3 번, 도착 지점은 5 번입니다. 맵은 다음과 같이 있습니다. 일단 모든 노드들의 관계를 저장할 리스트를 하나 만듭니다. adjacent로 만들었고, 노드의 수에 맞게 2 중 배열로 만듭니다. for 문으로 리스트에 해당하는 경로들을 넣어줍니다. 10 번째 줄에서 가는 경로를 넣고, 11 번째 줄에서 오는 경로를 넣습니다. searching이라는 함수를 만듭니다. 1 번째 줄에서 heapq, heappush, heappop을 불러옵니다. queue의 PriorityQueue를 사용해도 되는데, Thread 신경 안 쓰고 속도적인 측면만 필요하다면 heapq를 사용합니다. 5 번째 줄에서 시작 점에서 이동할 때 걸리는 모든 시간을 저장할 take_t...

알고리듬 Find a prime을 알아보겠습니다. ​ 소수는 1과 자기 자신으로 만 나눠지는 수를 말합니다. 0과 1은 소수가 아닙니다. ​ 소수를 구할 때에는 약수의 성질을 이용합니다. 약수의 경우 대칭되는 값이 존재합니다. 따라서, 우리는 소수를 확인하기 위해 1에서 26까지 전부 확인할 필요 없이 1과 2만 확인하면 13, 26을 확인한 것과 똑같습니다. ​ 그렇다면, 이 절반을 어떻게 찾을 수 있을까요? 바로 제곱근(root)을 사용합니다. 약수가 저렇게 대칭되지만, 제곱근의 경우 대칭되는 수가 자기 자신이기 때문입니다. ​ 26의 경우 대략 5입니다. 따라서, 1~ 5까지만 확인하면 됩니다. ​ ​ ​ 코드로 한 번 봅시다. 1 보다 작으면 False 2와 3이면 True 그 외에는 12번째 줄처럼 math.sqrt를 이용해서 절반까지만 확인하면 됩니다. 끝. 카테고리: Algorithm

알고리듬 Binary search and find boundary를 알아보겠습니다. ​ Binary search는 이진 탐색으로 찾는 시간이 O(log n)으로 빠릅니다. https://en.wikipedia.org/wiki/Binary_search_algorithm 이론은 다음과 같습니다. 2, 3, 5, 7, 11이라는 배열이 있습니다. 여기서 7을 찾아봅시다. ​ 가장 왼쪽을 left, 가장 오른쪽을 right로 두고, 그 가운데를 middle로 둡니다. 찾으려는 숫자(7)가 가운데(5)를 기준으로 오른쪽에 있으므로 왼쪽은 모두 제외합니다. middle이 있던 자리에 left로 만들고 또 가운데를 찾습니다. middle(7)과 찾으려는 숫자(7)이 같으므로 찾았습니다. 코드로 봅시다. 위의 방법 말고도 다른 방법이 있습니다. 위의 코드는 middle이 target과 같은지 항상 체크를 합니다. 아래의 코드는 항상 확인하지 않고 한 번 만 확인합니다. 찾으려는 값이 가장 왼쪽(leftmost)에 있는 값을 찾으려면 아래와 같이 사용합니다. 찾으려는 값이 가장 오른쪽(rightmost)에 있는 값을 찾으려면 아래와 같이 합니다. ...

알고리듬 How many times make words를 알아보겠습니다. ​ 수많은 글자 중에서 해당하는 단어를 몇 번 만들 수 있는지 알아보는 알고리듬을 다뤄보겠습니다. ​ jaehwa를 만들어 본다고 가정하고 진행합니다. 해당 글자는 다음과 같은 철자로 구성되어 있습니다. j 1 개, a 2 개, e 1 개, h 1 개, w 1 개입니다. 위의 글자 구성이 전부 있어야 하는데요. 글자 중 하나라도 없다면 해당 글자를 만들 수 없습니다. 즉, j가 99 개 있어도, 1 개밖에 못 만듭니다. 위의 단어를 구성하는 글자 중에서 가장 작은 숫자에 맞춰지게 됩니다. ​ Python으로 한 번 볼게요. ​ 아래의 글자 속에서 jaehwa를 몇 번 만들 수 있을까요? asdlkfjewoiurpewt]fivzj,./vncbhildfq[reiptojdklajfklc.sdafruweqporp[tu 먼저, dictionary를 만들어줍니다. 여기에는 미리 jaehwa를 넣어줍니다. 왜냐하면, 파이썬은 초깃값이 없을 때 뭔가 연산을 하면 오류가 나기 때문이죠. 그다음, 12 번째 줄에서 text를 한 글자씩 보면서 my_dict에 넣습니다. 결과는 다음과 같네요. h가 하나뿐이라서 안 봐도 1 개 밖에 못하겠군요. 이것을 코딩으로 계산하려...

알고리듬 Bipartite Matching을 알아보겠습니다. Bipartite Matching은 이분 매칭으로 한 쪽에서 한 쪽으로 매칭 시키는 것을 말합니다. ​ 예를 들어서 의자 앉기를 보죠. 4 사람과 4 개의 의자가 있습니다. 이 사람들이 최대 몇 명까지 의자에 앉을 수 있을까요? ​ 정답은 4 명 모두 다 앉을 수 있습니다. 0 -> 0 1 -> 1 2 -> 2 3 -> 3 이렇게 앉으면 됩니다. 이걸 알고리듬으로 어떻게 찾느냐가 문제인데요. ​ ​ 다음과 같이 풀이합니다. 0 번을 0 번에 앉힙니다. 다음 1 번은 어디 앉을까요? 일단 첫 번째 화살표로 갑니다. 어라... 0 번이 있네요. 0 번이 다른 곳에 앉을 수 있는지 찾아봅니다. 만약 다른 곳에 앉을 곳이 있다면, 0 번이 양보를 해주고 다른 곳으로 갑니다. 만약 다른 곳에 앉을 곳이 없다면, 1 번은 의자에 앉지 못합니다. 다행히 3 번에 앉을 수 있군요! ​ 다음, 2 번 앉아 봅시다. 첫 번째 화살표로 갑니다. 없네요. 앉습니다. 자, 마지막 3 번 앉아 봅시다. 어랏... 0 번이 있네요. 이제, 0 번을 다른 곳에 앉혀 봅니다. 1 번이 있네요. 1 번을 다른 곳에 앉혀 봅니다. 2 번이 있네요. 2 번을 다른 곳에 앉혀 봅시다. 오, 마침 2 번 자리가 비었군요. 그럼 이제, 모두 자리에 앉힙니다. ...