본문 바로가기

Develop

[코딩인터뷰] 백준 10026번 BFS from collections import deque # R G B 적록 색약 시 R = G n = int(input()) pic = [] for _ in range(n): pic.append(list(input())) dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1] v_a = [[False] * n for _ in range(n)] v_b = [[False] * n for _ in range(n)] c_a = 0 c_b = 0 for i in range(n): for j in range(n): if not v_a[i][j]: rgb_a = pic[i][j] q_a = deque() q_a.append((i, j)) v_a[i][j] = True c_a += 1 if not v..
[코딩인터뷰] 백준 2468번 Python 으로 DFS 전략으로 풀면 'Recursion Error' 나고 '메모리 초과' 나고 난리납니다. 그래서 BFS 로 바꿔서 풀어야 합니다. 전에는 DFS 가능했는데 메모리가 줄었나 봅니다. BFS from collections import deque # 2
[코딩인터뷰] 알고리즘 시간 복잡도 분석 방법 알고리즘 시간 복잡도 분석 방법 코딩 테스트는 시간 제한이 있습니다. 이미 구현한 전략이 제한된 실행 시간 안에 풀 수 없다는걸 깨닫고 다른 전략을 시도할 시간은 없습니다. 따라서 문제를 어떻게 풀까 고민하다 떠올린 아이디어가 실행 시간 안에 해결할 수 있는지를 가늠할 줄 알아야, 잘못된 구현을 하는 불상사를 피할 수 있습니다. 내가 구현할 알고리즘 전략이 주어진 실행 시간 안에 동작할 수 있는지를 간단하게라도 가늠할 줄 알아야 합니다. 일반적으로 10의 8승, 1억번 이상 의 연산 시간이 필요한 전략은 코딩 테스트 문제에 일반적으로 주어지는 '1초' 라는 제한된 실행 시간 안에 해결할 수 없습니다. 특히나 Python 는 타 언어에 비해 실행 시간이 더 걸리는 편이라 제한된 실행시간 안에..
[코딩인터뷰] 깊이 우선 탐색 Depth first search (DFS) 깊이 우선 탐색 Depth first search (DFS) 깊이 우선 탐색 (DFS) 는 너비 우선 탐색과 함께 코딩 테스트 출제 빈도가 높은 전략입니다. DFS 는 그래프에서 A 노드를 방문하고, 방문한 A 노드와 연결된 B 노드를 방문하고, 방문한 B 노드와 연결된 C 노드를 방문하는 과정을 반복해서 그래프의 모든 노드를 방문합니다. 너비 우선 탐색과 달리 굉장히 직관적인 탐색 방법입니다. DFS 을 사용하여 그래프를 탐색할 때 무한 반복을 조심해야 합니다. 만약 그래프에 사이클이 있다면 무한히 탐색을 반복하게 됩니다. 따라서 이미 방문한 노드를 기록하고 탐색할 때 방문했는지 안했는지를 확인해야 무한 반복을 피할 수 있습니다. DFS 전략으로 푸는 대표적인 문제 유형 노드 사이 간 거리가 다른 최단..
[코딩인터뷰] 백준 2638번 from collections import deque # 5
[코딩인터뷰] 백준 2146번 from collections import deque import sys sys.setrecursionlimit(10000) def create_island(id, x, y): global sea, islands, iv, dx, dy sea[x][y] = id islands[id].append((x,y, 0)) iv[x][y] = True for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0
[코딩인터뷰] 백준 16236번 from collections import deque # 크면 못지나감. 같으면 지나감. 작아야 먹음 # 자기 크기만큼 먹어야 성장 n = int(input()) space = [] for _ in range(n): space.append(list(map(int, input().split()))) # 아기상어 처음 위치 shark_loc = (0, 0) for i in range(n): for j in range(n): if space[i][j] == 9: space[i][j] = 0 shark_loc = (i, j) # 아기 상어 처음 크기 shark_level = 2 shark_eat_count = 0 # 시간 time = 0 # 이동 dx = [-1, 0, 1, 0] dy = [0, -1, 0, 1..
[코딩인터뷰] 백준 14502번 백준 14502번 연구소 문제는가능한 경우의 수가 많지 않습니다. 그래서 무식하게 벽을 세울 수 있는 모든 경우의 수를 검토해도 시간 안에 풀 수 있습니다. 만약 이게 문제가 아니었다면 바이러스를 기준으로 탐색해서 벽을 더 효율적인 세울 수 있는 방법을 찾아보고 싶네요. from copy import deepcopy from collections import deque def virus(): global n, m, maps, answer, viruses, dx, dy c_maps = deepcopy(maps) for v in viruses: q = deque() q.append(v) visited = [[False] * m for _ in range(n)] while 0 < len(q): c = q.po..