썸네일 [Union-Find] Friend-Circle Union-Find 알고리즘에 관한 설명은 나동빈님의 블로그에서 보고 이해했다. Union-Find 알고리즘은 간단히 말하자면 합집합 찾는 알고리즘 다르게 말하자면 서로소(disjoint set)을 찾는 알고리즘이다. 원리 및 구체적인 구현 방법은 나동빈님의 블로그에 아주 상세히 설명되어 있다. m.blog.naver.com/ndb796/221230967614 그 구현 및 실습은 leetcode의 Friend-Circle을 통해 구현해 보았다. find는 해당 노드의 제일 조상 노드를 찾는 함수이다. union은 각 노드의 제일 조상 노드가 동일한 경우에 합치는 함수이다. Union-Find 문제에 따라서 union을 언제 해야하는 지는 달라질 수 있다. from collections import def..
썸네일 rotate image 행렬을 시계방향으로 90도 만큼 회전 시키는 문제이다. 90도 회전은 행렬을 전치(Transpose) 한다. 전치된 행렬에서 각 행에 저장된 값을 역순으로 한다. 이 순서를 따르면 행렬이 90도 회전된 결과를 얻을 수 있다. 다만, 문제에서는 in-place 회전을 원하기 때문에 다른 방법을 이용해야 한다. 다른 방법으로 90도 회전시키기 위해서는 행렬의 길이 n이라고 했을 때 윗쪽 절반 행들과 아랫쪽 절반 행들의 위치를 바꾼다. 위치를 바꾼 후에 모든 원소에 대해서 (r,c) 와 (c,r)에 위치하는 값을 한번만 바꾼다. from typing import List class Solution: def rotate(self, matrix: List[List[int]]) -> None: for r in ra..
Longest Increment Subsequence 오늘 추가로 풀어본 알고리즘 문제는 최장 증가 수열이다. 예젠에도 백준에서 매우 유사한 문제를 풀어봤었다. DP 문제를 빠르게 푸는 방법은 정확한 의미의 점화식을 세우는 것이다. 처음 문제를 풀 때 세웠던 점화식은 i 번째 원소를 시작점로 하면서 j 번째 원소를 끝점으로 하는 최장 증가 수열의 길이라고 정의하고 풀려고 노력해 보았다. 잘못된 점화식을 세웠을 때 가장 빠르게 알 수 있는 문제가 i - 1 또는 j -1 과 현재 dp[i][j]와의 관계를 찾는 것이 불가능하거나 가능하더라도 매우 복잡해진다. 따라서 구글 검색을 통해 내가 생각한 점화식이 틀린지 확인해 보았는데, 역시나 틀린 점화식이었다. 알맞은 점화식은 dp[k], k 번째 원소를 끝으로 하는 최장 증가 수열의 길이이다. 배열 dp는 1로 ..
썸네일 DP 문제 Number of dice rolls with target 주사위 면의 수 f인 (1...f) d 개의 주사위를 굴려 target을 만드는 경우의 수를 구하시오. 문제 및 예제의 원본이다. 문제를 딱 보고 든 풀 수 있는 방법 중 하나는 DFS, BFS 였다. 하지만 DFS, BFS로 하면 30면 짜리 주사위의 30개를 굴려서 특정 target이 될 수 있는 경우의 수를 구할 때 시간초과(TLE)가 날 수 있다. 그렇다면 다른 방법으로 풀 수 있는 게 무엇일까 생각해봤다. DP 방법의 풀이가 가능한 지 알아보자. 일단 2차식 형태의 점화식을 세워보자. (여기서 2차식이라 함은 이차원 배열을 사용한다고 생각하면 된다.) dp[d][k]를 주사위 d개로 t를 만들 수 있는 경우의 수라고 하자. (항상 dp에서는 점화식을 어떻게 정의하느냐가 중요하다.) dp[d][t..
Permutation(순열) 알고리즘 Permutation은 알고리즘 문제를 풀다보면 다른 문제와 결합되어 자주 출제되는 문제 중 하나다. 여기서는 중복 순열은 다루지 않고 나중에 다루도록 하겠다. 순열은 [1,2,3,4]에서 4개를 뽑아 순서를 정하는 순열은 1,2,3,4 1,2,4,3 1,3,2,4, 1,3,4,2 1,4,2,3, 1,4,3,2 ... 이렇게 나오게 될 것이다. 이 글에서는 permutation 알고리즘을 구현하는 것과 다음 permutation을 구하는 알고리즘을 구현하겠다. 1.모든 Permutation을 구하는 코드 작성 함수의 매개변수로는 배열 또는 리스트[numbers], 몇 개를 뽑을 건지[r], 그리고 배열의 값을 변경할 위치[depth] 모든 Permutation을 구하는 코드를 설명하자면, recurssi..
라이브러리 브랜드 그룹 | iosios 공부용 블로그

티스토리툴바