알고리즘 이론32 배열 행 우선 순위, 열 우선 순위 2차원 배열에 어떠한 값들을 저장하는 방법은 두 가지가 있습니다. 두 가지 방법으로 저장한 배열은 각각 '행 우선 배열'과 '열 우선 배열'이라고 부릅니다. 하나씩 알아보도록 하겠습니다. 행 우선 배열(row major ordering) 먼저 행우선 배열입니다. 이름 그대로 행을 우선시해서 저장하는 배열을 뜻합니다. 위의 그림에서 각 행들에 속하는 요소들을 빨간색 네모로 묶어보았는데 저 빨간색 네모를 먼저 채우고 다음 네모를 채운다고 생각하시면 됩니다. 즉, 1행을 다 채우고 2행을 채우는 식으로 배열을 채워나갑니다. 그런 식으로 배열을 채워나가면 저장되는 요소들의 순서는 위의 그림과 같습니다. 이제 요소들의 주소를 알아보겠습니다. 일단 axb 배열의 (i,j)의 주소를 구하는 공식은 '시작 주소 + (.. 2022. 3. 9. 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. 이전 1 2 3 4 ··· 6 다음
