그래프 이론 서로소 집합 공통 원소가 없는, 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온- 파인드 자료구조이다. 서로소 집합 자료구조 union 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 find 특정 한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 정보가 주어졌을때 트리 자료 구조를 이용해서 집합을 표현한다. 서로소 집합 알고리즘 각 노드는 자기 자신을 부모 노드로 갖도록 초기화 한다. union을 확인하여, 서로 연결된 두 노드 A,B를 확인한다. A와 B의 루트 노트 A'와 B'를 각각 찾는다. A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가르키도록 한다.) 트리가 한쪽으로 기울어지는 것을 방지하기 위해서..

사라지는 발판 문제 각 플레이어는 자신의 캐릭터 하나를 보드 위에 올려놓고 게임을 시작합니다. 게임 보드는 1x1 크기 정사각 격자로 이루어져 있으며, 보드 안에는 발판이 있는 부분과 없는 부분이 있습니다. 발판이 있는 곳에만 캐릭터가 서있을 수 있으며, 처음 캐릭터를 올려놓는 곳은 항상 발판이 있는 곳입니다. 캐릭터는 발판이 있는 곳으로만 이동할 수 있으며, 보드 밖으로 이동할 수 없습니다. 밟고 있던 발판은 그 위에 있던 캐릭터가 다른 곳으로 이동하여 다른 발판을 밞음과 동시에 사라집니다. 양 플레이어는 번갈아가며 자기 차례에 자신의 캐릭터를 상하좌우로 인접한 4개의 칸 중에서 발판이 있는 칸으로 옮겨야 합니다. 다음과 같은 2가지 상황에서 패자와 승자가 정해지며, 게임이 종료됩니다. 움직일 차례인데..

정렬 알고리즘 Selection sort n개의 원소를 가진 배열 중에 가장 작은 값을 찾아서 처리되지 않은 데이터 중 맨 앞과 바꾼다. 이 과정을 N-1번 반복해 정렬이 완료된다. for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] Space ComplexityTime Complexity O(1) O(n^2) Bubble sort 인접한 두 개의 데이터를 비교해가면서 정렬을 진행한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 끝에 위치하..

동적계획법 (Dynamic Programming) 동적 계획법이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 분할 정복과 다른 점은 문제들이 서로 영향을 미치고 있다는 점이다. 동적 계획법의 경우 한 번 해결한 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 가져다 쓰는 것이다. 동적 계획법은 다음 조건을 만족할 때 사용할 수 있다. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 동적 계획법을 구현하는 방식에는 2가지가 있는데 탑 다운 방식과 바텀 업 방식이다. 탑다운 방식은 재귀 함수를 이용한다. 큰 문제를 해결하기 위해 작은 ..