파이썬 9

(파이썬) [알고리즘 문제 풀이] - 도둑질 (프로그래머스)

문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 풀이 저는 이 문제를 다이나믹 프로그래밍으로 풀었습니다. 이 문제에서 가장 중요한 포인트는 인접한 두 집을 털수 없다는 것입니다. 예를 들어 다음과 같은 테이블이 있다고 하면, money = [2..

(파이썬) [알고리즘 문제 풀이] - 정수 삼각형 (프로그래머스)

설명 오늘은 프로그래머스에서 레벨3 문제 정수 삼각형을 풀어 보았습니다. 이렇게 삼각형이 주어집니다. 위에서부터 값을 더해가면서 내려오는데 아래로 내려갈때는 대각선 왼쪽과 오른쪽으로만 이동이 가능합니다. 이렇게 삼각형이 바닥까지 내려왔을때 가장 큰 값을 찾는 문제 입니다. 저는 이 문제를 다이나믹 프로그래밍을 써서 풀어보았습니다. 다이나믹 프로그래밍을 통해 찾은 값들을 저장할 테이블이 필요 꼭대기부터 차례 차례 값 더하기 내려갈수 있는 방향이 2개이기 때문에 겹치는 부분은 값을 비교해서 더 높은 값을 선택 위의 사진에 있는 삼각형을 예시로 들어보면, 이 후에 마지막 줄에서 최대값을 찾아서 리턴해주면 알고리즘은 완성이 됩니다. 코드 def solution(triangle): dp = [[0 for i in..

(파이썬) [알고리즘 문제 풀이] - 히샤드 수 (프로그래머스)

문제 설명 양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요. 풀이 숫자 x를 x의 자릿수들을 모두 더한값으로 나눴을때 나누어 떨어지는지 그렇지 않은지 구분하는 문제 입니다. 숫자 x의 자릿수들을 더하기 위해 숫자 x의 string 형태가 필요 각 자릿수들을 integer 형태로 바꾼 뒤 총 합을 구함 x를 각 자릿수의 총합으로 나눈 숫자의 나머지가 0인지 확인 코드 def solution(x): x_str = str(x) sum_digit = sum( [ int(y) for y i..

(파이썬) [알고리즘 문제 풀이] - 수박수박수박수박수박수? (프로그래머스)

문제 설명 길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다. 풀이 주어진 숫자 n의 길이만큼 문자열 "수박"을 연장 시키면 되는 문제 입니다. 우선, "수박"이라는 문자열을 변수로 지정해둡니다. n 범위의 for 문을 사용하여 "수"와 "박"을 번갈아가면서 빈 문자열에 더 하도록 합였습니다. 문자열 "수박"에서 인덱스 0은 "수"이고 인덱스 1은 "박"입니다. 오직 인덱스 0과 1만 필요함으로 for 문의 인덱스 i에서 2로 나눈 나머지만 나오도록 하였습니다. 어떤 숫자든지 2로 나눈 나머지는 0이나 1만 가능하기 때문에 그렇습니다. 코드 def sol..

(파이썬) [알고리즘 문제 풀이] - 야근 지수 (프로그래머스)

문제 설명 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다. Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. 풀이 n은 현재 남아 있는 일할수 있는 시간이며 이 시간을 활용하여 works안에 있는 잔업마다 필요한 시간들을 줄여야 합니다. n 시간을 모두 사용하고도 남은 잔업의 시간들은 각각 제곱한 후에 더 합니다. 그리고 이 값을 야근 피로도 라고 부릅니다. 즉, 야근 피로도..

(파이썬) [알고리즘 문제 풀이] - 콜라츠 추측 (프로그래머스

프로그래머스의 연습 문제중 하나인 콜라츠 추측 입니다. 숫자가 한개 주어지며 규칙은 간단합니다. 주어진 숫자가 짝수라면 2로 나눈다. 주어진 숫자가 홀수라면 3을 곱하고 1을 더한다. 주어진 숫자가 1이 될때까지 반복한다. 단, 500번을 반복해도 1이 되지 않는다면 -1을 리턴한다. 위의 작업을 진행하기 위해서는 loop이 한개 필요합니다. For loop을 써도 되고 While loop을 써도 괜찮아 보이네요. 위 작업을 한번 할때마다 따로 variable을 만들어서 기록 해둡니다. loop은 주어진 숫자가 1이 되거나 작업 횟수가 500번이 넘어가면 멈추는 조건이 있어야 하겠네요. 짝수인지 홀수인지 구분하는건 if statement를 써서 2로 나눴을때 나머지가 0인지 체크 했습니다. def sol..

(파이썬) [알고리즘 문제 풀이] - 문자열 내 마음대로 정렬하기 (프로그래머스)

프로그래머스의 문제 중 하나인 문자열 내 마음대로 정렬하기 입니다. 문자열로 구성된 리스트 strings와 n에 대하여 strings를 n번째 인덱스로 정렬해서 리턴하면 되는 문제입니다. 문제에서 요구하는 정렬을 하기 위해서는 딱 2가지 규칙이 필요합니다. n번째 인덱스를 기준으로 오름차순 동일한 n번째 인덱스가 여럿일 경우 사전 순으로 정렬 사전 순으로 먼저 정렬을 한 후에 n번째 인덱스를 기준으로 정렬을 나중에 하여 문제에서 요구하는 조건을 달성했습니다. def solution(strings, n): strings.sort() strings.sort(key = lambda x:x[n]) return strings 파이썬에서는 lambda를 이용하여 특정 인덱스를 기준으로 하는 정렬을 이용할수 있습니다..

(파이썬) [알고리즘 문제 풀이] - 같은 숫자는 싫어 (프로그래머스)

오늘 풀어본 문제는 프로그래머스의 레벨1 문제중에 하나인 같은 숫자는 싫어 입니다. 숫자 배열이 하나 주어집니다. 이 숫자 배열 안에는 연속되는 숫자도 있고 그렇지 않은 숫자도 있습니다. 여기서 연속되는 숫자를 하나만 남기고 모두 제거하는 문제 입니다. 우선, 배열 안의 숫자들을 차례대로 두개씩 찾아 비교하기 위해 for loop이 하나 필요합니다. for loop 안에서 숫자와 그 바로 이전의 숫자가 서로 다른 경우 연속되는 숫자가 아니란 뜻임으로 따로 저장해둡니다. 알고리즘을 돌려보면 이런식으로 숫자가 저장되는걸 볼수 있습니다. def solution(arr): answer = [arr[0]] for i in range(1,len(arr)): if arr[i] != arr[i-1]: answer.ap..

(파이썬) [알고리즘 문제 풀이] - 위장 (프로그래머스)

오늘은 프로그래머스에서 위장이라는 문제를 풀어 보았습니다. Input은 옷의 종류와 이름이 담긴 배열로 주어집니다. 옷의 종류는 중복이 있을수 있으나 옷의 이름은 모두 다릅니다. 예를 들면 같은 하의 라도 청바지가 있고 반바지가 있을수 있습니다. 이 부분을 보시면 떠오르는 자료구조가 있을껍니다. 파이썬에는 key와 value로 이루어진 dictionary가 있습니다. 옷의 종류가 key가 되고 옷의 이름이 value가 된다고 생각하시면 됩니다. 여기까지 왔으면 이 문제의 반은 해결했다고 보시면 됩니다. 이제부터 모든 경우의 수를 계산해야 되는데 매우 간단합니다. 만약 옷의 종류가 A,B,C 이렇게 3가지가 있다면, 더보기 (A 타입의 옷의 개수 + 1) * (B 타입의 옷의 개수 + 1) * (C 타입의..