본문 바로가기

Develop/코딩인터뷰

[코딩인터뷰] 백준 3020번 개똥벌레 Prefix Sum 누적 합 import sys N, H = map(int, input().split()) MAX = H + 2 top = [0] * MAX bottom = [0] * MAX for k in range(N): v = int(input()) if k % 2 == 1: bottom[v] += 1 else: top[v] += 1 total_top = [0] * MAX total_bottom = [0] * MAX for i in reversed(range(1, H+1)): total_bottom[i] = bottom[i] + total_bottom[i + 1] total_top[i] = top[i] + total_top[i + 1] mini = 200001 count = 1 total = [0]..
[코딩인터뷰] 백준 16437번 16437번 양 구출 작전 문제는 "파이썬으로 풀지 말라는게 아닐까" 라는 느낌의 채점 기준이었습니다. 로직이 틀리지 않은거 같은데 왜 통과를 못하고 '메모리 초과' 가 뜰까 싶어서 C++ 정답 코드를 둘러봤는데 로직이 동일한 정답이 있었습니다. 그래서 '어? 환경설정 문젠가?' 싶어서 일단 C++ 정답으로 문제 정답 처리하고 파이썬으로 통과된 코드를 보고 환경설정을 좀 했더니 통과가 되었습니다. 정리하자면, 'PyPy 3' 로 제출하면 '메모리 초과' 가 발생합니다. 'Python 3' 로 제출하면 '시간 초과' 가 발생합니다. PyPy3 메모리 초과는 아무래도 BFS 방식으로 풀어야 해결할 수 있어 보이고, Pyth..
[코딩인터뷰] 백준 1987번 DFS import sys sys.setrecursionlimit(10 ** 5) # 세로 R 가로 C # 같은 알파벳 통과 불가 # (0,0) 포함 시작 def dfs(c, x, y): global answer if answer < c: answer = c for k in range(4): nx = x + dx[k] ny = y + dy[k] if 0
[코딩인터뷰] 백준 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