본문 바로가기

Develop/코딩인터뷰

[코딩인터뷰] 백준 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..
[코딩인터뷰] 백준 15684번 def is_completed(): global n global h global ladder for b in range(n): s = b for a in range(h): if 0 < s and ladder[a][s-1]: s -= 1 continue if ladder[a][s]: s += 1 continue if s != b: return False return True def dfs(count, a, b): global n global h global ladder global answer if is_completed(): if count < answer: answer = count return if count == 3: return # 현재 b = 세로선부터 마지막 바로 전 세로선까지만 # i = 세..
[코딩인터뷰] 백트래킹 Back tracking 백트래킹 Back tracking 백트래킹 (Back tracking)은 문제 해결 전략 중 하나로, 가능한 모든 경우의 수를 탐색하는 전략인 브루트 포스(Brute force) 전략에서 특정 조건을 만족하지 못하는 경우의 수들을 탐색 범위에서 제외시키며 탐색하는 전략입니다. 브루트 포스 전략은 모든 경우의 수를 전부 탐색하지만 백트래킹 전략은 특정 조건을 만족하지 못하는 경우의 수를 탐색에서 제외하기 때문에 브루트 포스 전략보다 탐색 효율이 좋습니다. 백트래킹 전략은 재귀적으로 조건을 만족하는지 검토하면서 정답을 완성합니다. 정답을 완성하는 과정 중 조건을 만족하지 못하는 경우의 수와 관련된 경우의 수들을 탐색 범위에서 제외시킵니다. 첫 정답이 완성되면 전 상태로 되돌리고 다른 가능한 경우의 수를 탐색..
[코딩인터뷰] 백준 14888번 Python3 는 시간초과 가 발생합니다. itertools.permutations 함수가 시간이 오래 걸리기 때문입니다. PyPy3 로 변경하면 통과됩니다. 저는 개인적으로 알고리즘 효율성에 큰 의미를 두지는 않습니다. 효율성이 중요하지 않다는건 아닌데, 실무를 하다보니 주어진 개발 기간을 코드의 효율을 개선하는데 투자하기 보다는 전체 설계를 개선할 수 있는 코드 또는 가독성이 좋아지는 코드를 짜는데 시간을 투자하는게 생산성이 더 높다고 생각합니다. 기간 내에 정확하게 개발해서 출시한 뒤에 효율이 크게 뒤떨어지는 부분부터 제품을 개선해 나가는 재미도 있으니까요. 당연히 효율 높은 코드를 바로바로 구현할 수 있도록 훈련을 지속적으로 하면 생산성과 효율 모두 달성할 수 있으니, 코딩 테스트로 연습할 때는 ..

티스토리툴바