본문 바로가기

알고리즘 배우기20

[프로그래머스] Lv 2. 전력망을 둘로 나누기 완전탐색으로 분류된 문제이며, 트리라는 구조를 생각하게 하게 하는 문제였다.항상 완전탐색 문제를 풀기전에는 이 모든 경우를 전부 연산하면 제한시간에 걸리는게 아닌가? 라는 생각이 든다.최악의 경우를 생각해서 runtime을 예상하면 된다고 한다. (10억번 연산에 1초)해당 문제는 정해진 runtime이 없지만 10초라고 생각하고 계산해보자. (메모리 제약은 100MB로 넉넉하게 주는게 아니면, 어쩌면 DP문제라고 바로 알아차릴 수 있을지도?,,)노드수는 최대 100개 그렇다면 만들어질 수 있는 edge수는 n(n+1)/2 = 약 5000개스펙: map=100*100, visitied=100, edge수 5000개완전탐색의 경우, [map 생성 및 접근:20,000, visitied 생성 및 탐색: 20.. 2024. 8. 17.
[프로그래머스] Lv 3. 정수 삼각형 처음으로 풀어본 DP문제Top-Down으로 해결했다. Bottom-up 방식은 풀이를 보아도 이해가 되지 않으므로, 일단 생략def solution(triangle): height = len(triangle) for h in range(1, height): for i in range(h+1): if i == 0: triangle[h][i] += triangle[h-1][i] elif i == h: triangle[h][i] += triangle[h-1][i-1] else: triangle[h][i] += max(triangle[h-1][i-1].. 2024. 7. 20.
[프로그래머스] Lv 2. 게임 맵 최단거리 def solution(maps): answer = 0 #상,하,좌,우 X = len(maps[0]) Y = len(maps) visited = [[False for _ in range(X)] for _ in range(Y)] dx = [0,0,-1,1] dy = [-1,1,0,0] queue = [] def bfs(x, y): visited[y][x] = True queue.append([y, x]) while queue: current = queue.pop(0) y, x = current[0], current[1] for i in.. 2024. 7. 19.
[프로그래머스] Lv 3. 네트워크 def solution(n, computers): visited = [False for i in range(n)] cnt = 0 def bfs(idx, visited): visited[idx] = True queue = [] queue.append(idx) while len(queue) > 0: current = queue.pop(0) visited[current] = True for i, value in enumerate(computers[current]): if value == 1 and visited[i] == False: .. 2024. 7. 19.

티스토리툴바