본문 바로가기

Problem Solving/Programmers - Python

 (43)
[Python | 파이썬] 도둑질 (프로그래머스 DYNAMIC PROGRAMMING) [Python | 파이썬] 도둑질 (프로그래머스 DYNAMIC PROGRAMMING) 원형으로 이어진 집들 중에서 이어진 두 집은 연속으로 털 수 없다. 따라서 첫번째 집을 터는 경우에는 마지막 집을 털 수 없다. 첫번째 집을 터는 경우는 따라서 n-1번째 집까지만 확인해야한다. 그리고 첫번째 집을 털지 않는 경우에는 dp[0] = 0이어야 한다. 마지막 집을 털어도 되기 때문에 n번째 집까지 확인한다. 더보기 def solution(money): answer = 0 n = len(money) dp_1, dp_2 = [0 for _ in range(n-1)], [0 for _ in range(n)] dp_1[0] = money[0] dp_1[1] = max(money[0], money[1]) for i ..
[Python | 파이썬] 등굣길 (프로그래머스 DYNAMIC PROGRAMMING) [Python | 파이썬] 등굣길 (프로그래머스 DYNAMIC PROGRAMMING) 이 문제는 dynamic programming을 이용해서 풀 수도 있지만 BFS를 이용해서 풀 수도 있다. 움직이는 방향은 최단거리를 유지해야하므로 오른쪽으로 가거나 아래로 가야한다. 최단경로의 갯수를 리턴해야하므로 처음에 maps[0][0]에서의 경로의 갯수는 1으로 시작한다. 그리고 queue에 현재 좌표를 삽입하고, queue에 원소가 남아있을 때까지 반복문에서 매번 pop해주며 현재 좌표에서 오른쪽이나 아래쪽으로 이동가능하다면 queue에 그 좌표를 삽입한다. 또한 mapx[nx][ny] += maps[x][y]로 경로를 추가해준다. 더보기 dx = [0, 1] dy = [1, 0] from collections..
[Python | 파이썬] 정수 삼각형 (프로그래머스 DYNAMIC PROGRAMMING) [Python | 파이썬] 정수 삼각형 (프로그래머스 DYNAMIC PROGRAMMING) 각 행마다 열의 개수는 각 행의 번호 + 1과 같다. 0행 => 1열 1행 => 2열 2행 => 3열 ... n번째 행 => n + 1개의 열이 존재 현재 열이 0 ( j == 0 )이라면 왼쪽 위는 j == -1이므로 불가능하고 오른쪽 위에서만 올 수 있다. 현재 열이 j == i라면 오른쪽 위는 불가능하고 왼쪽 위에서만 올 수 있다. 변수 triangle을 사용안하고 처음부터 dp를 사용해 푸는 방법 더보기 def solution(dp): answer = 0 n = len(dp) for i in range(1, n): for j in range(i+1): if j == 0: right = dp[i-1][j] l..
[Python | 파이썬] N으로 표현 (프로그래머스 DYNAMIC PROGRAMMING) [Python | 파이썬] N으로 표현 (프로그래머스 DYNAMIC PROGRAMMING) N의 사용횟수의 최소값을 return하는 함수를 작성하는 것이고, 최솟값이 8보다 크면 -1을 return 하도록 한다. N = 5일때 사용 횟수를 X로 하고 X번 사용했을 때 나타낼 수 있는 수 [X = 1] 5 ( i = 1) [X = 2] 55 5 + 5, 5 - 5, 5 * 5, 5 / 5 (i = 2, j = 0) [X = 3] 555 55 + 5, 55 - 5, 55 * 5, 55 / 5 5 + (5 + 5), 5 - (5 + 5), 5 * (5 + 5), 5 / (5 + 5) 5 + (5 - 5), 5 - (5 - 5), 5 * (5 - 5) * 5, 5 / (5 - 5) 5 + (5 * 5), 5 -..
[Python | 파이썬] H-Index (프로그래머스 정렬) [Python | 파이썬] H-Index (프로그래머스 정렬) h번 이상 인용된 논문의 갯수가 h개 이상일 때 h의 최대값을 구하는 문제이다. 따라서 h는 최대 n을 넘을 수 없다. 각 인용횟수 이상으로 인용된 논문들의 개수를 담고있는 배열 arr을 이용해 인용횟수가 i인 논문이 나타나면 arr[1] 부터 arr[i]까지 1씩 증가시킨다. 각 논문의 인용횟수를 차례대로 접근하면서 논문의 인용횟수가 n보다 크다면 h를 n으로 만든다. 그리고 각 논문이 최대로 인용될 수 있는 횟수부터 1번 이상 인용되는 경우의 횟수까지 1씩 더한다. 더하면서 인용횟수를 1씩 감소한다. 그리고 각 인용횟수 이상으로 인용된 논문들의 개수를 담고있는 배열 arr에서 조건을 만족하는 최대값을 찾아 return한다. 더보기 def ..
[Python | 파이썬] 가장 큰 수 (프로그래머스 정렬) [Python | 파이썬] 가장 큰 수 (프로그래머스 정렬) 가장 큰 수를 만들기 위해서는 주어진 numbers 배열을 각 숫자의 길이가 한글자라면 이뒤에도 이것과 같은 글자가 이어졌다고 생각하고 내림차순으로 정렬하고 앞에서부터 쭉 연결하면 된다. 즉 9와 90이 주어진다면 909 보다는 990이 크다. 따라서 9가 90보다 먼저오도록 정렬하려면 9를 99로 생각하고 정렬해야한다. 문제에서 주어진 numbers의 각 원소는 0 이상 1000 이하이므로 최대 한자리수가 세자리수와 비교될 수 있도록 모든 글자의 길이를 3배로 한다. 더보기 def solution(numbers): answer = '' numbers = list(map(str, numbers)) numbers.sort(key = lambda ..
[Python | 파이썬] K번째수 (프로그래머스 정렬) [Python | 파이썬] K번째수 (프로그래머스 정렬) 더보기 def solution(array, commands): answer = [] for i in commands: temp = array[i[0]-1:i[1]] temp.sort() answer.append(temp[i[2]-1]) return answer https://programmers.co.kr/learn/courses/30/lessons/42748?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr
[Python | 파이썬] 이중우선순위큐 (프로그래머스 HEAP) [Python | 파이썬] 이중우선순위큐 (프로그래머스 HEAP) 이문제는 대놓고 우선순위큐를 이중으로 쓰라고 말해주고 있다. 따라서 최소힙과 최대힙을 두개 구현하여 푸는 단순한 방법이 있고, heapq 라이브러리의 다른 함수를 써서 푸는 방법이 있다. 주의할 점은 최소힙과 최대힙 중 한곳에서 팝해준 뒤에 다른 힙에서는 remove 연산을 해줘야한다는 것이다. 또한 최대힙을 구현하기위해서는 데이터를 -를 붙여서 heappush해주고, 빼준뒤에는 다시 -를 붙여줘야 원래 데이터의 값이 나온다. => -를 붙인 데이터를 최소힙에서 찾아서 remove해주면 된다. 새로 알게된 heapq의 함수 - heapq.nlargest(n, heap) heap에서 큰 순서대로 n개의 수를 뽑아준다. - heapq.nsma..

티스토리툴바