본문 바로가기
반응형

Python

 (88)
[리트코드] Subsets(python) 리트코드, Subsets_부분집합 TL;DR 깊이 우선 탐색(DFS) 문제 1. 주어진 중복이 없는 정수 배열 nums에 대해서 생성할 수 있는 모든 부분 집합을 반환하라. 2. 정답 배열은 복사된 부분 집합을 포함해서는 안되며 정렬 순서에는 큰 상관이 없다. 입출력 형태 - 주어진 숫자 배열로 만들 수 있는 모든 부분 집합을 반환하면 된다. - 공집합 또한 부분 집합의 일부이므로 포함시켜야 한다. 풀이 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: answer = [] def dfs(index: int, subsets: List[int]): answer.append(subsets) for i in range(index, l..
[리트코드] Combination Sum(python) 리트코드, Combination Sum_조합의 합 TL;DR 깊이 우선 탐색(DFS) 문제 1. 주어진 구분된 정수 배열 candidates와 목표 정수 target에 대해서 조합한 숫자들의 합이 target이 되는 유일한 조합들의 배열을 반환해야 한다. 2. candidates 내에 동일한 숫자를 여러 번 고를 수 있으며, 만약 적어도 하나의 숫자가 다르다면 두 조합은 다른 조합이다. 3. 문제에서 target이 되는 조합의 수가 150보다 적은 것을 보장한다. - 주어진 정수 배열 candidates 내에 있는 숫자를 중복 선택한 조합들에 대해서 조합의 합이 target이 되는 배열을 반환하면 된다. 입출력 형태 - 주어진 정수 배열 [2, 3, 6, 7]에서 합이 7이 되도록 숫자를 조합하는 경우는..
[백준] DFS와 BFS(python) 백준, DFS와 BFS TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 분석 1. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 2. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고 3. 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 4. 정점 번호는 1번부터 N번까지이다. - 입력으로 주어진 그래프를 DFS와 BFS로 각각 순회한 결과를 출력하는 프로그램을 작성하는 문제이다. - 2번의 조건에 유의하여 문제를 풀어야 한다. 입출력 형태 - 가장 첫 번째 줄에 정점(vertex, node)의 개수와 간선(edge)의 개수, 그리고 시작 정점의 번호가 주어진다. - 두 번째 줄부터는 각 정점 간의 연결관계를 나..
[리트코드] Combinations(python) 리트코드, Combinations_조합 TL;DR 깊이 우선 탐색(DFS) 문제 분석 [1, n] 범위의 수로 만들 수 있는 k개의 모든 가능한 조합을 반환하라. - 1 ~ n 사이의 수에 대해서 k개를 뽑아 만들 수 있는 모든 조합을 반환하면 된다. 입출력 형태 - 1 ~ 4 사이의 숫자에서 2개를 뽑아 만들 수 있는 모든 조합을 반환하고 있다. - 만들 수 있는 조합의 개수는 공식(`n! / (n - k)!k!`)에 따라 6개가 반환되어야 한다. 틀린 풀이 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: answer = [] def dfs(vertex: int, combinations: List[List[int]] = [])..
[리트코드] Permutations(python) 리트코드, Permutations_순열 TL;DR DFS(깊이 우선 탐색) 문제 분석 1. 주어진 숫자 배열에 대해 만들 수 있는 모든 순열을 반환하라. 2. 반환된 배열은 어떤 순서로 되어 있어도 상관 없다. - 주어진 숫자들로 만들 수 있는 순열을 반환하면 된다. 입출력 형태 풀이 class Solution: def permute(self, nums: List[int]) -> List[List[int]]: answer = [] def dfs(v: int, permutation: List[int] = []): permutation.append(v) if len(permutation) == len(nums): answer.append(permutation) return for num in nums: if..
[프로그래머스] 숫자 문자열과 영단어(python) 프로그래머스, 숫자 문자열과 영단어 2021년 카카오 채용연계형 인턴십 TL;DR 문자열(string) 딕셔너리(dictionary) 문제 분석 1. 숫자의 일부 자릿수가 영단어로 바뀌었거나, 혹은 바뀌지 않고 그대로인 문자열 s를 원래 의미하는 숫자로 반환하는 함수를 완성하라. - 입출력 예시를 통해 원하는 답을 확인할 수 있다. 입출력 형태 - 주어진 문자열에 대해 글자로 주어진 문자열을 숫자로 변환하여 결과를 반환하면 된다. 풀이 def solution(s): answer = '' dic = { 'zero': '0', 'one': '1', 'two': '2', 'three': '3', 'four': '4', 'five': '5', 'six': '6', 'seven': '7', 'eight': '8'..
[리트코드] Number of Islands(python) 리트코드, Number of Islands_섬의 수 TL;DR 깊이 우선 탐색(DFS) 너비 우선 탐색(BFS) 문제 분석 1. 주어진 M * N 크기의 2차원 배열 grid는 '1' 땅, '0' 물을 의미한다. 2. 주어진 2차원 크기 배열에서 섬의 개수를 반환하라. 3. gird의 외곽은 모두 물로 둘러쌓여있다고 가정한다. - 1 ~ 2 : 땅(1)과 물(0)이 주어진 지도 형태의 2차원 배열 grid에 대해서 섬의 개수를 반환한다. - 3 : grid의 최외곽은 모두 물로 둘러쌓여있다고 생각한다. 이 부분을 입출력 형태에서 살펴볼 것이다. 입출력 형태 - 주어진 예시에서 빨간색으로 표시되어 있는 부분이 섬이다. - 문제 3번 조건에 따라 grid의 외곽은 모두 물로 되어 있으므로 섬으로 생각할 수 ..
[Python] 아스테리스크(*) 연산자 알아보기 아스테리스크(*)는 다양한 용도로 사용된다. 그 중에서도 가장 많이 알려진 것인 C언어에서의 포인터로써 사용되는 것이나 곱셈 연산자로써 사용되는 것일 것이다. 파이썬(Python)에서도 * 연산자가 다양한 용도로 사용된다. 다른 언어들과는 다른 기능들을 알게 되어 정리해보려 한다. 1. 곱셈 연산자 a, b = 5, 3 a * b # 15 가장 많이 익숙한 방법이다. 두 수의 곱셈 연산을 할 때 사용된다. 2. 언팩(Unpacking) 언팩(Unpacking), 단어의 뜻 대로 쌓여있는 것을 푸는 용도로도 사용된다. 무슨 말인지는 예시를 통해 확인할 수 있다. 배열 a = [1, 2, 3, 4, 5]의 원소를 한 줄에 출력하는 코드를 통해 * 연산자의 언팩에 대해서 살펴본다. 언팩을 사용하지 않고 출력하..

티스토리툴바