본문 바로가기

PS25

[프로그래머스] 거스름돈 문제 설명 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다. 5원을 1개 사용해서 거슬러 준다. 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세.. 2022. 6. 16.
[프로그래머스] 야근 지수 문제 설명 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. 제한 사항 works는 길이 1 이상, 20,000 이하인 배열입니다. works의 원소는 50000 이하인 자연수입니다. n은 1,000,000 이하인 자연수입니다. 입출력 예 works n result [4, 3, 3] 4 12 [2, 1, 2] 1 6 [1,1] 3.. 2022. 6. 16.
[백준 14500] 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이번 문제는 약한 빡구현 문제입니다. 5개의 도형이 있고 이 도형이 회전/대칭 한 모양에 대해 맵을 전체 순회하면서 해당 도형과 일치하는 부분의 합이 가장 큰 값을 구하는 문제입니다. 1*4 사각형과 2*2 사각형은 길이가 4, 2이기 때문에 따로 처리하고 나머지 3 도형은 3*3 배열안에 각 도형 모양에 맞게 선언해 주었습니다. 그리고 전체 맵의 길이를 상하좌우 +2만큼 증가시켜 위 3*3 배열.. 2022. 6. 9.
[백준 12100] 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 이 문제는 완전탐색으로 해결 할 수 있는 문제이다. 시간복잡도를 계산해 보면 재귀를 5번 호출하는것 20*20*4^5 인데 4^5는 상하좌우를 움직이면서 재귀호출하고 매번 상하좌우로 움직일때 총 블록의 갯수가 20*20이 되기 때문이다. 이 문제에서 고려해야할 부분은 총 2가지 인데 1. 상하좌우를 움직일때 기존의 map 에서 돌아야하기 때문에 기존 상태를 갖는 map.. 2021. 10. 4.
[종만북] 6.5 재귀호출과 완전탐색[게임판 덮기] 게임판 덮기 문제는 3칸짜리 블록을 H x W 의 보드에 몇 가지의 방법으로 맞출수 있는지 구하는 경우의 수 문제이다. 블록은 총 4가지 모양인데 ㄱ, ㄴ, ┌, ┘ 이런 모양으로 되어있다. 사고 과정 0. 블록이 들어가는 갯수가 3의 배수가 아니면 0을 리턴 1. 특정 지점 row와 col에서 위 4가지 모양에 대한 위치를 구하는 배열을 구한다. 2. 해당 모양에 대한 조건이 일치하면 블록을 그리고 일치하지 않으면 다음을 진행 3. 기존 상태를 복구하여 다른 모양일때를 구한다. 4. 모든 맵이 블록으로 꽉차면 리턴한다. 이렇게 사고과정을 하였고 구현을 진행했다. 그런데 구현중에 값이 너무 크게 나와 뭔가 잘못됐다는 걸 느꼇다. 나는 한 블록을 그리고 다음 블록을 그릴 위치를 구할때 i와 j를 0부터 시.. 2021. 9. 29.
[종만북] 6.4 재귀호출과 완전탐색[소풍] 소풍 문제는 서로 친구들끼리 짝을 지어주는 경우의 수를 만드는 문제이다. 입력은 학생 수 와 친구 쌍의수가 주어지고 그 다음줄은 서로 친구인 두학생의 번호가 주어진다. 예를 들면 학생수는 4명 친구 쌍은 6쌍일때 0 1 1 2 2 3 3 0 0 2 1 3 0과 1은 친구이고, 1과 2는 친구이고.... 이렇게 숫자 2개씩 한쌍을 이룬다. 그리고 학생수는 항상 짝수이다 사고 과정 1. 문제를 잘못이해 했는데 친구가 아예 없는 경우까지 생각해서 고민을 했다. 2. 이때 생각난건 순열이었는데 중복되는 경우를 어떻게 처리할지 고민했다. 예를 들면 (1,2) (0,3)과 (2,1) (3,0)은 같은 경우인데 순열로 나열하면 다른 경우로 들어가기 때문이다. 결국 순열에 집착해 옳바른 방향으로 생각하지 못하여 데이터.. 2021. 9. 29.

티스토리툴바