본문 바로가기

전체 글106

[백준] 1717. 집합의 표현 (+파이썬 코드) Question. 백준 1717. 집합의 표현 Answer. union-find 알고리즘을 구현하는 문제이다. 즉, union 함수랑 find_parent 함수를 구현할 수 있냐를 묻는 문제. sol 1) union-find 알고리즘을 구현하고, 같은 서로소 집합에 있는지 아닌지 확인해주는 함수를 구현해 풀었다. import sys sys.setrecursionlimit(1000000) # maximum recursion depth exceed (한도 안 늘리면 runtime error 발생) input = sys.stdin.readline def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) re.. 2021. 2. 15.
[백준] 10451. 순열 사이클 (+파이썬 코드) Question. 백준 10451. 순열 사이클 Answer. cycle의 개수를 세는 문제이다. sol 1) 이 문제에서 배열의 번호(start node)와 배열의 값(destination node)을 이용해 graph를 만들었다. 위 문제에서는 인접행렬이나 인접리스트로 그래프를 만들 필요는 없어서 일차원 배열로 graph를 만들었다. 그리고 union-find를 통해 cycle의 개수를 구하면 된다. 1) 배열의 번호가 start node를 의미하고, 배열의 값이 destination node를 의미하는 1차원 배열의 graph를 만든다. graph = [0] + list(map(int, input().split())) 2) start node와 destination node의 parent가 같지 않.. 2021. 2. 15.
[백준] 11724. 연결 요소의 개수 (+파이썬 코드) Question. 백준 11724. 연결 요소의 개수 Answer. 프로그래머스의 "네트워크"랑 비슷한 문제여서 자세한 풀이는 생략한다. sohyunwriter.tistory.com/90 [프로그래머스] "네트워크" (+파이썬 코드) Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 Answer. computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 해당 graph에서 connected component가 몇 개인지 구하는 문제이다. b.. sohyunwriter.tistory.com sol 1) 인접리스트 + dfs 반복문 주의사항 1) sys.stdin.readline 써야 시간초과 안 남 2) dfs 돌릴 때, visited한 node.. 2021. 2. 15.
adjacency matrix로 구현된 graph를 DFS할 때 time complexity Question. Answer. C 2021. 2. 14.
[프로그래머스] "네트워크" (+파이썬 코드) Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 Answer. computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 해당 graph에서 connected component가 몇 개인지 구하는 문제이다. bfs로 풀 수도 있고, dfs로 풀 수도 있다. 주어진 인접행렬을 이용해 DFS로 풀면 다음과 같다. sol1) 인접행렬 + dfs 1) i번째 노드를 방문하지 않았다면, 스택에 i번째 노드를 넣는다. 2) stack의 요소를 하나씩 pop 하며 visited 배열에 해당 노드를 true 처리한다. 3) 해당 노드와 연결된 노드들 중 방문하지 않은 노드들을 스택에 넣어준다. ---> dfs 함수 부분 4) 1~3을 n개의 노드에 대해 반복.. 2021. 2. 14.
[Python] list 복사 ([:], copy(), deepcopy()) 파이썬 ps를 하면서 많이 하기 쉬운 실수들에 대해 적는다. 다음 두 코드의 결과는 어떻게 될까? 하나는 맞고 하나는 이상한 결과를 배출한다. 1) class Solution(object): def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ results = [] def dfs(nums, k, pos, subsets=[]): if k == 0: results.append(subsets) return for i in range(pos, len(nums)): subsets.append(nums[i]) dfs(nums, k - 1, i + 1, subsets) subsets.pop() for i in range(len(.. 2021. 2. 11.
728x90