본문 바로가기

Lv 24

[프로그래머스] 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 2. 전화번호 목록 def solution(phone_book): hash = {} for n in phone_book: hash[n] = 1 for num in phone_book: arr = "" for n in num: arr += n if arr in hash and arr != num: return False return Truehttps://mainkey.tistory.com/20 [프로그래머스] 전화번호 목록 _ Python 해시Lv.2"전화번호 목록" (출처:프로그래머스) 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. .. 2024. 7. 16.
[프로그래머스] Lv 2. H-index def solution(citations): num_paper = len(citations) #citation.sort(reverse=True) def quick_sort_reverse(citations): if len(citations) pivot] lesser = [x for x in citations[1:] if x 2024. 7. 14.
[프로그래머스] Lv 2. [PCCP 기출문제] 2번 / 석유 시추 from collections import dequedef bfs(a, b, result, visited, land): dx = [0,0,1,-1] dy = [1,-1,0,0] n = len(land) m = len(land[0]) cnt = 0 visited[a][b] = 1 q = deque() q.append((a, b)) min_y, max_y = b, b while q: x, y = q.popleft() min_y = min(min_y, y) max_y = max(max_y, y) cnt += 1 for i in range(4): nx = x + dx[i] .. 2024. 7. 14.

티스토리툴바