본문 바로가기

알고리즘

 (138)
dfs, bfs - 네트워크 / 파이썬 dfs 풀이 def solution(n, computers): visit = [0] * n def dfs(com): visit[com] = 1 for idx, num in enumerate(computers[com]): if idx == com or visit[idx] or num == 0: continue dfs(idx) answer = 0 for i in range(n): if visit[i] == 0: dfs(i) answer += 1 return answer bfs 풀이 from collections import deque def solution(n, computers): answer = 0 visit = [0] * n for i in range(n): if visit[i]: continue q ..
bfs - 타겟 넘버 / 파이썬 from collections import deque def solution(numbers, target): answer = 0 q = deque() q.append([numbers[0], 0]) q.append([-numbers[0], 0]) while q: hap, idx = q.popleft() if idx == len(numbers)-1: if hap == target: answer += 1 else: q.append([hap+numbers[idx+1], idx+1]) q.append([hap-numbers[idx+1], idx+1]) return answer programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정..
완전탐색 - 소수 찾기 / 파이썬 from itertools import permutations def ck(num): ck_num = 0 for i in range(2, num+1): if num % i == 0: ck_num += 1 if ck_num == 2: return False return True def solution(numbers): answer = 0 num_set = set() for i in range(1, len(numbers)+1): lst = list(map(''.join, permutations(numbers, i))) for j in lst: if int(j)
해시 - 베스트 앨범 / 파이썬 def solution(genres, plays): dic, hap = {}, {} i = 0 for g, p in zip(genres, plays): if g not in dic: dic[g] = [[p, i]] hap[g] = p else: dic[g].append([p, i]) hap[g] += p i += 1 s_hap = sorted(hap.items(), key=lambda x: x[1], reverse=True) ret = [] for k, _ in s_hap: lst = sorted(dic[k], key=lambda x: x[0], reverse=True) if len(lst) > 2: lst = lst[:2] for _, num in lst: ret.append(num) return re..
해시 - 전화번호 목록 / 파이썬 def solution(phone_book): phone_book.sort() for num1, num2 in zip(phone_book, phone_book[1:]): if num2.startswith(num1): return False return True zip 함수 - 여러개의 Iterable 동시에 순회 startswith - 시작하는지 여부 programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr
[알고리즘] 백준 2887 행성 터널 / 파이썬 / 크루스칼 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이�� www.acmicpc.net def find(x): if parent[x] == x: return x parent[x] = find(parent[x]) return parent[x] def union(v1, v2): v1 = find(v1) v2 = find(v2) if v1 != v2: parent[v2] = v1 def parentCk(v1, v2): v1 = find(v1) v2 = find(v2)..
[알고리즘] 백준 2239 스도쿠 / 파이썬 / dfs www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다� www.acmicpc.net def cal(x, y): return (x//3)*3 + (y//3) def sol(n): if n == 81: for i in B: print(''.join(map(str, i))) return True x = n // 9 y = n % 9 if B[x][y]: return sol(n+1) else: for i in range(1, 10): if not c1[x][i] and not c2[y][i] ..
[알고리즘] 백준 14502 연구소 / 파이썬 www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net from collections import deque from copy import deepcopy dx, dy = [0, -1, 0, 1], [-1, 0, 1, 0] #bfs이용해 바이러스 퍼뜨림 def virus(i, j, Map2): q = deque() q.append([i, j]) while q: x, y = q.popleft() for k in range(4): xx, yy = x + dx[k], y + dy[..

티스토리툴바