본문 바로가기

PS/프로그래머스

 (64)
[프로그래머스-DFS/BFS] 여행경로_파이썬 ❌❌ programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr from collections import defaultdict def solution(tickets): tickets.sort(reverse = True) dic = defaultdict(list) for t1, t2 in tickets: dic[t1].append(t2) answer = [] stack = ["ICN"] while stac..
[프로그래머스-DFS/BFS] 단어 변환_파이썬 ❌❌ programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr def solution(begin, target, words): answer = 0 queue = [begin] while True: temp = [] for word1 in queue: if word1 == target: return answer for word2_idx in range(len(words)-1, -1, -1): wo..
[프로그래머스-DFS/BFS] 네트워크_파이썬 ❌❌ programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr def solution(n, computers): answer = 0 visited = [False] * n for i in range(n): if visited[i] == False: dfs(n, computers, visited, i) answer += 1 return answer def dfs(n, computers, visited, i): visited[i] = ..
[프로그래머스-DFS/BFS] 타겟 넘버_파이썬 ❌❌ programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr answer = 0 def dfs(idx, numbers, target, value): global answer l = len(numbers) if idx == l and value == target: answer += 1 return if idx == l: return dfs(idx+1, numbers, target, v..
[프로그래머스-동적계획법] 도둑질_파이썬 ❌⭕ programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr def solution(money): l = len(money) dp0 = [0] * len(money) dp0[0] = money[0] dp0[1] = max(money[0], money[1]) for i in range(2, l-1): dp0[i] = max(dp0[i-1], dp0[i-2]+money[i]) dp1 = [0] * len(money) dp1[1] = mone..
[프로그래머스-동적계획법] 등굣길_파이썬 ❌🔺 programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr def solution(m, n, puddles): graph = [[0]*(m+1) for _ in range(n+1)] graph[1][1] = 1 for i in range(1, n+1): for j in range(1, m+1): if i == 1 and j == 1: continue if [j, i] in puddles: graph[i][j] = 0 els..
[프로그래머스-동적계획법] 정수 삼각형_파이썬 ❌⭕ programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr def solution(triangle): for i in range(1, len(triangle)): for j in range(i+1): if j == 0: triangle[i][j] += triangle[i-1][j] elif j == i: triangle[i][j] += triangle[i-1][j-1] else: triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j]) return max(tr..
[프로그래머스-동적계획법] N으로 표현_파이썬 ❌❌ programmers.co.kr/learn/courses/30/lessons/42895?language=python3 코딩테스트 연습 - N으로 표현 programmers.co.kr def solution(N, number): dp = [] for i in range(1, 9): numbers = set() numbers.add(int(i*str(N))) for j in range(i-1): for x in dp[j]: for y in dp[i-j-2]: numbers.add(x+y) numbers.add(x*y) numbers.add(x-y) if y != 0: numbers.add(x//y) if number in numbers: return i dp.append(numbers) return -1 d..

티스토리툴바