본문 바로가기

공부

 (48)
[프로그래머스 DFS/BFS]타겟 넘버 - Python3 문제 https://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+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘 programmers.co.kr n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 ..
[프로그래머스 동적계획법/DP]정사각형 찾기 - Python3 문제 https://programmers.co.kr/learn/courses/18/lessons/1879 알고리즘 문제 해설 - 가장 큰 정사각형 찾기 | 프로그래머스 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.) 예를 들어 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 있다면 가장 큰 정사각형은 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 가 되며..
[프로그래머스 동적계획법/DP]도둑질 - Python3 (Lv.4) 문제 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 | 프로그래머스 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 programmers.co.kr 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 ..
[프로그래머스 동적계획법/DP]등굣길 - Python3 문제 https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 | 프로그래머스 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매 programmers.co.kr 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을..
[프로그래머스 동적계획법(DP)]정수 삼각형 - Python3 문제 https://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 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. ..
[프로그래머스 동적계획법(DP)]타일 장식물- Python3 문제 https://programmers.co.kr/learn/courses/30/lessons/43104 코딩테스트 연습 - 타일 장식물 | 프로그래머스 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다. 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1 programmers.co.kr 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 ..
[알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇 코딩테스트를 준비하면서 여러 문제를 풀다보면, 문제의 입력이 너무 크거나, 반복문과 조건문만으로는 계산하기가 너무 복잡한 경우가 있다. 이런 경우 어거지로 반복문을 돌리면 보통 효율성 테스트를 통과하지 못한다. 그런 경우에 고려해보면 좋은 방법이 바로 동적계획법이다. 동적계획법이란? 동적 계획법(Dynamic Programming)이라는 이름부터가 어려워보인다. 그러나, 사실 그렇게 큰 의미를 담고 있는 말은 아니다. 동적(Dynamic)이라는 말이 들어가서, 뭔가 느낌이 프로그램 실행시간 중에 뭘 어떤 조치를 취해주나 싶겠지만 그렇지 않다. 동적 계획법이라는 단어 자체가 있어보이기 위해서 그렇게 지었다는 말도 있고, 일부러 다른 사람들이 의미를 잘 모르게 하려고 지었다는 말도 있다. 그러니 꼭 이름 그..
[프로그래머스 힙]라면 공장 - Python3 문제 https://programmers.co.kr/learn/courses/30/lessons/42629 코딩테스트 연습 - 라면공장 | 프로그래머스 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량 programmers.co.kr 문제 설명 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 ..

티스토리툴바