본문 바로가기

모두보기

[코딩인터뷰] 알고리즘 시간 복잡도 분석 방법 알고리즘 시간 복잡도 분석 방법 코딩 테스트는 시간 제한이 있습니다. 이미 구현한 전략이 제한된 실행 시간 안에 풀 수 없다는걸 깨닫고 다른 전략을 시도할 시간은 없습니다. 따라서 문제를 어떻게 풀까 고민하다 떠올린 아이디어가 실행 시간 안에 해결할 수 있는지를 가늠할 줄 알아야, 잘못된 구현을 하는 불상사를 피할 수 있습니다. 내가 구현할 알고리즘 전략이 주어진 실행 시간 안에 동작할 수 있는지를 간단하게라도 가늠할 줄 알아야 합니다. 일반적으로 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..
[코딩인터뷰] 너비 우선 탐색 Breadth first search (BFS) 너비 우선 탐색 Breadth first search (BFS) 너비 우선 탐색 (BFS) 는 코딩 테스트 출제 빈도가 높은 전략입니다. 그래서 반드시 알고 있어야 하고 문제에 활용 가능할지 판단할 수 있어야 합니다. BFS 는 이름 그대로 너비를 우선하여 탐색하는 전략입니다. 그래프에서 각 노드를 방문하면서 방문한 노드와 연결된 노드들을 큐에 추가하고 빼면서 각 노드를 한 번씩 탐색하게 됩니다. 각 탐색을 진행하면서 문제가 요구하는 정답 찾아 가게 됩니다. BFS 는 전략 특성상 '노드 방문 여부'를 체크하지 않으면 무한 반복에 빠질 위험이 있습니다. 따라서 BFS 로 문제를 풀 때는 노드의 방문 여부를 체크하는 코드가 반드시 필요합니다. BFS 전략으로 푸는 대표적인 문제 유형 노드 사..
[코딩인터뷰] 백준 15686번 def set_min(chicken): global n global city global answer total = 0 for i in range(n): for j in range(n): if city[i][j] == 1: dists = [] for c in chicken: dists.append(abs(c[0] - i) + abs(c[1] - j)) total += min(dists) if total < answer: answer = total def dfs(chicken, x, y): global n global m global city if len(chicken) == m: set_min(chicken) return for i in range(x, n): t = 0 if x != i else y f..