5. 정수 삼각형 (DP)
2024. 7. 19. 23:59
프로그래머스/Lv. 3
유형 : DP난이도 쉬움. 풀이 시간 : 15분 def solution(triangle): answer = 0 solution = [[0] * i for i in range(1, len(triangle[len(triangle)-1])+1)] solution[0][0] = triangle[0][0] for i in range(1, len(triangle)): for j in range(len(triangle[i])): if j == 0: solution[i][j] = solution[i-1][j] + triangle[i][j] elif j == len(triangle[i])-1: ..
4. 여행경로 ★★
2024. 7. 19. 23:03
프로그래머스/Lv. 3
유형 : DFS풀이 시간 : 인터넷 검색 경로 찾는 문제는 DFS가 훨씬 편한 것 같다는 생각.. DFS를 사용할지 BFS를 사용할지도 잘 판단해야 할 듯. from collections import deque def solution(tickets): answer = [] visited = [False] * len(tickets) #재귀를 이용한 DFS 시작 def dfs(curr, path): #종료 조건 : PATH가 완성되었을 경우 if len(path) == len(tickets) + 1: answer.append(path) #정답 후보 집합에 append return #다음 노..
3. 단어 변환 (BFS)
2024. 7. 19. 22:10
프로그래머스/Lv. 3
유형 : BFS 풀이 시간 : 15분 from collections import deque def solution(begin, target, words): answer = 0 queue = deque() queue.append([begin, 0]) words.insert(0, begin) visitdict = dict([[word, False] for word in words]) visitdict[begin] = True #최단 거리 - bfs 사용 while queue: [curr, curcnt] = queue.popleft() for word in words: dif = 0 for i ..
2. 네트워크
2024. 7. 19. 21:06
프로그래머스/Lv. 3
유형 : BFS/DFS (어떤 걸 해도 상관 없을 듯)풀이 시간 : 15분 예전에 과제로 비슷한 문제를 수행한 적이 있어서 쉽게 풀었다. visited를 활용, 만약 방문하지 않은 노드가 있다면 answer += 1을 해 주고 (네트워크가 존재한다는 뜻)해당 노드를 기점으로 방문 가능한 노드를 전부 방문한다. (bfs, dfs)from collections import dequedef solution(n, computers): answer = 0 visited = [False for i in range(n)] for i in range(n): if visited[i] == False: answer += 1 #..
1. 베스트앨범 (해시 테이블) ★ (이차원 함수의 정렬)
2024. 7. 17. 23:24
프로그래머스/Lv. 3
유형 : 해시풀이 시간 : 20분 def solution(genres, plays): answer = [] gendict = {} for i in range(len(genres)): if genres[i] in gendict: gendict[genres[i]][0] += plays[i] gendict[genres[i]][1].append([plays[i], i]) else: gendict[genres[i]] = [plays[i], [[plays[i], i]]] vlist = list(gendict.values()) vlist.sort(reverse = True) for v i..