본문 바로가기
반응형

알고리즘 이론31

Python 문법 정리 참고 : https://programmers.co.kr/learn/courses/4008 파이썬을 파이썬답게 본 강의는 파이썬 문법을 이미 알고 있는 분들을 대상으로 만들어졌습니다. ##### 이런 분들께 추천합니다 * 파이썬 문법을 알고 계시는 분 * 알고리즘 문제를 조금 더 쉽게 풀고 싶은 분 * Python 코 programmers.co.kr 배열 map(함수, 리스트) : 리스트 요소들에 함수를 적용한 값을 반환 * symbol : 배열 요소들 출력시 요소값만 출력하고 싶을 때 사용. answer = [1,2,3] print(answer) # [1, 2, 3] print(*answer) # 1 2 3 zip : 각 iterables 요소를 모으는 iterator 생성 (공식문서) a = [1,2,.. 2021. 9. 25.
투포인터 (Two pointer) 투포인터란 이름 그대로 두 개의 포인터를 사용하여 문제를 풀어나갑니다. 2개의 포인터로 배열이나 문자열을 탐색할 때 탐색 위치를 저장하고 있습니다. 말로 하는거보다는 예를 들어서 한 번 살펴봅시다. 수들의 합. N개의 자연수 배열이 주어질 때, i~j 번째 수들의 합이 M이 되는 경우의 수를 구하는 문제입니다. 1 1 1 1 배열은 위와 같고, M = 2 라고 했을 때 투포인터로 정답을 구해봅시다. 두 개의 포인터를 두고 이들을 left, right라 합시다. left는 i, right는 j 번째 수의 위치를 가리킵니다. left는 범위를 줄이고자 할 때 증가시키고, right는 범위를 증가시키고자 할 때 증가시킵니다. 시작 인덱스는 둘 다 0입니다. left right 부분 배열합 0 0 1 0 1 2.. 2021. 9. 12.
유니온 파인드(Union-Find) 유니온 파인드(Union-Find)는 집합을 표현하기 위한 자료구조입니다. 이를 표현하기 위해 트리에서 부모노드를 저장하는 배열을 만듭니다. 부모노드가 없는 루트노드인 경우는 자기자신을 저장합니다. 이때 최상위 부모노드가 같은 값들이 같은 집합에 속하게 됩니다. [그림 1]에서는 1, 2, 3이 같은 집합. 4, 5가 같은 집합입니다. 주의할 점은, 부모노드가 아닌 최상위 부모노드가 같은 노드들이 같은 집합에 속합니다. [그림 2]에서 노드 4와 노드 2는 모두 같은 집합에 속하지만 부모노드 배열만 봐서는 같은 집합에 속하는지 알 수 없습니다. 같은 집합에 속하는지 알기 위해서는 각 노드들의 최상위 부모노드 배열을 알아야 합니다. 노드 4의 부모노드는 3이지만 최상위부모노드는 1이 됩니다. 다른 노드들의.. 2021. 6. 26.
플로이드 워셜 알고리즘 (Floyd warshall) 이때동안 포스팅한 최단거리 알고리즘은 벨만포드, 다익스트라 알고리즘이 있습니다. 이 두개의 알고리즘은 하나의 정점을 기준으로 다른 정점들까지의 최단거리를 구하는 알고리즘입니다. 플로이드 워셜 알고리즘은 이들과 달리 모든 정점간의 최단거리를 구하는 알고리즘입니다. 플로이드 워셜 알고리즘의 기본 원리는 i 정점에서 j 정점 간의 최단거리를 구하려고 할 때, 그 외의 노드 k를 두고 i -> k 로 이동하는 방법이 존재하고 k -> j로 이동하는 방법이 존재할 때, k를 거쳐서 가는 거리가 이때동안 구한 최단거리보다 더 짧을 때, 최단거리를 갱신하는 방법입니다. 정점들의 번호가 0~n-1, i에서 j로 가는 거리(간선)가 W(i, j)이고 최단거리를 배열 dist에 저장한다고 할 때, 플로이드 워셜 알고리즘은.. 2021. 6. 13.
트리의 지름 트리의 지름은 트리의 노드들 중 가장 먼 거리를 가지는 두 노드 사이의 거리를 의미합니다. 알고리즘 1. 임의의 노드 x를 선택한다. 2. dfs로 x와 가장 먼 노드(A)를 구한다. 만약 가장 먼 노드가 2개 이상이라면 이들 중 어떠한 것을 선택해도 상관없다. 3. dfs를 한 번 더 돌려서, 노드 A로부터 가장 먼 노드(B)를 구한다. 4. 노드 A와 노드 B의 거리가 트리의 지름이 된다. 노드 사이의 거리인데 최단거리 알고리즘을 돌려야하지 않나?! 싶기도 하지만 "트리"의 지름을 구하고 있음을 유의해봅시다. 트리의 성질 중 "트리의 두 노드 사이의 경로는 하나만 존재한다."가 있습니다. 따라서 dfs 탐색 중에 구해지는 노드 사이의 거리가 최단거리가 됩니다. 참고코드 : github.com/fpdj.. 2021. 2. 21.
[C++/STL] stack을 vector로 변환하기 STL에서 stack은 컨테이너에 대한 접근을 제어하는 목적으로 사용된다. 따라서 iterator를 제공해주지 않기 때문에 iterator을 사용해서 vector를 만들어낼 수 없다. 요소를 제거하면서 vector 생성 stack st; st.push(1); st.push(2); st.push(3); vector arr(st.size()); int index = arr.size() - 1; // copy st to arr while(!st.empty()){ arr[index--] = st.top(); st.pop(); } stack에서는 top을 통해서만 요소를 가져올 수 있기 때문에 top을 이용해서 vector의 뒤에서부터 값을 채워준다. 단, 이 방법을 쓰면 기존 stack에는 요소가 더 이상 남아.. 2021. 1. 21.
반응형