본문 바로가기

전체 글

 (172)
bfs - 단어 변환 / 파이썬 from collections import deque def ck(w1, w2): cnt = 0 lenth = len(w1) for i in range(lenth): if w1[i] == w2[i]: cnt += 1 return True if cnt == lenth-1 else False def solution(begin, target, words): if target not in words: return 0 q = deque() for w in words: if ck(begin, w): q.append([w, 1]) while q: word, cnt = q.popleft() if word == target: return cnt for w in words: if ck(word, w): q.append([..
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[..
[알고리즘] 백준 1600 말이 되고픈 원숭이 / 파이썬 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있�� www.acmicpc.net 2206번 문제와 아주 유사하다 응용해서 풀어주면 된다 방문을 체크하는 ck배열을 삼중배열로 만들어서 말처럼 이동한 경우/ 원숭이로 이동한 경우를 구별한다 x, y좌표로 말처럼 k번 이동했으면 ck[x][y][k]에 이동거리가 저장된다 x, y좌표로 원숭이로 이동했으면 k는 변하지 않는다 그리고 (H, W)까지 갔다면 저장했던 거리를 리턴, 아니라면 -1을 리턴해 출력해준다 from coll..

티스토리툴바