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: ..
18. 입국심사 ★★
2024. 7. 19. 23:44
프로그래머스/Lv. 2
유형 : 이분 탐색풀이 시간 : 인터넷 검색 def solution(n, times): times.sort() answer = 0 #이분 탐색 start = 0 end = n * times[len(times)-1] #최댓값 = 가장 오래 걸릴 경우 while start = n: #탐색 가능한 경우 answer = mid #우선 답을 저장 end = mid - 1 #더 작은 값을 찾기 위해 앞부분 탐색 return answer 풀이법이 정말 기발한.. 문제였다.이게 왜 이분탐색이야!? 싶었던 문제... 0~최대 시간까지의 범위에서mid 시간을 지정, 그 시간 내에 검사할 수 있는 사람의 수를 구..
17. 조이스틱 ★★ - 보류
2024. 7. 19. 23:28
프로그래머스/Lv. 2
유형: 그리디? 완전탐색?풀이 시간: 인터넷 검색 1. 나의 풀이def solution(name): answer = 0 a = ord('A') z = ord('Z') olist = [] for i in name: n = min (abs(ord(i) - a), abs(z - ord(i) + 1)) olist.append(n) answer += n cnt1 = 0 for i in range(len(olist)-1): if olist[i+1:].count(0) == len(olist[i+1:]): break cnt1 += 1 cnt2 = 0 olist...
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 #..
16. 게임 맵 최단거리 ★ (BFS, zip)
2024. 7. 19. 20:41
프로그래머스/Lv. 2
유형 : BFS풀이 시간 : 30분 *최단거리 == BFS를 이용해 풀이하자!!**visted queue를 잊지 말자!!*from collections import deque def solution(maps): answer = 0 msize = len(maps) nsize = len(maps[0]) queue = deque() visited = deque() #initialization queue.append([0, 0]) visited.append([0, 0]) #순회를 위한 dx, dy dx = [1, 0, 0, -1] dy = [0, 1, -1, 0] #bfs search while queue: [cur..
15. 타겟 넘버 ★(DFS)
2024. 7. 18. 23:12
프로그래머스/Lv. 2
유형 : DFS풀이 시간 : 인터넷 참고 from collections import dequedef solution(numbers, target): #dfs 구현 answer = 0 stack = deque() ln = len(numbers) #첫 번째 원소를 insert하고 시작 stack.append([numbers[0], 0]) stack.append([-numbers[0], 0]) while stack: [curracc, curridx] = stack.pop() if curridx == ln-1: if target == curracc: answer += 1 el..