python에는 너무 유용한 내장 함수가 많이 있는데, 그 중에서도 경우의 수를 구할 때 사용되는 내장 함수를 다뤄보겠다. 경우의 수는 전체 탐색이 필요한 알고리즘 문제에서 은근 자주 쓰이므로 기억해둘 것! 경우의 수를 구할 땐 itertools라는 모듈을 활용한다. import itertools 순열 서로 다른 n개 중에서 r개를 '순서'대로 나열하는 경우의 수 # 배열 ['1','2','3','4'] 중에서 서로 다른 원소 두 개를 순서대로 나열하는 경우의 수를 출력한다. itertools.permutations(['1','2','3','4'], 2) 중복순열 중복 가능한 n개 중에서 r개를 '순서'대로 나열하는 경우의 수 # 배열 ['1','2','3','4'] 에서 중복 가능한 원소 두 개를 순서..
[Algorithm] 너비우선탐색(BFS), 깊이우선탐색(DFS)
배울 때마다 헷갈리고 이해되지 않던 우선 탐색들... 오늘 드디어 완전히 이해 완료했다 생각보다 간단한 원리로 제작! 그래프로 문제를 해결할 때 어떤 방식으로 해결해야 적절한지에 따라 갈린다. 알고리즘에 큰 차이는 없다! 너비 우선 탐색 (Breadth First Seartch) 말 그대로 '너비를 우선적으로 탐색하는 알고리즘'이다. 즉, 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문한다고 생각하면 쉽다. '큐(queue)'를 사용하는 것이 이 알고리즘의 핵심! 노드를 방문하면서 인접한 노드 중 방문하지 않았던 노드의 정보만 큐에 넣어 '먼저 큐에 들어있던 순서대로' 노드를 방문하면 된다. 이때, python 라이브러리 중 deque 를 사용하면 시간을 절약할 수 있다. 코드 from co..
[Algorithm] 그래프 (Graph)
여러 노드(또는 정점, vertex) 들이 간선(edge, 또는 arc)으로 연걸된 추상 네트워크 이를 수식으로 표현하면, G는 그래프, V는 노드의 집합이고 E는 간선의 집합이다. 이와 같은 그래프에서 V는 {a, b, c, d} , E는 {{a, b}, {b, c}, {c, d}, {d, a}} 이다. 그래프의 종류 무방향 그래프 방향이 없는 그래프 간선을 통해 노드는 양방향으로 갈 수 있다. 보통 노드 A, B가 연결되어 있을 경우 (A, B) 또는 (B, A)로 표기 방향 그래프 간선에 방향이 있는 그래프 보통 노드 A, B가 A -> B 방향일 경우, 로 표기 가중치 그래프 (네트워크) 간선에 비용 또는 가중치가 할당된 그래프 연결 그래프 무방향 그래프에 있는 모든 노드에 대해 항상 경로가 존재..